Fairness in Repeated Matching: A Maximin Perspective
We study a sequential decision-making model where a set of items is repeatedly matched to the same set of agents over multiple rounds. The objective is to determine a sequence of matchings that either maximizes the utility of the least advantaged agent at the end of all rounds (optimal) or at the end of every individual round (anytime optimal). We investigate the computational challenges associated with finding (anytime) optimal outcomes and demonstrate that these problems are generally computationally intractable. However, we provide approximation algorithms, fixed-parameter tractable algorithms, and identify several special cases whereby the problem(s) can be solved efficiently. Along the way, we also establish characterizations of Pareto-optimal/maximum matchings, which may be of independent interest to works in matching theory and house allocation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Two-Sided Matching Meets Fair Division
We introduce a new model for two-sided matching which allows us to borrow popular fairness notions from the fair division literature such as envy-freeness up to one good and maximin share guarantee. In our model, each ag…
FairnessVocal Bursts Valence PredictionGroupwise Maximin Fair Allocation of Indivisible Goods
We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin sh…
FairnessAchieving Proportionality up to the Maximin Item with Indivisible Goods
We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fai…
FairnessLearning and Fairness in Energy Harvesting: A Maximin Multi-Armed Bandits Approach
Recent advances in wireless radio frequency (RF) energy harvesting allows sensor nodes to increase their lifespan by remotely charging their batteries. The amount of energy harvested by the nodes varies depending on thei…
FairnessMulti-Armed BanditsMaximin Relative Improvement: Fair Learning as a Bargaining Problem
When deploying a single predictor across multiple subpopulations, we propose a fundamentally different approach: interpreting group fairness as a bargaining problem among subpopulations. This game-theoretic perspective r…