Piecewise-constant valuation explained

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.^{[1] [2] [3] [4]}

Formal definition

V: 2 ^{C\to} R . The measure V can be represented by a value-density function v: C\to 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).

Notes and References

1. Book: Aziz. Haris. Ye. Chun. Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations . 2014. Liu. Tie-Yan. Qi. Qi. Ye. Yinyu. Web and Internet Economics. Lecture Notes in Computer Science. 8877. en. Cham. Springer International Publishing. 1–14. 10.1007/978-3-319-13129-0_1. 978-3-319-13129-0. 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 . 10.1609/aaai.v25i1.7874 . 5234366 . en. free.
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. en. 26. 1. 1285–1291. 10.1609/aaai.v26i1.8237 . 13013907 . 2374-3468. free.
4. Menon. Vijay. Larson. Kate. Kate Larson (computer scientist). 2017-05-17. Deterministic, Strategyproof, and Fair Cake Cutting. cs.GT. 1705.06306.