Before revision: In typical online matching problems, the goal is to maximize the number of matches. This paper studies online bipartite matching from the perspective of group-level fairness, and the goal is to balance the number of matches made across different groups of online nodes. We assume that an online node's group belongings are revealed upon arrival, and measure performance based on the group with the smallest fraction of its nodes matched at the end. We distinguish between two different objectives: long-run fairness, where the algorithm is audited for its fairness over many realizations from the same instance;
After revision: We consider the allocation of limited resources to heterogeneous customers who arrive in an online fashion. We would like to allocate the resources "fairly", so that no group of customers is marginalized in terms of their overall service rate. We study whether this is possible to do so in an online fashion, and if so, what a good online allocation policy is. We model this problem using online bipartite matching under stationary arrivals, a fundamental model in the literature typically studied under the objective of maximizing the total number of customers served. We instead study the objective of maximizing the minimum service rate across all groups, and propose two notions of fairness: long-run fairness, where the algorithm is audited for its fairness over many realizations from the same instance;