Cake sharing

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. 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 cohesive if 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. 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. 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. In the non-excludable setting, 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. 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.

Mixed divisible and indivisible candidates

Lu, Peters, Aziz, Bei and Suksompong 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374460269 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.