|
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 modern ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cut The Cake (3032677729)
Cut the Cake may refer to: *Cut the Cake (song), "Cut the Cake" (song), a 1975 hit for Average White Band *Cut the Cake (album), ''Cut the Cake'' (album), an album by Average White Band *Cut the Cake (horse), a racehorse who won the New Zealand Derby in 2003 {{disambig ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sigma Additive
In mathematics, an additive set function is a function mapping sets to numbers, with the property that its value on a union of two disjoint sets equals the sum of its values on these sets, namely, \mu(A \cup B) = \mu(A) + \mu(B). If this additivity property holds for any two sets, then it also holds for any finite number of sets, namely, the function value on the union of ''k'' disjoint sets (where ''k'' is a finite number) equals the sum of its values on the sets. Therefore, an additive set function is also called a finitely-additive set function (the terms are equivalent). However, a finitely-additive set function might not have the additivity property for a union of an ''infinite'' number of sets. A σ-additive set function is a function that has the additivity property even for countably infinite many sets, that is, \mu\left(\bigcup_^\infty A_n\right) = \sum_^\infty \mu(A_n). Additivity and sigma-additivity are particularly important properties of measures. They are abstrac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simmons–Su Protocols
The Simmons–Su protocols are several protocols for envy-free division. They are based on Sperner's lemma. The merits of these protocols is that they put few restrictions on the preferences of the partners, and ask the partners only simple queries such as "which piece do you prefer?". Protocols were developed for solving several related problems: Cake cutting In the envy-free cake-cutting problem, a "cake" (a heterogeneous divisible resource) has to be divided among ''n'' partners with different preferences over parts of the cake. The cake has to be divided to ''n'' pieces such that: (a) each partner receives a single connected piece, and (b) each partner believes that his piece is (weakly) better than all other pieces. A protocol for solving this problem was developed by Forest Simmons in 1980, in a correspondence with Michael Starbird. It was first publicized by Francis Su in 1999. Given a cut-set (i.e. a certain partition of the cake to ''n'' pieces), we say that a partne ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stromquist Moving-knives Procedure
The Stromquist moving-knives procedure is a procedure for envy-free cake-cutting among three players. It is named after Walter Stromquist who presented it in 1980. This procedure was the first envy-free moving knife procedure devised for three players. It requires four knives but only two cuts, so each player receives a single connected piece. There is no natural generalization to more than three players which divides the cake without extra cuts. The resulting partition is not necessarily efficient. Procedure A referee moves a sword from left to right over the cake, hypothetically dividing it into small left piece and a large right piece. Each player moves a knife over the right piece, always keeping it parallel to the sword. The players must move their knives in a continuous manner, without making any "jumps".The importance of this continuity is explained here: When any player shouts "cut", the cake is cut by the sword and by whichever of the players' knives happens to be the ... [...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] |
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] |
Super-proportional Division
A strongly-proportional division (sometimes called super-proportional division) is a kind of a fair division. It is a division of resources among ''n'' partners, in which the value received by each partner is strictly more than his/her due share of 1/''n'' of the total value. Formally, in a strongly-proportional division of a resource ''C'' among ''n'' partners, each partner ''i'', with value measure ''Vi'', receives a share ''Xi'' such thatV_i(X_i) > V_i(C)/n.Obviously, a strongly-proportional division does not exist when all partners have the same value measure. The best condition that can ''always'' be guaranteed is V_i(X_i) \geq V_i(C)/n, which is the condition for a plain proportional division. However, one may hope that, when different agents have different valuations, it may be possible to use this fact for the benefit of all players, and give each of them strictly more than their due share. Existence In 1948, Hugo Steinhaus conjectured the existence of a super-proportiona ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hill–Beck Land Division Problem
The following variant of the fair cake-cutting problem was introduced by Ted Hill in 1983. There is a territory ''D'' adjacent to ''n'' countries. Each country values the different subsets of ''D'' differently. The countries would like to divide ''D'' fairly among them, where "fair" means a proportional division. Additionally, ''the share allocated to each country must be connected and adjacent to that country''. This geographic constraint distinguishes this problem from classic fair cake-cutting. Formally, every country ''Ci'' must receive a disjoint piece of ''D'', marked ''Di'', such that a portion of the border between ''Ci'' and ''D'' is contained in the interior of ''Ci ∪ Di''. Impossibility and possibility There are cases in which the problem cannot be solved: # If there is a single point to which two countries assign all their value (e.g. a holy place), then obviously the territory cannot be divided proportionally. To prevent such situations, we assume that all count ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Edmonds–Pruhs Protocol
Edmonds–Pruhs protocol is a protocol for fair cake-cutting. Its goal is to create a partially proportional division of a heterogeneous resource among ''n'' people, such that each person receives a subset of the cake which that person values as at least 1/''an'' of the total, where a\geq 10 is some sufficiently large constant. It is a randomized algorithm whose running time is O(''n'') with probability close to 1. The protocol was developed by Jeff Edmonds and Kirk Pruhs, who later improved it in joint work with Jaisingh Solanki. Motivation A proportional division of a cake can be achieved using the recursive halving algorithm in time O(''n'' log ''n''). Several hardness results show that this run-time is optimal under a wide variety of assumptions. In particular, recursive halving is the fastest possible algorithm for achieving full proportionality when the pieces must be contiguous, and it is the fastest possible deterministic algorithm for achieving even partia ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fink Protocol
The Fink protocol (also known as Successive Pairs or Lone Chooser) is a protocol for proportional division of a cake. Its main advantage is that it can work in an online fashion, without knowing the number of partners in advance. When a new partner joins the party, the existing division is adjusted to give a fair share to the newcomer, with minimal effect on existing partners. Its main disadvantage is that, instead of giving each partner a single connected piece, it gives each partner a large number of "crumbs". Protocol We describe the protocol inductively for an increasing number of partners. When partner #1 enters the party, he just takes the entire cake. His value is thus 1. When partner #2 comes, partner #1 cuts the cake to two pieces that are equal in his eyes. The new partner chooses the piece that is better in his eyes. The value of each partner is thus at least 1/2 (just like in the divide and choose protocol). When partner #3 joins, both partners #1 and #2 cut their ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Fair Cake-cutting")
