Utilitarian cake-cutting
Utilitarian cake-cutting (also called maxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the…
≈ 3 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.
Utilitarian cake-cutting (also called maxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the sum of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule.
Utilitarian cake-cutting is often not "fair"; Hence, utilitarianism is often in conflict with fair cake-cutting. C has to be divided to n disjoint pieces, one piece per partner.
The piece allocated to partner i is called X_i , and C = X_1 \sqcup ... \sqcup X_n . A division X is called utilitarian or utilitarian-maximal or maxsum if it maximizes the following expression: \sum_{i=1}^{n}{V_i(X_i)} The concept is often generalized by assigning a different weight to each partner. A division X is called weighted-utilitarian-maximal (WUM) if it maximizes the following expression: \sum_{i=1}^{n}\frac{V_i(X_i)}{w_i} where the w_i are given positive constants.
When the cake is 1-dimensional and the pieces must be connected, the simple algorithm of assigning each piece to the agent that values it the most no longer works, even with piecewise-constant valuations. In this case, the problem of finding a UM division is NP-hard, and furthermore no FPTAS is possible unless P=NP.
There is an 8-factor approximation algorithm, and a fixed-parameter tractable algorithm which is exponential in the number of players. For every set of positive weights, a WUM division exists and can be found in a similar way. For 2 partners with piecewise-linear valuations: for each point in the cake, calculate the ratio between the utilities: r=u_1/u_2 .
Give partner 1 the points with r\geq r^* and partner 2 the points with r , where r^* is a threshold calculated so that the division is envy-free. In general r^* cannot be calculated because it might be irrational, but in practice, when the valuations are piecewise-linear, r^* can be approximated by an "irrational search" approximation algorithm.
For any \epsilon > 0 , The algorithm find an allocation that is \epsilon -EF (the value of each agent is at least the value of each other agent minus \epsilon ), and attains a sum that is at least the maximum sum of an EF allocation. Its run-time is polynomial in the input and in \log(1/\epsilon) .
For n partners with general valuations: additive approximation to envy and efficiency, based on the piecewise-constant-valuations algorithm.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368754203 under CC BY-SA 4.0; modifications have been made.