Fairness in Repeated Matching: A Maximin Perspective

Traditional machine learning (ML) algorithms often focus on global objectives such as efficiency (e.g., maximizing accuracy or minimizing error rates in decision-making systems) or maximizing revenue/profit (e.g., maximizing click-through rates for recommendation systems), as they align closely with organizational goals and are more straightforward to quantify and optimize. However, modern approaches increasingly emphasize fairness as a key desideratum, as societal and regulatory demands push for more equitable and responsible ML systems. We consider a multi-agent sequential decision-making scenario where a set of resources must be allocated among agents repeatedly over time, with the objective of achieving fairness in the assignment process. This framework encompasses applications such as dynamic spectrum allocation in wireless networks and energy distribution in smart grids [Elhachmi, 2022, Jain et al., 2022, Rony et al., 2021, Soares et al., 2024]. In the case of spectrum allocation, communication channels must be repeatedly assigned to devices, with each device requiring exclusive access to one channel in each time slot. Persistent disparities in access can degrade system efficiency, reduce user satisfaction, and undermine trust. Similarly, in many other ML-driven resource allocation systems, disparities in the distribution of resources--such as GPUs in distributed computing--can lead to unfair outcomes that compromise the perceived and actual effectiveness of the system. Numerous other applications where decisions are made dynamically--such as assigning tasks to workers in crowdsourcing platforms [Moayedikia et al., 2020], or distributing compute resources in cloud systems [Belgacem, 2022, Gupta et al., 2017, Saraswathi et al., 2015]--call for central decision-makers to ensure that no agent is persistently disadvantaged, which is critical for both fairness and long-term trust in the system. The scenarios described above can be captured using the repeated matching framework--a multi-agent sequential decision-making model in which a set of goods is repeatedly matched to agents over time, and each agent is assigned exactly one good at each round.