|
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 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. Example Consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations: The utilitarian rule gives each part to the partner with the highest utility. In this case, the utilitarian rule gives the entire chocolate to Alice and the entire Vanilla to George. The maxsum is 13. The utilitarian division is not fair: it is not proportional since George receives less than half the total cake value, and it is not envy-free since George envies Alice. Notation The cake is calle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cardinal Utility
In economics, a cardinal utility function or scale is a utility index that preserves preference orderings uniquely up to positive affine transformations. Two utility indices are related by an affine transformation if for the value u(x_i) of one index ''u'', occurring at any quantity x_i of the goods bundle being evaluated, the corresponding value v(x_i) of the other index ''v'' satisfies a relationship of the form :v(x_i) = au(x_i) + b\!, for fixed constants ''a'' and ''b''. Thus the utility functions themselves are related by :v(x) = au(x) + b. The two indices differ only with respect to scale and origin. Thus if one is concave, so is the other, in which case there is often said to be diminishing marginal utility. Thus the use of cardinal utility imposes the assumption that levels of absolute satisfaction exist, so that the magnitudes of increments to satisfaction can be compared across different situations. In consumer choice theory, ordinal utility with its weaker assumption ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pareto-efficient Envy-free Division
Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions. Existence of PEEF allocations We assume that each agent has a preference-relation on the set of all bundles of commodities. The preferences are complete, transitive, and closed. Equivalently, each preference relation can be represented by a continuous utility function. Weakly-convex preferences ''Theorem 1 (Varian):'' ''If the preferences of all agents are convex and strongly monotone, then PEEF allocations exist.'' ''Proof'': The proof relies on the existence of a competitive equilibrium with equal incomes. Assume that all resources in an economy are divided equally between the agents. I.e, if the total e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Cake-cutting
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 that he or she believes to be a fair share. The "cake" is only a metaphor; procedures for fair cake-cutting can be used to divide various kinds of resources, such as land estates, advertisement space or broadcast time. The prototypical procedure for fair cake-cutting is divide and choose, which is mentioned already in the book of Genesis. It solves the fair division problem for two people. The modern ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Efficient Cake-cutting
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: * The most common notion is Pareto-efficient, Pareto-efficiency. It means that no other allocation is better for at least one participant and at least as good for everyone. * A weaker notion is non-wastefulness. An allocation is non-wasteful if no agent receives a piece of cake that is worth 0 for him/her, and worth more than 0 for another ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Population Monotonicity
Population monotonicity (PM) is a principle of consistency in allocation problems. It says that, when the set of agents participating in the allocation changes, the utility of all agents should change in the same direction. For example, if the resource is good, and an agent leaves, then all remaining agents should receive at least as much utility as in the original allocation. The term "population monotonicity" is used in an unrelated meaning in the context of apportionment of seats in the congress among states. There, the property relates to the population of an individual state, which determines the state's ''entitlement.'' A population-increase means that a state is entitled to more seats. This different property is described in the page ''state-population monotonicity''. In fair cake cutting In the fair cake-cutting problem, classic allocation rules such as divide and choose are not PM. Several rules are known to be PM: * When the pieces may be ''disconnected'', any function ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Resource Monotonicity
Resource monotonicity (RM; aka aggregate monotonicity) is a principle of fair division. It says that, if there are more resources to share, then all agents should be weakly better off; no agent should lose from the increase in resources. The RM principle has been studied in various division problems. Allocating divisible resources Single homogeneous resource, general utilities Suppose society has m units of some homogeneous divisible resource, such as water or flour. The resource should be divided among n agents with different utilities. The utility of agent i is represented by a function u_i; when agent i receives y_i units of resource, he derives from it a utility of u_i(y_i). Society has to decide how to divide the resource among the agents, i.e, to find a vector y_1,\dots,y_n such that: y_1+\cdots+y_n = m. Two classic allocation rules are the egalitarian rule - aiming to equalize the utilities of all agents (equivalently: maximize the minimum utility), and the utilitari ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proportional Cake-cutting
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. Two assumptions are usually made when proportionality is discussed: * The valuations of the partners are ''non-atomic'', i.e., there are no indivisible elements with positive value. * The valuations of the partners are ''additive'', i.e., when a piece is divided, the value of the piece is equal to the sum of its parts. Formal definitions The cake is denoted by C. There are n people. Each person i has a value function V_i. A partition of the cake, X_1\sqcup \cdots \sqcup X_n = C, is called ''proportional'' if:V_i(X_i) \ge V_i(C)/n for every person i \in \. Procedures For two people, divide and choose is the classic solution. One person divides the resource into what they believe are equal halves, and the other person ch ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Piecewise-uniform Valuation
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 Measure may refer to: * Measurement, the assignment of a number to a characteristic of an object or event Law * Ballot measure, proposed legislation in the United States * Church of England Measure, legislation of the Church of England * Mea ... V: 2^C\to \mathbb. The measure ''V'' can be represented by a ''value-density function' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Equitable Division
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 and : :V_i(X_i) = V_j(X_j) Where: *X_i is the piece of cake allocated to partner ; *V_i is the value measure of partner . It is a real-valued function that, for every piece of cake, returns a number that represents the utility of partner from that piece. Usually these functions are normalized such that V_i(\emptyset)=0 and V_i(EntireCake)=1 for every . See the page on equitability for examples and comparison to other fairness criteria. Finding an equitable cake-cutting for two partners One cut - full revelation When there are 2 partners, it is possible to get an EQ division with a single cut, but it requires full knowledge of the partners' valuations. Assume that the cake ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Piecewise-linear Valuation
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 Measure may refer to: * Measurement, the assignment of a number to a characteristic of an object or event Law * Ballot measure, proposed legislation in the United States * Church of England Measure, legislation of the Church of England * Mea ... V: 2^C\to \mathbb. The measure ''V'' can be represented by a ''value-density function' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the mathematical optimization, optimization of a linear objective function, subject to linear equality and linear inequality Constraint (mathematics), constraints. Its feasible region is a convex polytope, which is a set defined as the intersection (mathematics), intersection of finitely many Half-space (geometry), half spaces, each of which is defined by a linear inequality. Its objective function is a real number, real-valued affine function, affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Fair Cake-cutting")
