Divide and choose
Encyclopedia
In problems of fair division
, divide and choose (also I cut, you choose) is a two-party proportional
envy-free
allocation
protocol. The protocol also works for dividing an undesirable, as in chore division
.
In the method, one person divides a good
or resource
into what he or she believes are equal halves, and the other person chooses the "half" he or she prefers. 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 rule is a concrete application of the veil of ignorance concept. Unlike those for more people, 2 person fair divisions are also automatically envy-free.
Divide and choose assumes the parties have equal entitlements
and wish to decide the division themselves or use mediation
rather than arbitration
. The goods are assumed to be divisible in any way and the values of the parts be additive, but each party may value the bits differently.
The divide and choose method does not guarantee each person gets exactly half the cake by their own valuations, and so is not an exact division
. There is no finite procedure for exact division but it can be done using two moving knives.
that is half vanilla
and half chocolate
. Suppose Bob likes only chocolate, and Carol only vanilla. If Bob is the cutter and he is unaware of Carol's preference, his optimal strategy is to divide the cake so that each half contains an equal amount of chocolate. But then, regardless of Carol's choice, Bob gets only half the chocolate and the allocation is clearly not Pareto efficient. It is entirely possible that Bob, in his ignorance, would put all the vanilla (and some amount of chocolate) in one larger portion, so Carol gets everything she wants while he would receive less than what he could have got by negotiating.
Bob. There is a procedure to solve even this but it is very unstable in the face of a small error in judgement. More practical solutions that can't guarantee optimality but are much better than divide and choose have been devised by Steven Brams
and Alan Taylor
, in particular the adjusted winner procedure
(AW).
In 2006 Steven J. Brams
, Michael A. Jones, and Christian Klamler detailed a new way to cut a cake called the surplus procedure
(SP) that satisfies equitability and so solves the above problem. Both people's subjective valuation of their piece as a proportion of the whole is the same.
Fair division
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 a fair amount...
, divide and choose (also I cut, you choose) is a two-party proportional
Proportional (fair division)
Proportional division or simple fair division is the original and simplest problem in fair division. Fair division problems are also called cake-cutting problems. A proportional division of a cake between N people would ensure each of them got at least 1/N of the cake by their own valuation...
envy-free
Envy-free
In mathematical sociology and especially game theory, envy-free is a property of certain fair division algorithms for a divisible heterogeneous good over which different players may have different preferences....
allocation
Allocative efficiency
Allocative efficiency is a theoretical measure of the benefit or utility derived from a proposed or actual selection in the allocation or allotment of resources....
protocol. The protocol also works for dividing an undesirable, as in chore division
Chore division
In problems of fair division, a resource is to be divided amongst a finite number of players; the resource is assumed to be desirable, and more is assumed to be better...
.
In the method, one person divides a good
Good (economics and accounting)
In economics, a good is something that is intended to satisfy some wants or needs of a consumer and thus has economic utility. It is normally used in the plural form—goods—to denote tangible commodities such as products and materials....
or resource
Factors of production
In economics, factors of production means inputs and finished goods means output. Input determines the quantity of output i.e. output depends upon input. Input is the starting point and output is the end point of production process and such input-output relationship is called a production function...
into what he or she believes are equal halves, and the other person chooses the "half" he or she prefers. 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 rule is a concrete application of the veil of ignorance concept. Unlike those for more people, 2 person fair divisions are also automatically envy-free.
Divide and choose assumes the parties have equal entitlements
Entitlement (fair division)
Entitlement in fair division describes that proportion of the resources or goods to be divided that a player can expect to receive. The idea is based on the normal idea of entitlement...
and wish to decide the division themselves or use mediation
Mediation
Mediation, as used in law, is a form of alternative dispute resolution , a way of resolving disputes between two or more parties. A third party, the mediator, assists the parties to negotiate their own settlement...
rather than arbitration
Arbitration
Arbitration, a form of alternative dispute resolution , is a legal technique for the resolution of disputes outside the courts, where the parties to a dispute refer it to one or more persons , by whose decision they agree to be bound...
. The goods are assumed to be divisible in any way and the values of the parts be additive, but each party may value the bits differently.
The divide and choose method does not guarantee each person gets exactly half the cake by their own valuations, and so is not an exact division
Exact division
In game theory, an exact or even division is a type of fair division where all the players believe everyone received the same amount.There is no finite fair division procedure for exact division of divisible goods. However there are moving knife procedures for two players...
. There is no finite procedure for exact division but it can be done using two moving knives.
Analysis
Analysis of the method becomes more difficult if two players place different values on some subsets of the resource. One commonly used example is a cakeCake
Cake is a form of bread or bread-like food. In its modern forms, it is typically a sweet and enriched baked dessert. In its oldest forms, cakes were normally fried breads or cheesecakes, and normally had a disk shape...
that is half vanilla
Vanilla
Vanilla is a flavoring derived from orchids of the genus Vanilla, primarily from the Mexican species, Flat-leaved Vanilla . The word vanilla derives from the Spanish word "", little pod...
and half chocolate
Chocolate
Chocolate is a raw or processed food produced from the seed of the tropical Theobroma cacao tree. Cacao has been cultivated for at least three millennia in Mexico, Central and South America. Its earliest documented use is around 1100 BC...
. Suppose Bob likes only chocolate, and Carol only vanilla. If Bob is the cutter and he is unaware of Carol's preference, his optimal strategy is to divide the cake so that each half contains an equal amount of chocolate. But then, regardless of Carol's choice, Bob gets only half the chocolate and the allocation is clearly not Pareto efficient. It is entirely possible that Bob, in his ignorance, would put all the vanilla (and some amount of chocolate) in one larger portion, so Carol gets everything she wants while he would receive less than what he could have got by negotiating.
Alternatives
If Bob knew Carol's preference and liked her, he could cut the cake into an all-chocolate piece, and an all-vanilla piece, Carol would choose the vanilla piece, and Bob would get all the chocolate. On the other hand if he doesn't like Carol he can cut the cake into slightly more than half vanilla in one portion and the rest of the vanilla and all the chocolate in the other. Carol might also be motivated to take the portion with the chocolate to spiteSpite
In fair division problems, spite is a phenomenon that occurs when a player's value of an allocation decreases when one or more other players' valuation increases...
Bob. There is a procedure to solve even this but it is very unstable in the face of a small error in judgement. More practical solutions that can't guarantee optimality but are much better than divide and choose have been devised by Steven Brams
Steven Brams
Steven J. Brams is a game theorist and political scientist at the New York University Department of Politics. Brams is best known for using the techniques of game theory and public choice to research voting systems and fair division. He is one of the independent discoverers of approval voting...
and Alan Taylor
Alan D. Taylor
Alan Dana Taylor is a mathematician who, with Steven Brams, solved the problem of envy-free fair division for an arbitrary number of people with the Brams–Taylor procedure.Taylor received his Ph.D...
, in particular the adjusted winner procedure
Adjusted Winner procedure
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...
(AW).
In 2006 Steven J. Brams
Steven Brams
Steven J. Brams is a game theorist and political scientist at the New York University Department of Politics. Brams is best known for using the techniques of game theory and public choice to research voting systems and fair division. He is one of the independent discoverers of approval voting...
, Michael A. Jones, and Christian Klamler detailed a new way to cut a cake called the surplus procedure
Surplus procedure
The surplus procedure is a fair division protocol for dividing goods in a way that achieves proportional equitability. It can be generalized to more than 2 people and is strategyproof. For 3 or more people it is not always possible to achieve a division that is both equitabile and envy-free.The...
(SP) that satisfies equitability and so solves the above problem. Both people's subjective valuation of their piece as a proportion of the whole is the same.
See also
- Pie rulePie ruleThe pie rule, sometimes referred to as the swap rule, is a meta-rule used to balance abstract strategy board games. Its use has been first reported in 1909 for a game from the Mancala family. Among recent games, Hex uses this rule...
- Resource allocationResource allocationResource allocation is used to assign the available resources in an economic way. It is part of resource management. In project management, resource allocation is the scheduling of activities and the resources required by those activities while taking into consideration both the resource...
- Market makerMarket makerA market maker is a company, or an individual, that quotes both a buy and a sell price in a financial instrument or commodity held in inventory, hoping to make a profit on the bid-offer spread, or turn. From a market microstructure theory standpoint, market makers are net sellers of an option to be...
, players in financial markets who offer to either buy or sell at a given price (plus a spread)