Moving-knife procedure
Encyclopedia
In the mathematics
of social science, and especially game theory
, a moving-knife procedure is a type of solution to the fair division
problem. The canonical example is the division of a cake
using a knife
.
The simplest example is a moving-knife equivalent of the I cut, you choose scheme, sometimes known as Austin's moving-knife procedure. One player moves the knife across the cake, conventionally from left to right. The cake is cut when either player calls "stop". If each player calls stop when he or she perceives the knife to be at the 50-50 point, then the first player to call stop will produce an envy-free
division if the caller gets the left piece and the other player gets the right piece. Note that this procedure is not necessarily efficient
.
Generalizing this scheme to more than two players cannot be done by a discrete procedure without sacrificing envy-freeness.
Examples of moving-knife procedures include
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
of social science, and especially game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, a moving-knife procedure is a type of solution to the fair division
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...
problem. The canonical example is the division of a cake
Cake
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...
using a knife
Knife
A knife is a cutting tool with an exposed cutting edge or blade, hand-held or otherwise, with or without a handle. Knives were used at least two-and-a-half million years ago, as evidenced by the Oldowan tools...
.
The simplest example is a moving-knife equivalent of the I cut, you choose scheme, sometimes known as Austin's moving-knife procedure. One player moves the knife across the cake, conventionally from left to right. The cake is cut when either player calls "stop". If each player calls stop when he or she perceives the knife to be at the 50-50 point, then the first player to call stop will produce an 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....
division if the caller gets the left piece and the other player gets the right piece. Note that this procedure is not necessarily efficient
Efficiency (economics)
In economics, the term economic efficiency refers to the use of resources so as to maximize the production of goods and services. An economic system is said to be more efficient than another if it can provide more goods and services for society without using more resources...
.
Generalizing this scheme to more than two players cannot be done by a discrete procedure without sacrificing envy-freeness.
Examples of moving-knife procedures include
- The Stromquist moving-knife procedureStromquist moving-knife procedureIn problems of envy-free division, the Stromquist moving-knife procedure is a moving-knife procedure for three players. It is named after Walter Stromquist who presented it in 1980....
- The Levmore-Cook moving knife procedure
- The Dubins-Spanier moving-knife procedure
- The Webb moving-knife procedure