优化多次匹配中弱势个体的公平性，确保每轮和最终结果都更公平。
Fairness in Repeated Matching: A Maximin Perspective
- 从最大化最弱势者收益出发设计匹配序列，兼顾全程与每轮公平。
- 证明多数情况计算困难，但提供近似与高效解法。
- 适用于资源分配、任务调度等需长期公平性的场景。
我们研究一种序列决策模型：一组物品在多轮中反复匹配给同一组代理人。目标是寻找匹配序列，使所有轮次结束后最弱势代理的效用最大化（最优），或在每一轮结束时都达到最优（即时最优）。我们分析了求解（即时）最优结果的计算挑战，表明这些问题通常计算上不可行。然而，我们提出了近似算法、固定参数可处理算法，并识别出若干可高效求解的特殊情况。此外，还建立了帕累托最优/最大匹配的刻画，对匹配理论与房屋分配研究可能具有独立价值。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。