Two's company, three's a crowd: consensus-halving for a constant number of agents
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2022
|
| _version_ | 1826309212845637632 |
|---|---|
| author | Deligkas, A Filos-Ratsikas, A Hollender, A |
| author_facet | Deligkas, A Filos-Ratsikas, A Hollender, A |
| author_sort | Deligkas, A |
| collection | OXFORD |
| description | 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 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. |
| first_indexed | 2024-03-07T07:30:45Z |
| format | Journal article |
| id | oxford-uuid:aaa65e87-5289-40db-8b3f-ef5652a1bd3f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:30:45Z |
| publishDate | 2022 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:aaa65e87-5289-40db-8b3f-ef5652a1bd3f2023-01-18T07:06:42ZTwo's company, three's a crowd: consensus-halving for a constant number of agentsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:aaa65e87-5289-40db-8b3f-ef5652a1bd3fEnglishSymplectic ElementsElsevier2022Deligkas, AFilos-Ratsikas, AHollender, AWe 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 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. |
| spellingShingle | Deligkas, A Filos-Ratsikas, A Hollender, A Two's company, three's a crowd: consensus-halving for a constant number of agents |
| title | Two's company, three's a crowd: consensus-halving for a constant number of agents |
| title_full | Two's company, three's a crowd: consensus-halving for a constant number of agents |
| title_fullStr | Two's company, three's a crowd: consensus-halving for a constant number of agents |
| title_full_unstemmed | Two's company, three's a crowd: consensus-halving for a constant number of agents |
| title_short | Two's company, three's a crowd: consensus-halving for a constant number of agents |
| title_sort | two s company three s a crowd consensus halving for a constant number of agents |
| work_keys_str_mv | AT deligkasa twoscompanythreesacrowdconsensushalvingforaconstantnumberofagents AT filosratsikasa twoscompanythreesacrowdconsensushalvingforaconstantnumberofagents AT hollendera twoscompanythreesacrowdconsensushalvingforaconstantnumberofagents |