Translate

giovedì 18 novembre 2021

# gst: apropos of Cake-cutting, the Art of dividing a cake by countably many cuts

<< Cake-cutting is a playful name for the fair division of a heterogeneous, divisible good among agents, a well-studied problem at the intersection of mathematics, economics, and artificial intelligence. The cake-cutting literature is rich and edifying. However, different model assumptions are made in its many papers, in particular regarding the set of allowed pieces of cake that are to be distributed among the agents and regarding the agents' valuation functions by which they measure these pieces. >>️

A simple example proposed by AA  <<  shows that a formal mathematical approach to cake-cutting needs to address questions like:

(o) Are (open, closed, half-open) intervals the only possible pieces of cake? 

(o) Do we allow for finitely many or infinitely many cuts (a “cut” being the split of any subset of [0,1] at a single point)? 

(o) Which properties should a valuation function have, and how does it interact with the family of admissible pieces of cake?  >>

<< Among the questions (AA) have tried to answer are: 

(i) Which subsets of [0,1] should be considered as pieces of cake? Only finite unions of intervals or more general sets? 

(ii) If valuation functions are considered as set-functions as studied in measure theory, should they be σ-additive or only finitely additive? 

(iii) more ...
>>️
AA << have surveyed the existing rich literature on cake-cutting algorithms and have identified the most commonly used choices of sets consisting of what is allowed as pieces of cake. After showing that these five most commonly used sets are distinct from each other, (they) have discussed them in comparison. >>️

Peter Kern, Daniel Neugebauer, et al. Cutting a Cake Is Not Always a "Piece of Cake": A Closer Look at the Foundations of Cake-Cutting Through the Lens of Measure Theory. arXiv: 2111.05402v1 [cs.GT]. Nov 9, 2021. 


keywords: gst, cake, cake-cutting, math.

Nessun commento:

Posta un commento

Nota. Solo i membri di questo blog possono postare un commento.