Class Fairness in Online Matching
Authors: Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, Nisarg Shah
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 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 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/2approximation 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-fillingbased 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. |
| Researcher Affiliation | Academia | 1 Pennsylvania State University 2 University of Hong Kong 3 University of Tokyo 4 University of Toronto |
| Pseudocode | Yes | ALGORITHM 1: MATCH-AND-SHIFT; ALGORITHM 2: EQUAL-FILLING |
| Open Source Code | No | The paper does not provide any statements about releasing open-source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving datasets, training, or public data access. It uses illustrative examples (e.g., Figure 1, Figure 2) but no specific public datasets. |
| Dataset Splits | No | The paper is theoretical and does not include empirical validation experiments or specify dataset splits (training, validation, test). |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical, presenting algorithms and proofs. It does not describe any software implementations or list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not detail any experimental setups or hyperparameters for empirical evaluation. |