This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Individual pieces set" – news · newspapers · books · scholar · JSTOR(April 2017)
In the theory of fair cake-cutting, the individual-pieces set (IPS) is a geometric object that represents all possible utility vectors in cake partitions.
Suppose we have a cake made of four parts. There are two people, Alice and George, with different tastes: each person values the different parts of the cake differently. The table below describes the parts and their values.
Chocolate
Lemon
Vanilla
Cherries
Alice's value
18
9
1
2
George's value
18
0
4
8
The cake can be divided in various ways. Each division (Alice's-piece, George's-piece) yields a different utility vector (Alice's utility, George's utility). The IPS is the set of utility vectors of all possible partitions.
The IPS for the example cake is shown on the right.
With two agents, the IPS is symmetric across the middle point (in this case it is the point (15,15)). Take some int on the IPS. This point comes from some partition. Swap the pieces between Alice and George. Then, Alice's new utility is 30 minus her previous utility, and George's new utility is 30 minus his previous utility, so the symmetric point is also on the IPS.
The top-right boundary of the IPS is the Pareto frontier – it is the set of all Pareto efficient partitions. With two agents, this frontier can be constructed in the following way:
Order the pieces of the cake in ascending order of the marginal-utility ratio (George's utility / Alice's-utility). In the above example, the order would be: Lemon (0), Chocolate (1), Vanilla+Cherries (4).
Start at the point where all cake is given to George (0,30).
Move each piece-of-cake in order from George to Alice; draw a line whose slope is the corresponding utility-ratio.
Finish at the point where all cake is given to Alice (30,0).
Historyedit
The IPS was introduced as part of the Dubins–Spanier theorems and used in the proof of Weller's theorem. The term "Individual Pieces set" was coined by Julius Barbanel.[1]
^Barbanel, Julius B. (2005). The geometry of efficient fair division. Introduction by Alan D. Taylor. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511546679. ISBN0-521-84248-4. MR 2132232. Short summary is available at: Barbanel, J. (2010). "A Geometric Approach to Fair Division". The College Mathematics Journal. 41 (4): 268. doi:10.4169/074683410x510263.
January 01, 1970
individual, pieces, this, article, relies, largely, entirely, single, source, relevant, discussion, found, talk, page, please, help, improve, this, article, introducing, citations, additional, sources, find, sources, news, newspapers, books, scholar, jstor, ap. This article relies largely or entirely on a single source Relevant discussion may be found on the talk page Please help improve this article by introducing citations to additional sources Find sources Individual pieces set news newspapers books scholar JSTOR April 2017 In the theory of fair cake cutting the individual pieces set IPS is a geometric object that represents all possible utility vectors in cake partitions Contents 1 Example 2 Properties 3 History 4 See also 5 ReferencesExample editSuppose we have a cake made of four parts There are two people Alice and George with different tastes each person values the different parts of the cake differently The table below describes the parts and their values nbsp Chocolate Lemon Vanilla Cherries Alice s value 18 9 1 2 George s value 18 0 4 8 The cake can be divided in various ways Each division Alice s piece George s piece yields a different utility vector Alice s utility George s utility The IPS is the set of utility vectors of all possible partitions The IPS for the example cake is shown on the right Properties editThe IPS is a convex set and a compact set This follows from the Dubins Spanier theorems With two agents the IPS is symmetric across the middle point in this case it is the point 15 15 Take some int x y displaystyle x y nbsp on the IPS This point comes from some partition Swap the pieces between Alice and George Then Alice s new utility is 30 minus her previous utility and George s new utility is 30 minus his previous utility so the symmetric point 30 x 30 y displaystyle 30 x 30 y nbsp is also on the IPS The top right boundary of the IPS is the Pareto frontier it is the set of all Pareto efficient partitions With two agents this frontier can be constructed in the following way Order the pieces of the cake in ascending order of the marginal utility ratio George s utility Alice s utility In the above example the order would be Lemon 0 Chocolate 1 Vanilla Cherries 4 Start at the point where all cake is given to George 0 30 Move each piece of cake in order from George to Alice draw a line whose slope is the corresponding utility ratio Finish at the point where all cake is given to Alice 30 0 History editThe IPS was introduced as part of the Dubins Spanier theorems and used in the proof of Weller s theorem The term Individual Pieces set was coined by Julius Barbanel 1 See also editRadon Nikodym setReferences edit Barbanel Julius B 2005 The geometry of efficient fair division Introduction by Alan D Taylor Cambridge Cambridge University Press doi 10 1017 CBO9780511546679 ISBN 0 521 84248 4 MR 2132232 Short summary is available at Barbanel J 2010 A Geometric Approach to Fair Division The College Mathematics Journal 41 4 268 doi 10 4169 074683410x510263 Retrieved from https en wikipedia org w index php title Individual pieces set amp oldid 1189402374, wikipedia, wiki, book, books, library,
