The Complexity of Envy-Free Graph Cutting

被引：0

作者：

Deligkas, Argyrios ^{[1
]}

Eiben, Eduard ^{[1
]}

Ganian, Robert ^{[2
]}

Hamm, Thekla ^{[2
]}

Ordyniak, Sebastian ^{[3
]}

机构：

[1] Royal Holloway Univ London, London, England

[2] TU Wien, Vienna, Austria

[3] Univ Leeds, Leeds, England

来源：

PROCEEDINGS OF THE THIRTY-FIRST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, IJCAI 2022 | 2022年

基金：

英国工程与自然科学研究理事会; 奥地利科学基金会;

关键词：

CAKE; CUT;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We consider the problem of fairly dividing a set of heterogeneous divisible resources among agents with different preferences. We focus on the setting where the resources correspond to the edges of a connected graph, every agent must be assigned a connected piece of this graph, and the fairness notion considered is the classical envy freeness. The problem is NP-complete, and we analyze its complexity with respect to two natural complexity measures: the number of agents and the number of edges in the graph. While the problem remains NP-hard even for instances with 2 agents, we provide a dichotomy characterizing the complexity of the problem when the number of agents is constant based on structural properties of the graph. For the latter case, we design a polynomial-time algorithm when the graph has a constant number of edges.

引用

页码：237 / 243

页数：7

共 32 条

[1] Abebe R, 2017, AAMAS'17: PROCEEDINGS OF THE 16TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS, P281
[2] Aumann Yonatan, 2015, ACM Transactions on Economics and Computation, V3, DOI 10.1145/2781776
[3] Aziz Haris, AAAI
[4] Balkanski E, 2014, AAAI CONF ARTIF INTE, P566
[5] Basu Saugata, 2006, ser. Algorithms and computation in mathematics
[6] Bei XH, 2022, Arxiv, DOI arXiv:1908.05433
[7] Bei XH, 2021, AAAI CONF ARTIF INTE, V35, P5159
[8] Bei XH, 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), P2114
[9] Bei XH, 2017, PROCEEDINGS OF THE TWENTY-SIXTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, P3632
[10] Bei Xiaohui, 2021, AAAI, P5151

← 1 2 3 4 →