Egalitarian Repeated Matching

Abstract:

We investigate maximin fairness in repeated matching problems, aiming to maximize the cumulative value received by the worst-off agent over multiple allocation rounds. When agent valuations are known, we prove that computing an optimal sequence is NP-hard, but we develop approximation algorithms that guarantee the worst-off agent's value falls within an additive offset of the optimal, regardless of the time horizon. We also explore the stricter notion of anytime optimality, which requires maximizing the minimum value at every round. While deciding if an instance admits an anytime optimal solution is coNP-hard for three or more agents, we provide exact algorithms for two agents and other special cases, such as binary valuations. Transitioning to unknown valuations, we model the problem as a stochastic semi-bandit where preferences must be learned through interaction. We refine a UCB-based matching framework to achieve a sublinear ex-ante regret bound alongside a nearly matching lower bound. These results are extended to scenarios involving K types of goods and identical valuations, for which we develop a block-based round-robin algorithm that establishes both gap-dependent and gap-independent regret bounds.