Journal article
Two's company, three's a crowd: consensus-halving for a constant number of agents
- Abstract:
-
We consider the ε-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 ε). 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 const...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Version of record, pdf, 798.5KB)
-
- Publisher copy:
- 10.1016/j.artint.2022.103784
Authors
Bibliographic Details
- Publisher:
- Elsevier Publisher's website
- Journal:
- Artificial Intelligence Journal website
- Volume:
- 313
- Article number:
- 103784
- Publication date:
- 2022-09-09
- Acceptance date:
- 2022-09-07
- DOI:
- ISSN:
-
0004-3702
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
1285572
- Local pid:
- pubs:1285572
- Deposit date:
- 2022-10-19
Terms of use
- Copyright holder:
- Deligkas et al.
- Copyright date:
- 2022
- Rights statement:
- © 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
- Licence:
- CC Attribution (CC BY)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record