|
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. State ... [...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] |
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] |
Weller's Theorem
Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among ''n'' partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency. Moreover, Weller's theorem says that there exists a price such that the allocation and the price are a competitive equilibrium (CE) with equal incomes (EI). Thus, it connects two research fields which were previously unrelated: fair cake-cutting and general equilibrium. Background Fair cake-cutting has been studied since the 1940s. There is a heterogeneous divisible resource, such as a cake or a land-estate. There are ''n'' partners, each of whom has a personal value-density function over the cake. The value of a piece to a partner is the integral of his value-density over that piece (this means that the value is a nonatomic measure over the cake). The envy-free cake-cutting prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lyapunov Vector-measure Theorem
In mathematics, a vector measure is a function defined on a family of sets and taking vector values satisfying certain properties. It is a generalization of the concept of finite measure, which takes nonnegative real values only. Definitions and first consequences Given a field of sets (\Omega, \mathcal F) and a Banach space X, a finitely additive vector measure (or measure, for short) is a function \mu:\mathcal \to X such that for any two disjoint sets A and B in \mathcal one has \mu(A\cup B) =\mu(A) + \mu (B). A vector measure \mu is called countably additive if for any sequence (A_i)_^ of disjoint sets in \mathcal F such that their union is in \mathcal F it holds that \mu = \sum_^\mu(A_i) with the series on the right-hand side convergent in the norm of the Banach space X. It can be proved that an additive vector measure \mu is countably additive if and only if for any sequence (A_i)_^ as above one has where \, \cdot\, is the norm on X. Countably additive vecto ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Leximin
In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division. Definition A vector x = (''x''1, ..., ''x''''n'') is ''leximin-larger'' than a vector y = (''y''1, ..., ''y''''n'') if one of the following holds: * The smallest element of x is larger than the smallest element of y; * The smallest elements of both vectors are equal, and the second-smallest element of x is larger than the second-smallest element of y; * ... * The ''k'' smallest elements of both vectors are equal, and the (''k''+1)-smallest element of x is larger than the (''k''+1)-smallest element of y. Examples The vector (3,5,3) is leximin-larger than (4,2,4), since the smallest element in the former is 3 and in the latter is 2. The vector (4,2,4) is leximin-larger than (5,3,2), since the smallest elements in both are 2, but the second-smallest e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Utilitarian
In ethical philosophy, utilitarianism is a family of normative ethical theories that prescribe actions that maximize happiness and well-being for all affected individuals. Although different varieties of utilitarianism admit different characterizations, the basic idea behind all of them is, in some sense, to maximize utility, which is often defined in terms of well-being or related concepts. For instance, Jeremy Bentham, the founder of utilitarianism, described ''utility'' as: That property in any object, whereby it tends to produce benefit, advantage, pleasure, good, or happiness ... rto prevent the happening of mischief, pain, evil, or unhappiness to the party whose interest is considered. Utilitarianism is a version of consequentialism, which states that the consequences of any action are the only standard of right and wrong. Unlike other forms of consequentialism, such as egoism and altruism, utilitarianism considers the interests of all sentient beings equally. ... [...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-proportional ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Problem Of The Nile
The problem of the Nile is a mathematical problem related to equal partitions of measures. The problem was first presented by Ronald Fisher in 1936–1938. It is presented by Dubins and Spanier in the following words:"Each year, the Nile would flood, thereby irrigating or perhaps devastating parts of the agricultural land of a predynastic Egyptian village. The value of different portions of the land would depend upon the height of the flood. In question was the possibility of giving to each of the ''k'' residents, piece of land whose value would be 1/''k'' of the total land value, no matter what the height of the flood."Formally, for each height ''h'', there is a nonatomic measure ''vh'' on the land, which represents the land values when the height of the Nile is ''h''. In general, there can be infinitely many different heights, and hence, infinitely many different measures. William Feller showed in 1938 that a solution for the general case might not exist. When the number of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exact Division
Exact division, also called consensus division, is a partition of a continuous resource (" 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 should be partition ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lester Dubins
Lester Dubins (April 27, 1920 – February 11, 2010) was an American mathematician noted primarily for his research in probability theory. He was a faculty member at the University of California at Berkeley from 1962 through 2004, and in retirement was Professor Emeritus of Mathematics and Statistics. It has been thought that, since classic red-and-black casino roulette is a game in which the house on average wins more than the gambler, that "bold play", i.e. betting one's whole purse on a single trial, is a uniquely optimal strategy. While a graduate student at the University of Chicago, Dubins surprised his teacher Leonard Jimmie Savage with a mathematical demonstration that this is not true. Dubins and Savage wrote a book that appeared in 1965 titled ''How to Gamble if You Must (Inequalities for Stochastic Processes)'' which presented a mathematical theory of gambling processes and optimal behavior in gambling situations, pointing out their relevance to traditional appro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Set
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment (possibly empty). For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex. The boundary of a convex set is always a convex curve. The intersection of all the convex sets that contain a given subset of Euclidean space is called the convex hull of . It is the smallest convex set containing . A convex function is a real-valued function defined on an interval with the property that its epigraph (the set of points on or above the graph of the function) is a convex set. Convex minimization is a subfield of optimization that studies the problem of minimizing convex functions over convex se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Compact Set
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i.e. that the space not exclude any ''limiting values'' of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval ,1would be compact. Similarly, the space of rational numbers \mathbb is not compact, because it has infinitely many "punctures" corresponding to the irrational numbers, and the space of real numbers \mathbb is not compact either, because it excludes the two limiting values +\infty and -\infty. However, the ''extended'' real number line ''would'' be compact, since it contains both infinities. There are many ways to make this heuristic notion precise. These ways usually agree in a metric space, but may not be equivalent in other topologic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Fair Cake-cutting")
