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.
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.
Geometric properties The IPS is a convex set and a compact set. This follows from the Dubins–Spanier theorems.
With two agents 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)} 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)} 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).
With three or more agents WIth three or more agents, the IPS is not symmetric around its middle point (neither (1/n,...,1/n) nor (1/2,...,1/2)). However, it has a more nuanced "rotational" symmetry property around (1/n,...,1/n).
Fairness properties Each point in the IPS can represent many different allocations. However, some fairness properties are common to all such allocations:
Proportionality: an allocation is proportional iff the coordinates of its IPS point are all at least 1/n; Super-proportionality: an allocation is super-proportional iff the coordinates of its IPS point are all larger than 1/n. When there are two agents, super-proportionality is equivalent to strong-envy-freeness and super-envy-freeness, so these properties too are determined by the IPS point. But when there are three or more agents, properties related to envy-freeness cannot be determined by the IPS point alone.
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.
Full individual pieces set The Full Individual Pieces Set (FIPS) is an extension of the IPS: it represents all possible value matrices of cake allocations. Each point in the FIPS is an n-by-n matrix, where element i,j equals the value agent i attributes to the piece of agent j. A point in the FIPS determines both proportionality properties and envy-freeness properties of the represented allocations, for any number of agents.
See also Radon–Nikodym set
References
