Consensus Halving for Sets of Items

Paul W. Goldberg (), Alexandros Hollender (), Ayumi Igarashi (), Pasin Manurangsi () and Warut Suksompong ()
Additional contact information
Paul W. Goldberg: Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom
Alexandros Hollender: Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom
Ayumi Igarashi: Principles of Informatics Research Division, National Institute of Informatics, Tokyo 101-8430, Japan
Pasin Manurangsi: Google Research, Mountain View, California 94043
Warut Suksompong: School of Computing, National University of Singapore, Singapore 117417, Singapore

Mathematics of Operations Research, 2022, vol. 47, issue 4, 3357-3379

Abstract: 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.

Keywords: Primary: 91B10; 68Q17; secondary: 68W01; consensus halving; PPAD-hardness; resource allocation (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1249 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:4:p:3357-3379

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().