Piecewise-constant valuation

Last updated

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.

Contents

Piecewise-constant and piecewise-uniform valuations are particularly useful in algorithms for fair cake-cutting. [1] [2] [3] [4]

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).

Related Research Articles

Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inheritance, partnership dissolutions, divorce settlements, electronic frequency allocation, airport traffic management, and exploitation of Earth observation satellites. It is an active research area in mathematics, economics, dispute resolution, etc. The central tenet of fair division is that such a division should be performed by the players themselves, maybe using a mediator but certainly not an arbiter as only the players really know how they value the goods.

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

Exact division, also called consensus division, is a partition of a continuous resource ("cake") into some k pieces, such that each of n people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only the chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division (with k = 3 and n = 2), as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms:

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

Efficient cake-cutting is a problem in economics and computer science. It involves a heterogeneous resource, such as a cake with different toppings or a land with different coverings, that is assumed to be divisible - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be economically efficient. Several notions of efficiency have been studied:

Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners i and j:

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/n of the total.

Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency.

Utilitarian 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.

Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent.

A simultaneous eating algorithm(SE) is an algorithm for allocating divisible objects among agents with ordinal preferences. "Ordinal preferences" means that each agent can rank the items from best to worst, but cannot (or does not want to) specify a numeric value for each item. The SE allocation satisfies SD-efficiency - a weak ordinal variant of Pareto-efficiency (it means that the allocation is Pareto-efficient for at least one vector of additive utility functions consistent with the agents' item rankings).

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

Strategic fair division is the branch of fair division in which the participants are assumed to hide their preferences and act strategically in order to maximize their own utility, rather than playing sincerely according to their true preferences.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query asks an agent to specify a piece of cake with a given value.

Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:

Egalitarian cake-cutting is a kind of fair cake-cutting in which the fairness criterion is the egalitarian rule. The cake represents a continuous resource, that has to be allocated among people with different valuations over parts of the resource. The goal in egalitarian cake-cutting is to maximize the smallest value of an agent; subject to this, maximize the next-smallest value; and so on. It is also called leximin cake-cutting, since the optimization is done using the leximin order on the vectors of utilities.

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

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 [cs.GT].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.