|
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] |
Fair Division
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. That problem arises in various real-world settings such as division of inheritance, partnership dissolutions, divorce settlements, electronic frequency allocation, airport traffic management, and exploitation of Earth observation satellites. It is an active research area in mathematics, economics (especially social choice theory), dispute resolution, etc. The central tenet of fair division is that such a division should be performed by the players themselves, maybe using a mediator but certainly not an arbiter as only the players really know how they value the goods. The archetypal fair division algorithm is divide and choose. It demonstrates that two agents with different tastes can divide a cake such that each of them believes that he got the best piece. The research in fair division can be seen as an exten ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proportional Division
A proportional division is a kind of fair division in which a resource is divided among ''n'' partners with subjective valuations, giving each partner at least 1/''n'' of the resource by his/her own subjective valuation. Proportionality was the first fairness criterion studied in the literature; hence it is sometimes called "simple fair division". It was first conceived by Steinhaus. Example Consider a land asset that has to be divided among 3 heirs: Alice and Bob who think that it's worth 3 million dollars, and George who thinks that it's worth $4.5M. In a proportional division, Alice receives a land-plot that she believes to be worth at least $1M, Bob receives a land-plot that ''he'' believes to be worth at least $1M (even though Alice may think it is worth less), and George receives a land-plot that he believes to be worth at least $1.5M. Existence A proportional division does not always exist. For example, if the resource contains several indivisible items and the number ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hugo Steinhaus
Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz University in Lwów (now Lviv, Ukraine), where he helped establish what later became known as the Lwów School of Mathematics. He is credited with "discovering" mathematician Stefan Banach, with whom he gave a notable contribution to functional analysis through the Banach–Steinhaus theorem. After World War II Steinhaus played an important part in the establishment of the mathematics department at Wrocław University and in the revival of Polish mathematics from the destruction of the war. Author of around 170 scientific articles and books, Steinhaus has left his legacy and contribution in many branches of mathematics, such as functional analysis, geometry, mathematical logic, and trigonometry. Notably he is regarded as one of the early found ... [...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 modern ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bronisław Knaster
Bronisław Knaster (22 May 1893 – 3 November 1980) was a Polish mathematician; from 1939 a university professor in Lwów and from 1945 in Wrocław. He is known for his work in point-set topology and in particular for his discoveries in 1922 of the hereditarily indecomposable continuum or pseudo-arc and of the Knaster continuum, or buckethandle continuum. Together with his teacher Hugo Steinhaus and his colleague Stefan Banach, he also developed the last diminisher procedure for fair cake cutting. Knaster received his Ph.D. degree from University of Warsaw in 1925, under the supervision of Stefan Mazurkiewicz. See also *Knaster–Tarski theorem *Knaster–Kuratowski fan In topology, a branch of mathematics, the Knaster–Kuratowski fan (named after Polish mathematicians Bronisław Knaster and Kazimierz Kuratowski) is a specific connected topological space with the property that the removal of a single point ... * Knaster's condition References 1893 births 199 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dubins–Spanier Theorems
The Dubins–Spanier theorems are several theorems in the theory of fair cake-cutting. They were published by Lester Dubins and Edwin Spanier in 1961. Although the original motivation for these theorems is fair division, they are in fact general theorems in measure theory. Setting There is a set U, and a set \mathbb which is a sigma-algebra of subsets of U. There are n partners. Every partner i has a personal value measure V_i: \mathbb \to \mathbb. This function determines how much each subset of U is worth to that partner. Let X a partition of U to k measurable sets: U = X_1 \sqcup \cdots \sqcup X_k. Define the matrix M_X as the following n\times k matrix: :M_X ,j= V_i(X_j) This matrix contains the valuations of all players to all pieces of the partition. Let \mathbb be the collection of all such matrices (for the same value measures, the same k, and different partitions): :\mathbb = \ The Dubins–Spanier theorems deal with the topological properties of \mathbb. Stat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Purely Existential Proof
In mathematics, an existence theorem is a theorem which asserts the existence of a certain object. It might be a statement which begins with the phrase " there exist(s)", or it might be a universal statement whose last quantifier is existential (e.g., "for all , , ... there exist(s) ..."). In the formal terms of symbolic logic, an existence theorem is a theorem with a prenex normal form involving the existential quantifier, even though in practice, such theorems are usually stated in standard mathematical language. For example, the statement that the sine function is continuous everywhere, or any theorem written in big O notation, can be considered as theorems which are existential by nature—since the quantification can be found in the definitions of the concepts used. A controversy that goes back to the early twentieth century concerns the issue of purely theoretic existence theorems, that is, theorems which depend on non-constructive foundational material such as the axiom ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Douglas R
Douglas may refer to: People * Douglas (given name) * Douglas (surname) Animals *Douglas (parrot), macaw that starred as the parrot ''Rosalinda'' in Pippi Longstocking *Douglas the camel, a camel in the Confederate Army in the American Civil War Businesses * Douglas Aircraft Company * Douglas (cosmetics), German cosmetics retail chain in Europe * Douglas (motorcycles), British motorcycle manufacturer Peerage and Baronetage * Duke of Douglas * Earl of Douglas, or any holder of the title * Marquess of Douglas, or any holder of the title * Douglas Baronets Peoples * Clan Douglas, a Scottish kindred * Dougla people, West Indians of both African and East Indian heritage Places Australia * Douglas, Queensland, a suburb of Townsville * Douglas, Queensland (Toowoomba Region), a locality * Port Douglas, North Queensland, Australia * Shire of Douglas, in northern Queensland Belize * Douglas, Belize Canada * Douglas, New Brunswick * Douglas Parish, New Brunswick * Douglas, Onta ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Divide 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] |
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] |
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 Envy-freeness
A super-envy-free division is a kind of a fair division. It is a division of resources among ''n'' partners, in which each partner values his/her share at strictly ''more'' than his/her due share of 1/''n'' of the total value, and simultaneously, values the share of every other partner at strictly less than 1/''n''. Formally, in a super-envy-free division of a resource ''C'' among ''n'' partners, each partner ''i'', with value measure ''Vi'', receives a share ''Xi'' such that:V_i(X_i) > V_i(C)/n ~~ \text ~~ \forall j\neq i:V_i(X_j) < V_i(C)/n .This is a strong fairness requirement: it is stronger than both and super-proportionality. Existence Super envy-freeness was introduced by Julius Barbanel in 199 ...[...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Fair Cake-cutting")
