Class Fairness in Online Matching
DOI:
https://doi.org/10.1609/aaai.v37i5.25704Keywords:
GTEP: Fair Division, GTEP: Mechanism Design, GTEP: Social Choice / VotingAbstract
We initiate the study of fairness among classes of agents in online bipartite matching where there is a given set of offline vertices (aka agents) and another set of vertices (aka items) that arrive online and must be matched irrevocably upon arrival. In this setting, agents are partitioned into a set of classes and the matching is required to be fair with respect to the classes. We adopt popular fairness notions (e.g. envy-freeness, proportionality, and maximin share) and their relaxations to this setting and study deterministic and randomized algorithms for matching indivisible items (leading to integral matchings) and for matching divisible items (leading to fractional matchings). For matching indivisible items, we propose an adaptive-priority-based algorithm, MATCH-AND-SHIFT, prove that it achieves (1/2)-approximation of both class envy-freeness up to one item and class maximin share fairness, and show that each guarantee is tight. For matching divisible items, we design a water-filling-based algorithm, EQUAL-FILLING, that achieves (1-1/e)-approximation of class envy-freeness and class proportionality; we prove (1-1/e) to be tight for class proportionality and establish a 3/4 upper bound on class envy-freeness.Downloads
Published
2023-06-26
How to Cite
Hosseini, H., Huang, Z., Igarashi, A., & Shah, N. (2023). Class Fairness in Online Matching. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5673-5680. https://doi.org/10.1609/aaai.v37i5.25704
Issue
Section
AAAI Technical Track on Game Theory and Economic Paradigms