论文标题
使用参数整数线性编程的高质量公平分配
High-Multiplicity Fair Allocation Using Parametric Integer Linear Programming
论文作者
论文摘要
使用参数整数线性编程中的见解，我们可以显着改善以前的工作[Proc。 ACM EC 2019]关于高级公平分配。在其中，我们回答了以前的工作中的一个悬而未决的问题，我们证明了寻找不可分割的项目的无嫉妒的帕累托有效分配的问题是固定参数相对于组合参数“代理数量”加上“项目类型的数量”的问题。与此结果相比，我们的中心改进是要打破必须在其中需要一单努性编码相应的效用和多重性值的条件。具体而言，我们表明，在保留固定参数障碍性的同时，这些值可以用二进制编码，从而大大扩展了可行值的范围。
Using insights from parametric integer linear programming, we significantly improve on our previous work [Proc. ACM EC 2019] on high-multiplicity fair allocation. Therein, answering an open question from previous work, we proved that the problem of finding envy-free Pareto-efficient allocations of indivisible items is fixed-parameter tractable with respect to the combined parameter "number of agents" plus "number of item types." Our central improvement, compared to this result, is to break the condition that the corresponding utility and multiplicity values have to be encoded in unary required there. Concretely, we show that, while preserving fixed-parameter tractability, these values can be encoded in binary, thus greatly expanding the range of feasible values.
