<div class="csl-bib-body">
<div class="csl-entry">Deligkas, A., Eiben, E., Ganian, R., Hamm, T., & Ordyniak, S. (2022). The Complexity of Envy-Free Graph Cutting. In L. De Raedt (Ed.), <i>Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence</i> (pp. 237–243). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2022/34</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/136181
-
dc.description.abstract
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.
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Agent-based and Multi-agent Systems
en
dc.subject
Resource Allocation
en
dc.subject
Computational Social Choice
en
dc.title
The Complexity of Envy-Free Graph Cutting
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.contributor.affiliation
Royal Holloway University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
Royal Holloway University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
University of Leeds, UK
-
dc.contributor.editoraffiliation
Örebro University, Sweden
-
dc.relation.isbn
978-1-956792-00-3
-
dc.relation.doi
10.24963/ijcai.2022
-
dc.description.startpage
237
-
dc.description.endpage
243
-
dc.relation.grantno
P31336-N35
-
dc.relation.grantno
Y1329-N
-
dc.rights.holder
IJCAI Organization
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
-
tuw.peerreviewed
true
-
tuw.relation.publisher
International Joint Conferences on Artificial Intelligence
-
tuw.project.title
New Frontiers for Parameterized Complexity
-
tuw.project.title
Parameterisierte Analyse in der Künstlichen Intelligenz
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.linking
https://www.ijcai.org/proceedings/2022/video/34
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.24963/ijcai.2022/34
-
dc.identifier.libraryid
AC17204108
-
dc.description.numberOfPages
7
-
tuw.author.orcid
0000-0002-7762-8045
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.editor.orcid
0000-0002-6860-6303
-
tuw.event.name
Thirty-First International Joint Conference on Artificial Intelligence
en
dc.description.sponsorshipexternal
Austrian Science Fund (FWF)
-
dc.description.sponsorshipexternal
EPSRC
-
dc.relation.grantnoexternal
W1255-N23
-
dc.relation.grantnoexternal
EP/V00252X/1
-
tuw.event.startdate
23-07-2022
-
tuw.event.enddate
29-07-2022
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Vienna
-
tuw.event.country
AT
-
tuw.event.presenter
Deligkas, Argyrios
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.value
100
-
item.mimetype
application/pdf
-
item.grantfulltext
open
-
item.fulltext
with Fulltext
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openaccessfulltext
Open Access
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
crisitem.author.dept
Royal Holloway University of London
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.orcid
0000-0002-7762-8045
-
crisitem.author.parentorg
E180 - Fakultät für Informatik
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
