|
Fair Pie-cutting
The fair pie-cutting problem is a variation of the fair cake-cutting problem, in which the resource to be divided is circular. As an example, consider a birthday cake shaped as a disk. The cake should be divided among several children such that no child envies another child (as in a standard cake-cutting problem), with the additional constraint that the cuts must be radial, so that each child receives a circular sector. A possible application of the pie model might be for dividing an island’s shoreline into connected lots. Another possible application is in division of periodic time, such as dividing a daily cycle into "on-call" periods. Model A pie is usually modeled as the 1-dimensional interval ,2π(or ,1, in which the two endpoints are identified. This model was introduced in 1985 and later in 1993. Every procedure for fair cake-cutting can also be applied to cutting a pie by just ignoring the fact that the two endpoints are identified. For example, if the cake-cutti ... [...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 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] |
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] |
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] |
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 the closed interval I = ,b/math> ... [...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] |
If And Only If
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both statements are true or both are false. The connective is biconditional (a statement of material equivalence), and can be likened to the standard material conditional ("only if", equal to "if ... then") combined with its reverse ("if"); hence the name. The result is that the truth of either one of the connected statements requires the truth of the other (i.e. either both statements are true, or both are false), though it is controversial whether the connective thus defined is properly rendered by the English "if and only if"—with its pre-existing meaning. For example, ''P if and only if Q'' means that ''P'' is true whenever ''Q'' is true, and the only case in which ''P'' is true is if ''Q'' is also true, whereas in the case of ''P if Q ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Equitable Division
Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners and : :V_i(X_i) = V_j(X_j) Where: *X_i is the piece of cake allocated to partner ; *V_i is the value measure of partner . It is a real-valued function that, for every piece of cake, returns a number that represents the utility of partner from that piece. Usually these functions are normalized such that V_i(\emptyset)=0 and V_i(EntireCake)=1 for every . See the page on equitability for examples and comparison to other fairness criteria. Finding an equitable cake-cutting for two partners One cut - full revelation When there are 2 partners, it is possible to get an EQ division with a single cut, but it requires full knowledge of the partners' valuations. Assume that the cake i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Continuous Function
In mathematics, a continuous function is a function such that a small variation of the argument induces a small variation of the value of the function. This implies there are no abrupt changes in value, known as '' discontinuities''. More precisely, a function is continuous if arbitrarily small changes in its value can be assured by restricting to sufficiently small changes of its argument. A discontinuous function is a function that is . Until the 19th century, mathematicians largely relied on intuitive notions of continuity and considered only continuous functions. The epsilon–delta definition of a limit was introduced to formalize the definition of continuity. Continuity is one of the core concepts of calculus and mathematical analysis, where arguments and values of functions are real and complex numbers. The concept has been generalized to functions between metric spaces and between topological spaces. The latter are the most general continuous functions, and their d ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Disk (mathematics)
In geometry, a disk (Spelling of disc, also spelled disc) is the region in a plane (geometry), plane bounded by a circle. A disk is said to be ''closed'' if it contains the circle that constitutes its boundary, and ''open'' if it does not. For a radius r, an open disk is usually denoted as D_r, and a closed disk is \overline. However in the field of topology the closed disk is usually denoted as D^2, while the open disk is \operatorname D^2. Formulas In Cartesian coordinates, the ''open disk'' with center (a, b) and radius ''R'' is given by the formula D = \, while the ''closed disk'' with the same center and radius is given by \overline = \. The area (geometry), area of a closed or open disk of radius ''R'' is π''R''2 (see area of a disk). Properties The disk has circular symmetry. The open disk and the closed disk are not topologically equivalent (that is, they are not homeomorphism, homeomorphic), as they have different topological properties from each other. For ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Exact Division
Consensus splitting, also called exact 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 ... [...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] |
