Almost Envy-Free Allocations with Connected Bundles. Bilò, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, D., Vinci, C., & Zwicker, W. S. In 10th Innovations in Theoretical Computer Science Conference (ITCS), volume Lipics 124, pages 21, 2019. Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
Almost Envy-Free Allocations with Connected Bundles [link]Paper  doi  abstract   bibtex   
We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.
@inproceedings{bilo_almost_2019,
	abstract = {We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph G. When the items are arranged in a path, we show that EF1 allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. Sperner's lemma can also be used to show that on a path, an EF2 allocation exists for any number of agents. Except for the results using Sperner's lemma, all of our procedures can be implemented by efficient algorithms. Our positive results for paths imply the existence of connected EF1 or EF2 allocations whenever G is traceable, i.e., contains a Hamiltonian path. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.},
	author = {Bil{\`o}, Vittorio and Caragiannis, Ioannis and Flammini, Michele and Igarashi, Ayumi and Monaco, Gianpiero and Peters, Dominik and Vinci, Cosimo and Zwicker, William S.},
	booktitle = {10th {Innovations} in {Theoretical} {Computer} {Science} {Conference} ({ITCS})},
	date-modified = {2021-09-03 10:17:52 +0200},
	doi = {10.4230/LIPIcs.ITCS.2019.14},
	editor = {Avrim Blum},
	isbn = {978-3-95977-095-8},
	pages = {21},
	publisher = {Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
	title = {Almost {Envy}-{Free} {Allocations} with {Connected} {Bundles}},
	url = {https://drops.dagstuhl.de/opus/volltexte/2018/10107/},
	volume = {Lipics 124},
	year = {2019},
	Bdsk-Url-1 = {https://drops.dagstuhl.de/opus/volltexte/2018/10107/},
	Bdsk-Url-2 = {https://doi.org/10.4230/LIPIcs.ITCS.2019.14}}
Downloads: 0
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021