论文标题
在非均质矩阵限制下公平划分
On Fair Division under Heterogeneous Matroid Constraints
论文作者
论文摘要
我们研究具有可行性限制的加性代理之间不可分割的商品的公平分配。在这些设置中，每个代理都被限制在指定的一组可行捆绑包中。由于AI社区对现实世界问题的适用性，此类情况引起了人们的极大兴趣。根据一些不可能的结果，我们限制了捕获自然情景的矩阵可行性限制，例如分配向医生的转变，以及将会议论文分配给裁判。 我们专注于一种嫉妒性的普遍公平概念，直到一种善良（EF1）。以前用于查找EF1分配的算法要么仅限于具有相同可行性限制的代理，要么允许物品免费处理。一个开放的问题是，异构药物之间存在EF1的完整分配，在代理的可行性限制及其估值中，异质性既是异质性。在这项工作中，我们通过为不同的矩形和估值类型提供积极和负面的结果来取得进展。 Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) $n$ agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous additive valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable矩阵约束。
We study fair allocation of indivisible goods among additive agents with feasibility constraints. In these settings, every agent is restricted to get a bundle among a specified set of feasible bundles. Such scenarios have been of great interest to the AI community due to their applicability to real-world problems. Following some impossibility results, we restrict attention to matroid feasibility constraints that capture natural scenarios, such as the allocation of shifts to medical doctors, and the allocation of conference papers to referees. We focus on the common fairness notion of envy-freeness up to one good (EF1). Previous algorithms for finding EF1 allocations are either restricted to agents with identical feasibility constraints, or allow free disposal of items. An open problem is the existence of EF1 complete allocations among heterogeneous agents, where the heterogeneity is both in the agents' feasibility constraints and in their valuations. In this work, we make progress on this problem by providing positive and negative results for different matroid and valuation types. Among other results, we devise polynomial-time algorithms for finding EF1 allocations in the following settings: (i) $n$ agents with heterogeneous partition matroids and heterogeneous binary valuations, (ii) 2 agents with heterogeneous partition matroids and heterogeneous additive valuations, and (iii) at most 3 agents with heterogeneous binary valuations and identical base-orderable matroid constraints.
