论文标题
反复将项目与代理商公平有效地匹配
Repeatedly Matching Items to Agents Fairly and Efficiently
论文作者
论文摘要
我们考虑了一个新颖的设置，其中一组项目在多个回合中反复匹配相同的代理。每个代理商每回合完全获得一个项目，这给找到高效和/或公平{\ em重复匹配}带来了有趣的挑战。我们模型的一个特定功能是，某个回合中代理的价值取决于代理商过去使用的项目的数量。我们提供了一组关于重复匹配的效率和公平性的正面和负面结果。例如，当物品是商品时，在某些条件下，可以满足嫉妒性的广泛性概念的变化（ef1）。此外，即使可以单独实现公平和（近似）效率，也很难达到公平性和（近似）效率。对于可能是某些代理商和其他代理商的商品的混合物品，我们提出并研究了一种新的公平概念，我们称之为{\ em交换嫉妒}（Swapef）。
We consider a novel setting where a set of items are matched to the same set of agents repeatedly over multiple rounds. Each agent gets exactly one item per round, which brings interesting challenges to finding efficient and/or fair {\em repeated matchings}. A particular feature of our model is that the value of an agent for an item in some round depends on the number of rounds in which the item has been used by the agent in the past. We present a set of positive and negative results about the efficiency and fairness of repeated matchings. For example, when items are goods, a variation of the well-studied fairness notion of envy-freeness up to one good (EF1) can be satisfied under certain conditions. Furthermore, it is intractable to achieve fairness and (approximate) efficiency simultaneously, even though they are achievable separately. For mixed items, which can be goods for some agents and chores for others, we propose and study a new notion of fairness that we call {\em swap envy-freeness} (swapEF).
