דילוג לניווט ראשי דילוג לחיפוש דילוג לתוכן הראשי

DIVIDING A GRAPHICAL CAKE

פרסום מחקרי: פרסום בכתב עת › מאמר › ביקורת עמיתים

3 ציטוטים ‏(Scopus)

תקציר

We consider the classical cake cutting problem where we wish to fairly divide a heterogeneous resource among interested agents. Work on this subject typically assumes that the cake is represented by an interval. We introduce a generalized setting where the cake is represented by an arbitrary undirected graph, which allows us to model the division of road networks. Unlike in the interval setting, common fairness criteria such as proportionality cannot always be satisfied in graphical cake cutting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with additive valuations, and exhibit a tight guarantee for each graph in the case of two agents. We also study several variants and extensions, including when more than one connected piece per agent is allowed as well as when the item to be divided is undesirable.

שפה מקוריתאנגלית
עמודים (מ-עד)19-54
מספר עמודים36
כתב עתSIAM Journal on Discrete Mathematics
כרך39
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2025

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'DIVIDING A GRAPHICAL CAKE'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי