Cake sharing

From Wikipedia, the free encyclopedia

Cake sharing is a problem in social choice theory, in which a group of agents with different preferences has to choose together a subset of a heterogeneous divisible resource, such as time or space. They have a fixed budget, determining the maximum size of the subset that they can choose. Here are two examples.

Time sharing: a group of people would like to have a party of two hours at Sunday. Each person has different preferences about what time the party should be at (e.g. Alice is available between 8:00 to 12:00 and between 16:00 to 20:00, George is available between 10:00 and 17:00, etc.). They have to choose a subset of two hours, from the total available amount of 24 hours.
Space sharing: A group of people would like to build a new settlement of a given fixed size. Each person has different preferences regarding the location. They have to choose a subset of the given size, from the total region available for them.

The problem was introduced by Bei, Lu and Suksompong in 2022--2025.^[1]^[2]

Definitions

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

Relation to multiwinner voting

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

Justified representation

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.

Results

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

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 rule

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.

Related problems

Cake-sharing differs from some closely-related social choice problems.

1. Cake-cutting is another problem involving a heterogeneous divisible resource, such as time or space, and agents with different preferences over the resource. In cake-cutting the entire resource is allocated, and each agent receives his own piece (i.e., each piece is a private good); in cake-sharing only a subset of the resource is allocated, and all agents enjoy the subset together (i.e., it is a public good). There is also an intermediate setting called fair division among groups, in which a resource should be allocated among groups of agents, where each piece of the resource is a public good among the group members, but private w.r.t. the other groups.

2. Multiwinner voting is another problem in which agents with different preferences have to choose together a subset (a committee) that would serve all of them together. As in cake-sharing, the size of the selected subset (the number of members in the committee) is fixed in advance. The difference is that in multiwinner voting the candidates are discrete, whereas in cake-sharing the cake is continuous; effectively, there is a continuum of different candidates. Cake-sharing with piecewise-uniform valuations is the continuous analogue of multiwinner approval voting.

3. Fractional approval voting (also called fair mixing) is a variant of multiwinner voting in which fractions of candidates can be chosen (e.g., if there are three candidates x,y,z, and the committee size is 2, then it is possible to choose 1/3 of x, 2/3 of y, and all of z). The fractions can correspond to the candidates serving part-time, or serving with a certain probability. This problem can be reduced to cake-sharing in the following way.^[3]^: Sec.4 The cake is the interval [0,m], where m is the number of candidates. Each candidate j corresponds to the sub-interval [j-1,j]. A fractional-voting-agent who approves a set of candidates is mapped to a cake-sharing-agent who approves the corresponding set of sub-intervals.

4. Budget-proposal aggregation is a problem in which a fixed budget has to be allocated among several issues. Each agent proposes a different budget-allocation, and the goal is to aggregate all proposals into a single budget-allocation. This problem (when agents' preferences are based on L1 distance) can be reduced to cake-sharing in the following way.^[3]^: Sec.4 The cake is the interval [0,m], where m is the number of issues. Each issue j corresponds to the sub-interval [j-1,j]. A budget-aggregation-agent who wants to allocate x_j to each agent j, is mapped to a cake-sharing-agent who approves, from each interval [j-1,j], the sub-interval [j-1, j-1+x_j].

5. Agreeable subset is another problem in which agents with different preferences have to choose together a subset that would serve all of them together. However, the size of the subset is not fixed in advance; the requirement is that the elected subset is, according to all agents, at least as good as the remaining (non-elected) subset; subject to that, the elected subset should be as small as possible.

Mixed divisible and indivisible candidates

Lu, Peters, Aziz, Bei and Suksompong^[4] extend cake-sharing to settings with mixed divisible and indivisible candidates: there is a set of m indivisible candidates, as well as a cake [0,c]. Their extended setting generalizes both cake-sharing and multiwinner-voting.

The extended definition of EJR, which allows L-cohesive groups with non-integer L, may be unattainable. They define two relaxations:

EJR-M guarantees to any L-cohesive subset of agents, when there is a set of resources of total size exactly L, that at least one agent in the subset receives utility at least L. EJR-M reduces to EJR both in settings with only indivislbe candidates and in settings with only a divisible candidate.
EJR-β (for any real number β) guarantees to any L-cohesive group, that at least one group member receives utility larger than L-β.

They prove that:

For any β<1, EJR-β may be unattainable.
The Nash rule does not satisfy EJR-β for any β.
A rule called Greedy-EJR satisfies EJR-M, but runs in exponential time, and has proportionality degree ~L/2.
A generalization of the method of equal shares satisfies EJR-1 but not EJR-M, but satisfies EJR for divisible-only instances, and has proportionality degree ~L/2.
A generalization of PAV, using an analytic extension to the harmonic series, satisfies EJR-1 but not EJR-M, does not satisfy EJR for divisible-only instances, but has proportionality degree larger than L-1.