论文标题
关于几乎无嫉妒的分配数量
On the Number of Almost Envy-Free Allocations
论文作者
论文摘要
嫉妒是资源分配公平性的标准基准。由于当资源由不可分割的项目组成时，即使有两种代理，也不能总是满足它，因此经常考虑嫉妒的放松嫉妒性（EF1）和嫉妒性（EFX）（EFX）。在两种代理的情况下，我们对满足这些基准的分配的数量建立了紧密的下限。特别是，虽然对于任何数量的项目，虽然可能只有两个EFX分配，但EF1分配的数量始终是项目数量的指数。我们的结果应用了HyperCube上的顶点等级不等式的版本，并有助于解释两个概念之间稳健性的较大差距。
Envy-freeness is a standard benchmark of fairness in resource allocation. Since it cannot always be satisfied when the resource consists of indivisible items even when there are two agents, the relaxations envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) are often considered. We establish tight lower bounds on the number of allocations satisfying each of these benchmarks in the case of two agents. In particular, while there can be as few as two EFX allocations for any number of items, the number of EF1 allocations is always exponential in the number of items. Our results apply a version of the vertex isoperimetric inequality on the hypercube and help explain the large gap in terms of robustness between the two notions.
