Piecewise-constant valuation
{{Short description|Piece-wise division of objects}}
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.{{Cite book|last1=Aziz|first1=Haris|last2=Ye|first2=Chun|chapter=Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations |date=2014|editor-last=Liu|editor-first=Tie-Yan|editor2-last=Qi|editor2-first=Qi|editor3-last=Ye|editor3-first=Yinyu|title=Web and Internet Economics|chapter-url=|series=Lecture Notes in Computer Science|volume=8877|language=en|location=Cham|publisher=Springer International Publishing|pages=1–14|doi=10.1007/978-3-319-13129-0_1|isbn=978-3-319-13129-0|s2cid=18365892}}{{Cite journal|last1=Cohler|first1=Yuga J.|last2=Lai|first2=John K.|last3=Parkes|first3=David C.|last4=Procaccia|first4=Ariel D.|date=2011-08-04|title=Optimal Envy-Free Cake Cutting|url=https://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/view/3638|journal=Twenty-Fifth AAAI Conference on Artificial Intelligence|volume=25 |pages=626–631 |doi=10.1609/aaai.v25i1.7874 |s2cid=5234366 |language=en|doi-access=free}}{{Cite journal|last1=Brams|first1=Steven|last2=Feldman|first2=Michal|last3=Lai|first3=John|last4=Morgenstern|first4=Jamie|last5=Procaccia|first5=Ariel|date=2012|title=On Maxsum Fair Cake Divisions|url=https://ojs.aaai.org/index.php/AAAI/article/view/8237|journal=Proceedings of the AAAI Conference on Artificial Intelligence|language=en|volume=26|issue=1|pages=1285–1291|doi=10.1609/aaai.v26i1.8237 |s2cid=13013907 |issn=2374-3468|doi-access=free}}{{cite arXiv|last1=Menon|first1=Vijay|last2=Larson|first2=Kate|author2-link=Kate Larson (computer scientist)|date=2017-05-17|title=Deterministic, Strategyproof, and Fair Cake Cutting|class=cs.GT|eprint=1705.06306}}
Formal definition
There is a resource represented by a set C. There is a valuation over the resource, defined as a continuous measure . The measure V can be represented by a value-density function . 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, C1,...,Ck, such that for each j in 1,...,k, the function v inside Cj equals some constant Uj.
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 Cj 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, ajx+bj (piecewise-constant corresponds to the special case in which aj=0 for all j).