|
Proportional Cake-cutting With Different Entitlements
In the fair cake-cutting problem, the partners often have different entitlements. For example, the resource may belong to two shareholders such that Alice holds 8/13 and George holds 5/13. This leads to the criterion of ''weighted proportionality'' (WPR): there are several weights w_i that sum up to 1, and every partner i should receive at least a fraction w_i of the resource by their own valuation. In contrast, in the simpler proportional cake-cutting setting, the weights are equal: w_i=1/n for all i Several algorithms can be used to find a WPR division. Cloning Suppose all the weights are rational numbers, with common denominator D. So the weights are p_1/D,\dots,p_n/D, with p_1+\cdots+p_n=D. For each player i, create p_i clones with the same value-measure. The total number of clones is D. Find a proportional cake allocation among them. Finally, give each partner i the pieces of his p_i clones. Robertson and Webb show a simpler procedure for two partners: Alice cuts the cake ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fair Cake-cutting
Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible. The division should be ''unanimously'' fair - each person should receive a piece that he or she believes to be a fair share. The "cake" is only a metaphor; procedures for fair cake-cutting can be used to divide various kinds of resources, such as land estates, advertisement space or broadcast time. The prototypical procedure for fair cake-cutting is divide and choose, which is mentioned already in the book of Genesis. It solves the fair division problem for two people. The moder ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proportional Cake-cutting
A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/''n'' of the total. Two assumptions are usually made when proportionality is discussed: * The valuations of the partners are ''non-atomic'', i.e., there are no indivisible elements with positive value. * The valuations of the partners are ''additive'', i.e., when a piece is divided, the value of the piece is equal to the sum of its parts. Formal definitions The cake is denoted by C. There are n people. Each person i has a value function V_i. A partition of the cake, X_1\sqcup \cdots \sqcup X_n = C, is called ''proportional'' if:V_i(X_i) \ge V_i(C)/n for every person i \in \. Procedures For two people, divide and choose is the classic solution. One person divides the resource into what they believe are equal halves, and the other person ch ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ramsey Theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a question of the form: "how big must some structure be to guarantee that a particular property holds?" More specifically, Ron Graham described Ramsey theory as a "branch of combinatorics". Examples A typical result in Ramsey theory starts with some mathematical structure that is then cut into pieces. How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property? This idea can be defined as partition regularity. For example, consider a complete graph of order ''n''; that is, there are ''n'' vertices and each vertex is connected to every other vertex by an edge. A complete graph of order 3 is called a triangle. Now colour each edge either red or blue. How large must ''n'' be i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Euclidean Algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his ''Elements'' (c. 300 BC). It is an example of an ''algorithm'', a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations. The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cut And Choose
Divide and choose (also Cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource ("the cake") and two partners who have different preferences over parts of the cake. The protocol proceeds as follows: one person ("the cutter") cuts the cake into two pieces; the other person ("the chooser") selects one of the pieces; the cutter receives the remaining piece. The procedure has been used since ancient times to divide land, cake and other resources between two parties. Currently, there is an entire field of research, called fair cake-cutting, devoted to various extensions and generalizations of cut-and-choose. History Divide and choose is mentioned in the Bible, in the Book of Genesis (chapter 13). When Abraham and Lot come to the land of Canaan, Abraham suggests that they divide it among them. Then Abraham, coming from the south, divides the land to a "left" (western ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Robertson–Webb Query Model
In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of ''queries'' that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query (also called a Mark query) asks an agent to specify a piece of cake with a given value. Despite the simplicity of the model, many classic cake-cutting algorithms can be described only by these two queries. On the other hand, there are fair cake-cut ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stromquist–Woodall Theorem
The Stromquist–Woodall theorem is a theorem in fair division and measure theory. Informally, it says that, for any cake, for any ''n'' people with different tastes, and for any fraction ''w'', there exists a subset of the cake that all people value at exactly a fraction ''w'' of the total cake value, and it can be cut using at most 2n-2 cuts. The theorem is about a circular 1-dimensional cake (a "pie"). Formally, it can be described as the interval ,1in which the two endpoints are identified. There are ''n'' continuous measures over the cake: V_1,\ldots,V_n; each measure represents the valuations of a different person over subsets of the cake. The theorem says that, for every weight w \in ,1/math>, there is a subset C_w, which all people value at exactly w: : \forall i = 1,\ldots,n: \,\,\,\,\, V_i(C_w)=w, where C_w is a union of at most n-1 intervals. This means that 2n-2 cuts are sufficient for cutting the subset C_w. If the cake is not circular (that is, the endpoints are ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exact Division
Exact division, also called consensus division, is a partition of a continuous resource ("fair cake-cutting, cake") into some ''k'' pieces, such that each of ''n'' people with different tastes agree on the value of each of the pieces. For example, consider a cake which is half chocolate and half vanilla. Alice values only the chocolate and George values only the vanilla. The cake is divided into three pieces: one piece contains 20% of the chocolate and 20% of the vanilla, the second contains 50% of the chocolate and 50% of the vanilla, and the third contains the rest of the cake. This is an exact division (with ''k''=3 and ''n''=2), as both Alice and George value the three pieces as 20%, 50% and 30% respectively. Several common variants and special cases are known by different terms: * Consensus halving – the cake should be partitioned into two pieces (''k''=2), and all agents agree that the pieces have equal values. *Consensus 1/''k''-division, for any constant ''k''>1 - the cake s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Intermediate Value Theorem
In mathematical analysis, the intermediate value theorem states that if f is a continuous function whose domain contains the interval , then it takes on any given value between f(a) and f(b) at some point within the interval. This has two important corollaries: # If a continuous function has values of opposite sign inside an interval, then it has a root in that interval (Bolzano's theorem). # The image of a continuous function over an interval is itself an interval. Motivation This captures an intuitive property of continuous functions over the real numbers: given ''f'' continuous on ,2/math> with the known values f(1) = 3 and f(2) = 5, then the graph of y = f(x) must pass through the horizontal line y = 4 while x moves from 1 to 2. It represents the idea that the graph of a continuous function on a closed interval can be drawn without lifting a pencil from the paper. Theorem The intermediate value theorem states the following: Consider an interval I = ,b/math> of real ... [...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] |
Cake-cutting
Cake-cutting may refer to: * Fair cake-cutting Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ..., a mathematical problem of fairly dividing a heterogenous resource among people with different preferences ** Efficient cake-cutting, a similar division problem in economics and computer science * Wedding-cake cutting, the habit of cutting the wedding cake and distributing it to the guests, as a symbol of fertility {{disambiguation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Fair Cake-cutting")
