Cake sharing

Summarize Fact Check

There is a resource called a cake, modeled by an interval [0,c], for some c>0. There is a set of agents numbered 1,...,n. Each agent i has a value-density function v_i over the cake. The value of i for a piece of cake W, denoted V_i(W), is the integral of v_i over W (in other words, V_i is a nonatomic measure over the cake).

There is a fixed "budget" b < c. The agents have to collectively choose a subset of [0,c], with a total length of at most b. If subset W is chosen, then each agent i enjoys a utility of V_i(W); this formalizes the fact that W - once chosen - is a public good.

In a variant called the excludable setting, it is possible to exclude some agents from enjoying some parts of the chosen subset. That is, in addition to choosing W, each agent i is allocated a subset W_i of W, and enjoys a utility of V_i(W_i); the W_i need not be disjoint.

In a more general model,^[2]: App.A each part of the cake may have a different cost. Formally, there is a cost-density function over the cake, and the cost of each piece of cake is the integral of the cost-density function over that cake. The goal is to select a piece of cake with a total cost of at most b (in the simple model, the cost of each piece of cake equals its length).

Cake-sharing can be seen as a continuous analogue of multiwinner voting. In multiwinner voting, a group of agents has to choose together some b candidates from a given set of c candidates (where b<c and both are integers); in cake-sharing there is effectively a continuum of candidates, represented by the interval of length c, and the agents have to choose together a subset of a fixed length b (where b<c and both are real numbers).

One of the common goals in multiwinner voting is to choose a committee that guarantees justified representation to cohesive subsets of agents. Generally, a subset of agents is called cohesiveif it is both sufficiently large, and agree on a sufficiently large candidate subset. In the multiwinner voting context, a subset N' is called L-cohesive, for any integer L>0, if |N'| >= L*n/b, and there is a subset of L candidates approved by all agents in N'. In the cake-sharing context, a subset N' is called L-cohesive, for any real L>0, if |N'| >= L*n/b, and there is a cake-subset of length L that is approved by all agents in N. The most common justified representation axioms are:

• Proportional Justified Representation (PJR): for every real L>0, in every L-cohesive group, the length of (union A_i) cap W is at least L.
• Extended Justified Representation (EJR): for every real L>0, in every L-cohesive group, at least one agent has utility at least L (that is, for at least one agent i, the length of A_i cap W is at least L).
• Average Justified Representation (AJR), also called Average Fair Share (AFS): for every real L>0, in every L-cohesive group, the average utility of an agent is at least L.

Clearly, AJR implies EJR, and EJR implies PJR.

Bei, Lu and Suksompong^[2] assume that agents have piecewise-uniform valuations. This means that the value-density of each agent in each point is either 0 or 1. Equivalently, agent i's preferences are represented by a subset A_i of the cake which the agent approves. The utility that agent i derives from a subset W is the length of the intersection of A_i with W. They study two selection rules.

The leximin rule selects a cake-subset based on the egalitarian rule, using lexicographic max-min optimization. There can be several leximin-optimal allocations, but in all of them, all agents have the same utilities,. The leximin rule is truthful in the excludable setting, i.e., if it is possible to block agents from using subsets of W which they did not appove. It can be computed in polynomial time.^[2]: Sec.3 It guarantees to each agent a normalized utility of exactly b/[c*n - b*n + b)] = 1 / [n*(c/b-1) + 1)]. This guarantee is optimal among all rules that are excludably-truthful and position-oblivious.^[2]: Sec.4 In the non-excludable setting, ^[2]: Sec.6 no position-oblivious rule that guarantees a positive utility to all agents is truthful and Pareto efficient.

The leximin rule can be adapted to the model with a non-uniform cost, and the adaptation is still excludable-truthful and has the same minimum-utility guarantee, but it is no longer Pareto efficient.^[2]: App.A

The max Nash welfare (MNW) rule selects a cake-subset based on the proportional-fair rule, maximizing the product of utilities. Equivalently, it maximizes the sum of Log(V_i) Thus, it can be seen as a continuous analog of proportional approval voting (PAV), which maximizes the sum of Harmonic(V_i).

For two agents MNW is equivalent to the leximin rule, but for three or more agents MNW is not truthful even in the excludable setting.

On the positive side, MNW satisfies AJR (hence also EJR and PJR), and it is the only welfare-maximizing rule satisfying any of these properties. This is analogous to the fact that PAV satisfies EJR in multiwinner approval voting, and that PAV is the only Thiele rule satisfying even PJR (PAV also "almost" satisfies AJR, as it guarantees each L-cohesive group an average utility larger than L-1).^[2]: Sec.7

MNW guarantees to each agent a normalized utility of exactly b/[c*n - b*n + b)] = 1 / [n*(c/b-1) + 1)], the same as the leximin rule.