Proportional (fair division)

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. The cake can have an irregular structure, for instance a fruit-cake with icing, and the recipients may value the different parts differently. There is no requirement for a division to be envy-free.

There are two main types of solution studied: "discrete" procedures require one person at a time to divide the resource, "moving knife" ones have one or more knives move over the resource and people can choose when to stop them.

The problem generalizes directly to other resources that can be split easily without losing value. The methods adapt easily to similar problems in chore division (dividing up an undesirable resource). Proportional division problems also include dividing a resource where each recipient is entitled to a different proportion. Fair division of indivisible good is however a much harder problem.

Two players

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.

Many players

The problem can be extended to three or more people, but the method for finding an optimum solution becomes complicated.

A simple method, the Successive Pairs Algorithm, [Optimization in Integers and Related Extremal Problems. T.L.Saaty. McGraw-Hill 1970] 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.

An early method due to Banach and Knaster, the Last Diminisher Algorithm, depends on trimming pieces. It 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.

Straightforward algorithms like those above can lead to the resource being divided into a very large number of tiny bits. Straightforward use of the successive pairs algorithm would generate n! pieces, in fact only about n^3/3 are needed as each person only really needs to do n-1 cuts when the nth player comes along. Last diminsher only needs n imes(n-1)/2 cuts. Algorithms using divide and conquer can reduce the number considerably to bring the number of cuts down to about n imeslog_2(n).

The Dubins-Spanier moving knife procedure also achieves proportional division. It was the first example of a continuous procedure in far division. The knife is passed over the cake from one end to the other. A player says stop when they think 1 / n of the cake is to the left of the knife, the cake is cut and they get that piece. Repeat with the remaining cake and players, the last player gets the remainder of the cake. This is similar to the last diminisher procedure and like it can be used to cut the cake into contiguous parts for each player.

Proportional division where the entitlements of he players differ can for rational ratios be handled by treating each player as a number of proxy players each entitled to the same amount.

See also

* Allocative efficiency

References

* Jack Robertson and William Webb (1998). "Cake-Cutting Algorithms: Be Fair If You Can", AK Peters Ltd, . ISBN 1-56881-076-8.
* Steven J. Brams and Alan D. Taylor (1996). "Fair Division - From cake-cutting to dispute resolution" Cambridge University Press. ISBN 0-521-55390-3


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Fair division — Cake cutting redirects here. For the wedding tradition, see Wedding reception#Wedding cake. 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… …   Wikipedia

  • 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. Entitlements can in the main be determined by agreeing on a… …   Wikipedia

  • Proportional representation — (sometimes referred to as full representation, or PR), is a category of electoral formula aiming at a close match between the percentage of votes that groups of candidates (grouped by a certain measure) obtain in elections and the percentage of… …   Wikipedia

  • Partage équitable — En économie, mais aussi en mathématiques, et plus particulièrement en théorie des jeux, le problème du partage équitable, connu aussi sous le nom de problème de partage du gâteau (de l anglais cake cutting problem), est le problème du partage d… …   Wikipédia en Français

  • Proportionality — may refer to:*Proportionality (mathematics), the special mathematical relationships of direct and inverse proportion between two variables *Proportionality (physics) *Proportionality (law), a legal principle under municipal law in which the… …   Wikipedia

  • Voting system — For other uses, see Voting system (disambiguation). Part of the Politics series Electoral methods …   Wikipedia

  • Apportionment paradox — An apportionment paradox exists when the rules for apportionment in a political system produce results which are unexpected or seem to violate common sense. To apportion is to divide into parts according to some rule, the rule typically being one …   Wikipedia

  • Divide and choose — In problems of fair division, divide and choose (also I cut, you choose) is a two party proportional envy free allocation protocol.[1] The protocol also works for dividing an undesirable, as in chore division. In the method, one person divides a… …   Wikipedia

  • LABOR — Jewish Labor Organizations IN THE PRE STATE PERIOD Since the last decades of the 19th century, a number of sporadic labor associations have arisen in agriculture and in the printing, clothing, and building trades, as well as groups limited to a… …   Encyclopedia of Judaism

  • Evolution-Data Optimized — or Evolution Data only, abbreviated as EV DO or EVDO and often EV, is a telecommunications standard for the wireless transmission of data through radio signals, typically for broadband Internet access. It uses multiplexing techniques including… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”