We study the problem of allocating indivisible goods among strategic agents. We focus on settings wherein monetary transfers are not available and each agent's private valuation is a submodular function with binary marginals, i.e., the agents' valuations are matroid-rank functions. In this setup, we establish a notable dichotomy between two of the most well-studied fairness notions in discrete fair division; specifically, between envy-freeness up to one good (EF1) and maximin shares (MMS). First, we show that a Pareto-efficient mechanism of Babaioff et al. (2021) is group strategy-proof for finding EF1 allocations, under matroid-rank valuations. The group strategy-proofness guarantee strengthens the result of Babaioff et al. (2021), that establishes truthfulness (individually for each agent) in the same context. Our result also generalizes a work of Halpern et al. (2020), from binary additive valuations to the matroid-rank case. Next, we establish that an analogous positive result cannot be achieved for MMS, even when considering truthfulness on an individual level. Specifically, we prove that, for matroid-rank valuations, there does not exist a truthful mechanism that is index oblivious, Pareto efficient, and maximin fair. For establishing our results, we develop a characterization of truthful mechanisms for matroid-rank functions. This characterization in fact holds for a broader class of valuations (specifically, holds for binary XOS functions) and might be of independent interest.
翻译:我们研究的是在战略代理人之间分配不可分割货物的问题。 我们注重的是无法提供货币转移和每个代理人的私人估值是具有二进制边际的亚模式功能,即代理人的估值是非机械式的功能。 在这种设置中,我们在离散的公平划分中,在两个最受研究最深的公平概念之间建立了显著的二分法;具体地说,在一种良好(EF1)和最大份额(MMS)之间,我们注重的是无法提供货币转移和每个代理人的私人估值是一种二进制机制(2021年)的组合战略,可以用来找到EF1分配,在配机头级估值下进行。集团战略可靠性保证加强了Babaioff等人(2021年)的结果,从而确立了在同一背景下,两个最真实的公平概念(每个代理人都是个人)之间的真实性。我们的结果还概括了Halpern et al. (2020年)的工作,从二进调加价估值到制级(Babilto)案例。 其次,我们确定MMS无法取得类似的积极结果,即使考虑更真实性、更真实性、更真实性、更真实性的机制, 也证明我们可能存在一个真实性的机制。