Misplaced Pages

A piecewise-constant valuation is a kind of a function that represents the utility of an agent over a continuous resource, such as land. It occurs when the resource can be partitioned into a finite number of regions, and in each region, the value-density of the agent is constant. A piecewise-uniform valuation is a piecewise-constant valuation in which the constant is the same in all regions.

Piecewise-constant and piecewise-uniform valuations are particularly useful in algorithms for fair cake-cutting.

Formal definition

There is a resource represented by a set C. There is a valuation over the resource, defined as a continuous measure ${\displaystyle V:2^{C}\to \mathbb {R} }$. The measure V can be represented by a value-density function ${\displaystyle v:C\to \mathbb {R} }$. The value-density function assigns, to each point of the resource, a real value. The measure V of each subset X of C is the integral of v over X.

A valuation V is called piecewise-constant, if the corresponding value-density function v is a piecewise-constant function. In other words: there is a partition of the resource C into finitely many regions, C₁,...,C_k, such that for each j in 1,...,k, the function v inside C_j equals some constant U_j.

A valuation V is called piecewise-uniform if the constant is the same for all regions, that is, for each j in 1,...,k, the function v inside C_j equals some constant U.

Generalization

A piecewise-linear valuation is a generalization of piecewise-constant valuation in which the value-density in each region j is a linear function, a_jx+b_j (piecewise-constant corresponds to the special case in which a_j=0 for all j).

References

1. Aziz, Haris; Ye, Chun (2014). "Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations". In Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 8877. Cham: Springer International Publishing. pp. 1–14. doi:10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0. S2CID 18365892.
2. Cohler, Yuga J.; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2011-08-04). "Optimal Envy-Free Cake Cutting". Twenty-Fifth AAAI Conference on Artificial Intelligence. 25: 626–631. doi:10.1609/aaai.v25i1.7874. S2CID 5234366.
3. Brams, Steven; Feldman, Michal; Lai, John; Morgenstern, Jamie; Procaccia, Ariel (2012). "On Maxsum Fair Cake Divisions". Proceedings of the AAAI Conference on Artificial Intelligence. 26 (1): 1285–1291. doi:10.1609/aaai.v26i1.8237. ISSN 2374-3468. S2CID 13013907.
4. Menon, Vijay; Larson, Kate (2017-05-17). "Deterministic, Strategyproof, and Fair Cake Cutting". arXiv:1705.06306 .

• Utility function types
• Cake-cutting