论文标题
在线公平部门的预期结果和操纵
Expected Outcomes and Manipulations in Online Fair Division
论文作者
论文摘要
在线环境中不可分割的商品公平分配的两种简单而有吸引力的机制就像和平衡一样。我们研究了有关这些机制结果的一些基本计算问题。特别是，我们考虑了期望的结果，哪些结果是必要的以及如何计算其确切结果。通常，我们表明，这样的问题更容易计算，而不是平衡。像是防策略，但平衡不是一样，我们还考虑了计算问题，即通过平衡，代理可以计算战略性的竞标来改善其结果。我们证明这个问题通常是棘手的。
Two simple and attractive mechanisms for the fair division of indivisible goods in an online setting are LIKE and BALANCED LIKE. We study some fundamental computational problems concerning the outcomes of these mechanisms. In particular, we consider what expected outcomes are possible, what outcomes are necessary, and how to compute their exact outcomes. In general, we show that such questions are more tractable to compute for LIKE than for BALANCED LIKE. As LIKE is strategy-proof but BALANCED LIKE is not, we also consider the computational problem of how, with BALANCED LIKE, an agent can compute a strategic bid to improve their outcome. We prove that this problem is intractable in general.
