Individual pieces set

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.

Example

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.

Properties

The 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 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:

History

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]

See also

References

  1. Barbanel, Julius B.; with an introduction by Alan D. Taylor (2005). The geometry of efficient fair division. 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.
This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.