|
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 believed 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 in the book of Book of Genesis, Genesis to resolve Abraham and Lot's conflict. This procedure solves the fa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Wikidata 8th Birth Day Cake Cutting Kochi IMG 20201030 181238
Wikidata is a Wiki, collaboratively edited multilingual knowledge graph hosted by the Wikimedia Foundation. It is a common source of open data that Wikimedia projects such as Wikipedia, and anyone else, are able to use under the CC0 public domain license. Wikidata is a wiki powered by the software MediaWiki, including its extension for semi-structured data, the Wikibase. As of early 2025, Wikidata had 1.65 billion item statements (semantic triples). Concept Wikidata is a document-oriented database, focusing on ''items'', which represent any kind of topic, concept, or object. Each item is allocated a unique persistent identifier called its ''QID'', a positive integer prefixed with the upper-case letter "Q". This makes it possible to provide translations of the basic information describing the topic each item covers without favouring any particular language. Some examples of items and their QIDs are , , , , and . Item ''labels'' do not need to be unique. For example, t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lebesgue Measure
In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of higher dimensional Euclidean '-spaces. For lower dimensions or , it coincides with the standard measure of length, area, or volume. In general, it is also called '-dimensional volume, '-volume, hypervolume, or simply volume. It is used throughout real analysis, in particular to define Lebesgue integration. Sets that can be assigned a Lebesgue measure are called Lebesgue-measurable; the measure of the Lebesgue-measurable set A is here denoted by \lambda(A). Henri Lebesgue described this measure in the year 1901 which, a year after, was followed up by his description of the Lebesgue integral. Both were published as part of his dissertation in 1902. Definition For any interval I = ,b/math>, or I = (a, b), in the set \mathbb of real numbers, let \ell(I)= b - a denote its length. For any subset E\subseteq ... [...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 par ... [...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. Stromquist procedure Simpler version In a simpler version of the problem, a division is regarded as "fair" if all people ("players") are satisfied that each has received at least 1/ n (here n = 3) of the cake. For this version, there is a simple and practical solution, attributed by Steinhaus to Banach and Knaster. Procedure for ther simpler version A referee moves a sword from left to right over the cake, hypothetically dividing it into small left piece and a large right pi ... [...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 d ... [...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 or super-fair division) is a kind of a fair division Fair division is the problem in game theory of dividing a set of resources among several people who have an Entitlement (fair division), entitlement to them so that each person receives their due share. The central tenet of fair division is that .... 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 ... [...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 cou ... [...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 A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ... 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 u ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Even–Paz Protocol
The Even–Paz algorithm is an computationally-efficient algorithm for fair cake-cutting. It involves a certain heterogeneous and divisible resource, such as a birthday cake, and n partners with different preferences over different parts of the cake. It allows the n people to achieve a proportional division. History The first published algorithm for proportional division of a cake was the last diminisher algorithm, published in 1948. Its run-time complexity was O(n^2). In 1984, Shimon Even and Azaria Paz published their improved algorithm, whose run-time complexity is only O(n\log n). Description The algorithm uses a divide-and-conquer strategy, it is possible to achieve a proportional division in time O(n\log n). * Each partner is asked to draw a line dividing the cake into a right and left part such that he believes the ratio is \lfloor n/2\rfloor :\lceil n/2\rceil. The cuts are required to be non-intersecting; a simple way to guarantee this is to allow only horizontal l ... [...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 Cake is a flour confection usually made from flour, sugar, and other ingredients and is usually baked. In their oldest forms, cakes were modifications of bread, but cakes now cover a wide range of preparations that can be simple or elabor .... 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 t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Moving-knife Procedure
In the mathematics of social science, and especially game theory, a moving-knife procedure is a type of solution to the fair division problem. "Fair division" is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. The central tenet of fair division is that such a division should be performed by the players themselves, without the need for external arbitration, as only the players themselves really know how they value the goods. The name of the procedure comes from the canonical example of the fair division of a cake using a knife. Examples 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, first described by A.K.Austin as a prelude to his own procedure: * One player moves the knife across the cake, conventionally from left to right. * The cake is cut when ''either'' player ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
