Class Fairness in Online Matching

Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, Nisarg Shah

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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/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.

Original languageEnglish (US)
Title of host publicationAAAI-23 Technical Tracks 5
EditorsBrian Williams, Yiling Chen, Jennifer Neville
PublisherAAAI press
Pages5673-5680
Number of pages8
ISBN (Electronic)9781577358800
StatePublished - Jun 27 2023
Event37th AAAI Conference on Artificial Intelligence, AAAI 2023 - Washington, United States
Duration: Feb 7 2023Feb 14 2023

Publication series

NameProceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023
Volume37

Conference

Conference37th AAAI Conference on Artificial Intelligence, AAAI 2023
Country/TerritoryUnited States
CityWashington
Period2/7/232/14/23

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Cite this