Fair division of graphs and of tangled cakes

dc.WoS.categoriesComputer Science, Software EngineeringOperations Research & Management ScienceMathematics, Applieden_US
dc.authorid0000-0002-8213-3987en_US
dc.contributor.authorIgarashi, Ayumi
dc.contributor.authorZwicker, William S
dc.date.accessioned2023-09-25T07:33:02Z
dc.date.available2023-09-25T07:33:02Z
dc.date.issued2023-04
dc.description.abstractFair division has been studied in both continuous and discrete contexts. One strand of the continuous literature seeks to award each agent with a single connected piece-a subinterval. The analogue for the discrete case corresponds to the fair division of a graph, where allocations must be contiguous so that each bundle of vertices is required to induce a connected subgraph. With envy-freeness up to one item (EF1) as the fairness criterion, however, positive results for three or more agents havemostly been limited to traceable graphs. We introduce tangles as a new context for fair division. A tangle is a more complicated cake-a connected topological space constructed by gluing together several copies of the unit interval [0, 1]-and each single tangle T corresponds in a natural way to an infinite topological class G(T) of graphs, linking envy-free fair division of tangles to EFk fair division of graphs. In addition to the unit interval itself, we show that only five other stringable tangles guarantee the existence of envyfree and connected allocations for arbitrarily many agents, with the corresponding topological classes containing only traceable graphs. Any other tangle T has a bound r on the number of agents for which such allocations necessarily exist, and our Negative Transfer Principle then applies to the graphs in T 's class; for any integer k >= 1, almost all graphs in this class are non-traceable and fail to guarantee EFk contiguous allocations for r + 1 or more agents, even when very strict requirements are placed on the valuation functions for the agents. With bounds on the number of agents, however, we obtain positive results for some non-stringable classes. An elaboration of Stromquist's moving knife procedure shows that the non-stringable lips tangle L guarantees envy-free allocations of connected shares for three agents. We then modify the discrete version of Stromquist's procedure in Bilo et al. (Games Econ Behav 131:197-221, 2022) to show that all graphs in the topological class G(L) (most of which are non-traceable) guarantee EF1 allocations for three agents.en_US
dc.fullTextLevelFull Texten_US
dc.identifier.doi10.1007/s10107-023-01945-5
dc.identifier.issn1436-4646
dc.identifier.issn0025-5610
dc.identifier.scopus2-s2.0-85152529851en_US
dc.identifier.urihttps://hdl.handle.net/11411/5204
dc.identifier.urihttps://doi.org/10.1007/s10107-023-01945-5
dc.identifier.wosWOS:000973627400002en_US
dc.identifier.wosqualityQ1en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.nationalInternationalen_US
dc.numberofauthors2en_US
dc.publisherSPRINGER HEIDELBERGen_US
dc.relation.ispartofMATHEMATICAL PROGRAMMINGen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectFair divisionen_US
dc.subjectCake cuttingen_US
dc.subjectGraphsen_US
dc.subjectTanglesen_US
dc.subjectEnvy-freenessen_US
dc.titleFair division of graphs and of tangled cakes
dc.typeArticle

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Yükleniyor...
Küçük Resim
İsim:
2023WosZwicker.pdf
Boyut:
1.08 MB
Biçim:
Adobe Portable Document Format
Açıklama:
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
license.txt
Boyut:
1.71 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama: