|
Adjusted Winner Procedure
Adjusted Winner (AW) is a procedure for envy-free item allocation. Given two agents and some goods, it returns a partition of the goods between the two agents with the following properties: # Envy-freeness: Each agent believes that his share of the goods is at least as good as the other share; # Equitable division, Equitability: The "relative happiness levels" of both agents from their shares are equal; # Pareto-optimality: no other allocation is better for one agent and at least as good for the other agent; # At most one good has to be shared between the agents. For two agents, Adjusted Winner is the only Pareto optimal and equitable procedure that divides at most a single good. The procedure can be used in divorce settlements and partnership dissolutions, as well as international conflicts. The procedure was designed by Steven Brams and Alan D. Taylor. It was first published in their book on fair division and later in a stand-alone book. The algorithm has been commercialized t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Item Allocation
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. Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy. One way to attain fairness is to use monetary transfers; see Fair allocation of items and money. When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations. Finding an envy-free allocation whenever it exists Preference-orderings on bundles: envy-freeness The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nash Equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs. If each player has chosen a strategy an action plan based on what has happened so far in the game and no one can increase one's own expected payoff by changing one's strategy while the other players keep their's unchanged, then the current set of strategy choices constitutes a Nash equilibrium. If two players Alice and Bob choose strategies A and B, (A, B) is a Nash equilibrium if Alice has no other strategy available that does better than A at maximizing her payoff in response to Bob choosing B, and Bob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Division Experiments
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. Case studies Allocating indivisible heirlooms 1. Flood describes a division of a gift containing 5 parcels: whiskey, prunes, eggs, suitcase, etc. The division was done using the Knaster auction. The resulting division was fair, but in retrospect it was found that coalitions could gain from manipulation. 2. When Mary Anna Lee Paine Winsor died at the age of 93, her estate included two trunks of silver, that had to be divided among her 8 grandchildren. It was divided using a decentralized, fair and efficient allocation procedure, which combined market equilibrium and a Vickrey auction. Although most participants did not fully understand the algorithm or the preference information desired, it handled the major considerations well and was regarded as equitable. Allo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Cake-cutting
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. When there are only two partners, the problem is easy and was solved in antiquity by the divide and choose protocol. When there are three or more partners, the problem becomes much more challenging. Two major variants of the problem have been studied: * Connected pieces, e.g. if the cake is a 1-dimensional interval then each partner must receive a single sub-interval. If there are n partners, only n-1 cuts are needed. * General pieces, e.g. if the cake is a 1-dimensional interval then each partner can receive a union of disjoint sub-intervals. Short history Modern research into the fair cake-cutting problem started in the 1940s. The first fairness criterion studied was proportional divi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Brams–Taylor Procedure
The Brams–Taylor procedure (BTP) is a procedure for envy-free cake-cutting. It explicated the first finite procedure to produce an envy-free division of a cake among any positive integer number of players. History In 1988, prior to the discovery of the BTP, Sol Garfunkel contended that the problem solved by the theorem, namely n-person envy-free cake-cutting, was among the most important problems in 20th century mathematics. The BTP was discovered by Steven Brams and Alan D. Taylor. It was first published in the January 1995 issue of American Mathematical Monthly, and later in 1996 in the authors' book. Brams and Taylor hold a joint US patent from 1999 related to the BTP. Description The BTP divides the cake part-by-part. A typical intermediate state of the BTP is as follows: * A part of the cake, say X, is divided in an envy-free way among all partners. * The rest of the cake, say Y, remains undivided, but - * One partner, say Alice, has an Irrevocable Advantage (IA) ... [...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] |
Weller's Theorem
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. Moreover, Weller's theorem says that there exists a price such that the allocation and the price are a competitive equilibrium (CE) with equal incomes (EI). Thus, it connects two research fields which were previously unrelated: fair cake-cutting and general equilibrium. Background Fair cake-cutting has been studied since the 1940s. There is a heterogeneous divisible resource, such as a cake or a land-estate. There are ''n'' partners, each of whom has a personal value-density function over the cake. The value of a piece to a partner is the integral of his value-density over that piece (this means that the value is a nonatomic measure over the cake). The envy-free cake-cutting prob ... [...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] |
Diminishing Marginal Utility
In economics, utility is the satisfaction or benefit derived by consuming a product. The marginal utility of a good or service describes how much pleasure or satisfaction is gained by consumers as a result of the increase or decrease in consumption by one unit. There are three types of marginal utility. They are positive, negative, or zero marginal utility. For instance, you like eating pizza, the second piece of pizza brings you more satisfaction than only eating one piece of pizza. It means your marginal utility from purchasing pizza is positive. However, after eating the second piece you feel full, and you would not feel any better from eating the third piece. This means your marginal utility from eating pizza is zero. Moreover, you might feel sick if you eat more than three pieces of pizza. At this time, your marginal utility is negative. In other words, a negative marginal utility indicates that every unit of goods or service consumed will do more harm than good, which will le ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Additive Utility
In economics, additive utility is a cardinal utility function with the sigma additivity property. Additivity (also called ''linearity'' or ''modularity'') means that "the whole is equal to the sum of its parts." That is, the utility of a set of items is the sum of the utilities of each item separately. Let S be a finite set of items. A cardinal utility function u:2^S\to\R, where 2^S is the power set of S, is additive if for any A, B\subseteq S, :u(A)+u(B)=u(A\cup B)-u(A\cap B). It follows that for any A\subseteq S, :u(A)=u(\emptyset)+\sum_\big(u(\)-u(\emptyset)\big). An additive utility function is characteristic of independent goods. For example, an apple and a hat are considered independent: the utility a person receives from having an apple is the same whether or not he has a hat, and vice versa. A typical utility function for this case is given at the right. Notes * As mentioned above, additivity is a property of cardinal utility functions. An analogous property of ordinal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Truthful Mechanism
In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about what the others do, you fare best or at least not worse by being truthful. SP is also called truthful or dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. An SP game is not always immune to collusion, but its robust variants are; with group strategyproofness no group of people can collude to misreport their preferences in a way that makes every member better off, and with strong group strategyproofness no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off. Examples Typical examples of SP mechanisms are majority voting between two alternatives, second- ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-freeness
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy. General definitions Suppose a certain resource is divided among several agents, such that every agent i receives a share X_i. Every agent i has a personal preference relation \succeq_i over different possible shares. The division is called envy-free (EF) if for all i and j: :::X_i \succeq_i X_j Another term for envy-freeness is no-envy (NE). If the preference of the agents are represented by a value functions V_i, then this definition is equivalent to: :::V_i(X_i) \geq V_i(X_j) Put another way: we say that agent i ''envies'' agent j if i prefers the piece of j over his own piece, i.e.: :::X_i \prec_i X_j :::V_i(X_i) 2 the problem is much harder. See envy-free cake-cutting. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
