In the theory of

fair cake-cutting Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...

, 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. Individual Pieces Set

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 In geometry, a set of points is convex if it contains every line segment between two points in the set. For example, a solid cube (geometry), cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is n ...

and a

compact set In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., i ...

. This follows from the

Dubins–Spanier theorems The Dubins–Spanier theorems are several theorems in the theory of fair cake-cutting. They were published by Lester Dubins and Edwin Spanier in 1961. Although the original motivation for these theorems is fair division, they are in fact general ...

. 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)

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)

is also on the IPS. The top-right boundary of the IPS is the Pareto frontier – it is the set of all

Pareto efficient In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves at least one person in society better off without leaving anyone else worse ...

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

The IPS was introduced as part of the

and used in the proof of

Weller's theorem Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among ''n'' partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a ...

. The term "Individual Pieces set" was coined by Julius Barbanel.

References

{{DEFAULTSORT:Radon-Nikodym set Cake-cutting Measure theory

Example

Properties

History

See also

References