论文标题
两公司，三人的人群：持续数量的代理商共识达成共识
Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents
论文作者
论文摘要
我们考虑$ \ varepsilon $ -consensus-halaving问题，其中一组异质的代理旨在将连续资源分为两个（不一定是连续的）部分，所有这些部分同时认为它们的值大致相同（最高$ \ varepsilon $）。最近，该问题已显示为PPA完整，即使是非常简单的估值功能，也以$ n $ $ n $削减的方式进行了PPA票务。为了了解问题的复杂性的根源，我们考虑了只有恒定代理数量的设置，并且我们考虑了问题的计算复杂性和查询复杂性。 对于具有单调估值功能的药物，我们显示了二分法：对于两个药物，问题是多项式时间可溶可溶剂，而对于三个或多个代理，它变为ppa complete。同样，我们表明，对于两种单调剂，可以通过多项式查询解决问题，而对于三个或多个代理，我们提供了指数的查询复杂性下限。这些结果是通过与单调borsuk-ulam问题的有趣联系来启用的，这可能引起独立的兴趣。对于具有一般估值的代理商，我们表明问题是PPA算法，即使对于两个代理，也可以接受指数的查询复杂性下限。
We consider the $\varepsilon$-Consensus-Halving problem, in which a set of heterogeneous agents aim at dividing a continuous resource into two (not necessarily contiguous) portions that all of them simultaneously consider to be of approximately the same value (up to $\varepsilon$). This problem was recently shown to be PPA-complete, for $n$ agents and $n$ cuts, even for very simple valuation functions. In a quest to understand the root of the complexity of the problem, we consider the setting where there is only a constant number of agents, and we consider both the computational complexity and the query complexity of the problem. For agents with monotone valuation functions, we show a dichotomy: for two agents the problem is polynomial-time solvable, whereas for three or more agents it becomes PPA-complete. Similarly, we show that for two monotone agents the problem can be solved with polynomially-many queries, whereas for three or more agents, we provide exponential query complexity lower bounds. These results are enabled via an interesting connection to a monotone Borsuk-Ulam problem, which may be of independent interest. For agents with general valuations, we show that the problem is PPA-complete and admits exponential query complexity lower bounds, even for two agents.
