论文标题
Matroid排名估值下的公平分配的一般框架
A General Framework for Fair Allocation under Matroid Rank Valuations
论文作者
论文摘要
我们研究了具有Matroid排名估值的代理商中相当分配一组不可分割的商品的问题 - 当添加到捆绑包中时，每种商品都提供$ 0 $或$ 1 $的边际价值。我们将洋基交换算法概括为创建一个简单的框架，称为洋基将军交换，该框架可以有效地计算分配，以最大化任何满足某些轻度假设的正义标准（或公平目标）。除了最大程度地提高司法标准外，洋基掉期将保证最大程度地提高功利主义社会福利，确保最多有二次估值查询的战略性和使用。我们展示了如何使用洋基将军交换来计算五个不同的司法标准的分配：（a）优先考虑洛伦兹的优势，（b）Maximin公平，（c）加权leximin，（d）最大加权的纳什福利，以及（e）最大加权$ p $ p $ -meanean福利。特别是，我们的框架提供了第一个多项式时间算法，用于计算加权级别的leximin，最大加权纳什福利和最大加权$ p $ $ p $ - 英雄福利分配，用于具有矩阵排名估值的代理商。
We study the problem of fairly allocating a set of indivisible goods among agents with matroid rank valuations -- every good provides a marginal value of $0$ or $1$ when added to a bundle and valuations are submodular. We generalize the Yankee Swap algorithm to create a simple framework, called General Yankee Swap, that can efficiently compute allocations that maximize any justice criterion (or fairness objective) satisfying some mild assumptions. Along with maximizing a justice criterion, General Yankee Swap is guaranteed to maximize utilitarian social welfare, ensure strategyproofness and use at most a quadratic number of valuation queries. We show how General Yankee Swap can be used to compute allocations for five different well-studied justice criteria: (a) Prioritized Lorenz dominance, (b) Maximin fairness, (c) Weighted leximin, (d) Max weighted Nash welfare, and (e) Max weighted $p$-mean welfare. In particular, our framework provides the first polynomial time algorithms to compute weighted leximin, max weighted Nash welfare and max weighted $p$-mean welfare allocations for agents with matroid rank valuations.
