Consensus Halving for Sets of Items

• 成果类型: Article; Early Access
• 署名作者: Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut
• 署名单位: University of Oxford; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan; Alphabet Inc.; Google Incorporated; National University of Singapore
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1249
• 发表日期: 2022
• 关键词: borsuk-ulam; Envy-freeness; complexity; EXISTENCE; bisection

摘要

Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work shows that, when the resource is represented by an interval, a consensus halving with at most n cuts always exists but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting in which the resource consists of a set of items without a linear ordering. For agents with linear and additively separable utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts and show that n cuts are almost surely necessary when the agents' utilities are randomly generated. On the other hand, we show that, for a simple class of monotonic utilities, the problem already becomes polynomial parity argument, directed version-hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, with which we wish to divide the resource into k parts in possibly unequal ratios and provide some consequences of our results on the problem of computing small agreeable sets.