|
Fair division, also known as the cake cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received their fair share. The problem is hard because each recipient may have a different measure of value of the resource: in the "cake cutting" version, one recipient may like marzipan, another like cherries, and so on.
For two people there is a simple solution which is commonly employed. This is the so-called divide and choose method. One person divides the resource into what they believe are equal halves, and the other person chooses the "half" they prefer. Thus, the person making the division has an incentive to divide as fairly as possible: for if they do not, they will likely receive an undesirable portion. This solution satisfies the problem's mathematical 'envy-free' requirement. However that term assumes they only work on their own valuation and don't know or consider how the other person values hers. And on the other hand if they don't know how the other values her share the division can be very inefficient in maximising the value for each. In problems of fair division, divide and choose (also I cut, you choose) is a method whereby two people may divide a resource in an envy-free manner. ...
According to Sol Garfunkel, the cake cutting problem had been one of the most important open problems in 20th century mathematics (Ref: Sol Garfunkel. More Equal than Others: Weighted Voting. For All Practical Purposes. COMAP. 1988.), when the most important variant of the problem was finally solved together by Steven Brams and Alan Taylor in 1995. Solomon Sol Garfunkel (born 1943) is a mathematician who has focused his career on mathematics education. ...
Steven J. Brams (born November 28, 1940) is a political scientist and professor at New York University. ...
Alan Dana Taylor is a mathematician who, with Steven Brams, solved the problem of envy-free Fair division for an arbitrary number of people. ...
Many players
The problem can be extended to three or more people, but the method for finding an optimum solution becomes complicated.
One method continues the division to successively smaller "equal" portions. The first person divides the resource into what they believe are equal halves. The second then chooses a half, leaving the remainder for the first person. Each of these two people then divide their respective portions into thirds. The third person picks two of the resulting portions: one from the first person and one from the second person. If there are four people, each of the first three people divides their portions into fourths, and the process continues.
A problem with this approach is that the portions may become reduced to absurdly small sizes.
Another method begins with the first person portioning off 1 / n of the resource (for n people). Each following person then examines the portion in turn, removing a part for themselves if they believe the portion to be larger than 1 / n. The last person to remove part receives the portion. The process continues until the entire resource has been fairly divided.
The problem was one of the big open problems of the twentieth century. People have yet to discover an envy-free and fair cake cutting algorithm for 4 or more poeple. Solutions to one, two, and three people exist, but do not generalize.
Variants Some cake-cutting procedures are discrete, whereby players make cuts with a knife (usually in a sequence of steps). Moving-knife procedures, on the other hand, allow continuous movement and can let players call "stop" at any point. This article is about the tool. ...
In the mathematics of social science, and especially game theory, a moving-knife procedure is a type of solution to the fair division problem. ...
A variant of the fair division problem is chore division: this is the "dual" to the cake cutting problem in which an undesirable object is to be distributed amongst the players. The canonical example is a set of chores that the players between them must do. Note that "I cut, you choose" works for chore division. In problems of fair division, a resource (prototypically a cake) is to be divided amongst a finite number of players; the resource is assumed to be desirable, and more is assumed to be better. ...
Other variants include cakes which contain indivisible items (i.e. nuts or berries on the cake) which must be fairly distributed between players (such pieces are referred to as atoms), or the requirement of having connected pieces (i.e. only whole pieces and not fragments are allowed). In topology and related branches of mathematics, a topological space X is said to be disconnected if it is the union of two disjoint nonempty open sets. ...
Limitations The nature of the resource to be divided may affect fair division. The classic example is the tale of the Judgement of Solomon (1 Kings 3:15-28) in which King Solomon proposes to settle a dispute between two women who each claim a child by dividing the child in half. Solomon assumed the actual mother would place a greater value on the child's life than on raising the child and therefore surrender it rather than have it killed. The judgement of Solomon is a metaphorical expression for a decision which destroys the subject matter of a dispute rather than allowing either disputing party to share in it. ...
(Redirected from 1 Kings) The Books of Kings (also known as [The Book of] Kings in Hebrew: Sefer Melachim מלכים) is a part of Judaisms Tanakh, the Hebrew Bible. ...
It has been suggested that Sulayman be merged into this article or section. ...
See also Steven J. Brams (born November 28, 1940) is a political scientist and professor at New York University. ...
Equity is the concept or idea of fairness or justice in economics, particularly in terms of taxation and welfare economics. ...
Just in many usages, including economic ones, may express ethical acceptance of some possible social state(s) against which other possible social states are measured. ...
Game theory is often described as a branch of applied mathematics and economics that studies situations where multiple players make decisions in an attempt to maximize their returns. ...
The Nash Bargaining Game is a simple two player game used to model bargaining interactions. ...
The tragedy of the anticommons occurs when rational individuals (acting separately) collectively waste a given resource by under-utilizing it. ...
The Tragedy of the Commons is a type of social trap, often economic, that involves a conflict over resources between individual interests and the common good. ...
In fair division problems, spite is a phenomenon that occurs when a players value of an allocation decreases when one or more other players valuation increases. ...
In fair division, a set of preferences is weakly additive if the following condition is met: If A is larger than B, and C is larger than D (and pieces A and C do not overlap) then A together with C is preferable to B together with D. Weak additivity...
In problems of fair division, the adjusted winner procedure is used to partition a bundle of goods between two players in such a way as to minimize envy and maximize efficiency and equitability. ...
References - Steven J. Brams and Alan D. Taylor (1995). "An Envy-Free Cake Division Protocol," American Mathematical Monthly, 102, pp.9-19. (JUSTOR)
- Steven J. Brams and Alan D. Taylor (1996). Fair Division - From cake-cutting to dispute resolution Cambridge University Press. ISBN 0-521-55390-3
- Vincent P. Crawford (1987). "fair division," The New Palgrave: A Dictionary of Economics, v. 2, pp. 274-75.
- Jack Robertson and William Webb (1998). Cake-Cutting Algorithms: Be Fair If You Can, AK Peters Ltd, . ISBN 1-56881-076-8.
- Bryan Skyrms (1996). The Evolution of the Social Contract Cambridge University Press. ISBN-13: 9780521555838
- Hal Varian (1987). "fairness," The New Palgrave: A Dictionary of Economics, v. 2, pp. 275-76.
Hal Ronald Varian is a central academic in the economics of information technology and the information economy. ...
External links
| view | Topics in game theory | | Definitions Game theory is often described as a branch of applied mathematics and economics that studies situations where multiple players make decisions in an attempt to maximize their returns. ...
| Normal form game · Extensive form game · Cooperative game · Information set · Preference In game theory, normal form is a way of describing a game. ...
It has been suggested that Game tree be merged into this article or section. ...
A cooperative game is a game where groups of players (coalitions) may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players. ...
In game theory, an information set is a set that, for a particular player, establishes all the possible moves that could have taken place in the game so far, given what that player has observed so far. ...
Preference (or taste) is a concept, used in the social sciences, particularly economics. ...
| | Equilibrium concepts Price of market balance In economics, economic equilibrium is simply a state of the world where economic forces are balanced and in the abscence of external shocks the (equilibrium) values of economic variables will not change. ...
In game theory and economic modelling, a solution concept is a process via which equilibria of a game are identified. ...
| Nash equilibrium · Subgame perfection · Bayesian-Nash · Perfect Bayesian · Trembling hand · Proper equilibrium · Epsilon-equilibrium · Correlated equilibrium · Sequential equilibrium · Quasi-perfect equilibrium · Evolutionarily stable strategy · Risk dominance In game theory, the Nash equilibrium (named after John Forbes Nash, who proposed it) is a kind of solution concept of a game involving two or more players, where no player has anything to gain by changing only his or her own strategy unilaterally. ...
Subgame perfect equilibrium is an economics term used in game theory to describe an equilibrium such that players strategies constitute a Nash equilibrium in every subgame of the original game. ...
In game theory, a Bayesian game is one in which information about characteristics of the other players (i. ...
In game theory, a Bayesian game is one in which information about characteristics of the other players (i. ...
The trembling hand perfection is a notion that eliminates actions of players that are unsafe because they were chosen through a slip of the hand. ...
Proper equilibrium is a refinement of Nash Equilibrium due to Roger B. Myerson. ...
In game theory, an Epsilon-equilibrium is a strategy profile that approximately satisfies the condition of Nash Equilibrium. ...
In game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. ...
Sequential equilibrium is a refinement of Nash Equilibrium for extensive form games due to David M. Kreps and Robert Wilson. ...
Quasi-perfect equilibrium is a refinement of Nash Equilibrium for extensive form games due to Eric van Damme. ...
In game theory, an evolutionarily stable strategy (or ESS; also evolutionary stable strategy) is a strategy which if adopted by a population cannot be invaded by any competing alternative strategy. ...
Risk dominance and payoff dominance are two related refinements of the Nash equilibrium (NE) solution concept in game theory, defined by John Harsanyi and Reinhard Selten. ...
| | Strategies In game theory, a players strategy, in a game or a business situation, is a complete plan of action for whatever situation might arise; this fully determines the players behaviour. ...
| Dominant strategies · Mixed strategy · Tit for tat · Grim trigger · Collusion In game theory, dominance occurs when one strategy is better or worse than another regardless of the strategies of a players opponents. ...
In game theory a mixed strategy is a strategy which chooses randomly between possible moves. ...
Tit for Tat is a highly-effective strategy in game theory for the iterated prisoners dilemma. ...
Grim Trigger is a trigger strategy in game theory for a repeated game, such as an iterated prisoners dilemma. ...
Look up collusion in Wiktionary, the free dictionary. ...
| | Classes of games | Symmetric game · Perfect information · Dynamic game · Repeated game · Signaling game · Cheap talk · Zero-sum game · Mechanism design · Stochastic game · Nontransitive game In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. ...
Perfect information is a term used in economics and game theory to describe a state of complete knowledge about the actions of other players that is instantaneously updated as new information arises. ...
In game theory, a sequential game is a game where one player chooses his action before the others chooses theirs. ...
In game theory, a repeated game (or iterated game) is an extensive form game which consists in some number of repetitions of some base game (called a stage game). ...
Signaling games are dynamic games with two players, the sender (S) and the receiver (R). ...
Cheap Talk is a term used in Game Theory for pre-play communication which carries no cost. ...
Zero-sum describes a situation in which a participants gain (or loss) is exactly balanced by the losses (or gains) of the other participant(s). ...
Mechanism design is a sub-field of game theory. ...
In game theory, a stochastic game is a competitive game with probabilistic transitions played by two players. ...
A non-transitive game is a game for which the various strategies produce one or more loops of preferences. ...
| | Games Game theory studies strategic interaction between individuals in situations called games. ...
| Prisoner's dilemma · Traveler's dilemma · Coordination game · Chicken · Volunteer's dilemma · Dollar auction · Battle of the sexes · Stag hunt · Matching pennies · Ultimatum game · Minority game · Rock, Paper, Scissors · Pirate game · Dictator game · Public goods game · Nash bargaining game · Blotto games · War of attrition Will the two prisoners cooperate to minimize total loss of liberty or will one of them, trusting the other to cooperate, betray him so as to go free? In game theory, the prisoners dilemma (sometimes abbreviated PD) is a type of non-zero-sum game in which two players...
In game theory, the travelers dilemma (sometimes abbreviated TD) is a type of non-zero-sum game in which two players attempt to maximise their own payoff, without any concern for the other players payoff. ...
In game theory, the Nash equilibrium (named after John Nash) is a kind of optimal strategy for games involving two or more players, whereby the players reach an outcome to mutual advantage. ...
For other uses, see Chicken (disambiguation). ...
The Volunteers dilemma game models a situation in which each of N players faces the decision of either making a small sacrifice from which all will benefit or freeriding. ...
On eBay, where an auction has a starting price of $1 ...
The Battle of the Sexes is a two player game used in game theory. ...
In game theory, the Stag Hunt is a game first discussed by Jean-Jacques Rousseau. ...
Matching Pennies is the name for a simple example game used in game theory. ...
The Ultimatum game is an experimental economics game in which two parties interact anonymously and only once, so reciprocation is not an issue. ...
Minority Game is a game proposed by Yi-Cheng Zhang and Damien Challet from the University of Fribourg. ...
Rock, Paper, Scissors chart Listen to this article ( info/dl) This audio file was created from an article revision dated 2006-07-13, and may not reflect subsequent edits to the article. ...
From Howard Pyles Book of Pirates The pirate game is a simple mathematical game. ...
The dictator game is a very simple game in experimental economics, similar to the ultimatum game. ...
The Public goods game is a standard of experimental economics; in the basic game subjects secretly choose how many of their private tokens to put into the public pot. ...
The Nash Bargaining Game is a simple two player game used to model bargaining interactions. ...
Blotto games (or Colonel Blotto games) constitute a class of two-person zero-sum games in which the players are tasked to simultaneously distribute limited resources over several objects, with the gain (or payoff) being equal to the sum of the gains on the individual objects. ...
In game theory the War of attrition is a model of aggression in which two contestants compete for a resource of value V by persisting while accumulating costs at a constant rate c. ...
| | Theorems | Minimax theorem · Purification theorems · Folk theorem · Revelation principle · Arrow's theorem “Minmax†redirects here. ...
In game theory, the purification theorem was contributed by Nobel laurate John Harsanyi in 1973[1]. The theorem aims to justify a puzzling aspect of mixed strategy Nash equilibria: that each player is wholly indifferent amongst each of the actions he puts non-zero weight on, yet he mixes them...
In game theory, folk theorems are a class of theorems which imply that in repeated games, any outcome is a feasible solution concept, if under that outcome the players minimax conditions are satisfied. ...
The revelation principle of economics can be stated as, To any equilibrium of a game of incomplete information, there corresponds an associated revelation mechanism that has an equilibrium where the players truthfully report their types. ...
In voting systems, Arrow’s impossibility theorem, or Arrow’s paradox demonstrates the impossibility of designing a set of rules for social decision making that would meet all of a certain set of criteria. ...
| |
Feeds |
Contact