|
Symmetric Fair Cake-cutting
Symmetric fair cake-cutting is a variant of the fair cake-cutting problem, in which fairness is applied not only to the final outcome, but also to the assignment of roles in the division procedure. As an example, consider a birthday cake that has to be divided between two children with different tastes, such that each child feels that his/her share is "fair", i.e., worth at least 1/2 of the entire cake. They can use the classic divide and choose procedure: Alice cuts the cake into two pieces worth exactly 1/2 in her eyes, and George chooses the piece that he considers more valuable. The outcome is always fair. However, the procedure is not symmetric: while Alice always gets a value of exactly 1/2 of her value, George may get much more than 1/2 of his value. Thus, while Alice does not envy George's share, she does envy George's role in the procedure. In contrast, consider the alternative procedure in which Alice and George both make half-marks on the cake, i.e., each of them marks t ... [...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] |
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] |
Aristotle
Aristotle (; grc-gre, Ἀριστοτέλης ''Aristotélēs'', ; 384–322 BC) was a Greek philosopher and polymath during the Classical period in Ancient Greece. Taught by Plato, he was the founder of the Peripatetic school of philosophy within the Lyceum and the wider Aristotelian tradition. His writings cover many subjects including physics, biology, zoology, metaphysics, logic, ethics, aesthetics, poetry, theatre, music, rhetoric, psychology, linguistics, economics, politics, meteorology, geology, and government. Aristotle provided a complex synthesis of the various philosophies existing prior to him. It was above all from his teachings that the West inherited its intellectual lexicon, as well as problems and methods of inquiry. As a result, his philosophy has exerted a unique influence on almost every form of knowledge in the West and it continues to be a subject of contemporary philosophical discussion. Little is known about his life. Aristotle was born in th ... [...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
A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/''n'' of the total. Two assumptions are usually made when proportionality is discussed: * The valuations of the partners are ''non-atomic'', i.e., there are no indivisible elements with positive value. * The valuations of the partners are ''additive'', i.e., when a piece is divided, the value of the piece is equal to the sum of its parts. Formal definitions The cake is denoted by C. There are n people. Each person i has a value function V_i. A partition of the cake, X_1\sqcup \cdots \sqcup X_n = C, is called ''proportional'' if:V_i(X_i) \ge V_i(C)/n for every person i \in \. Procedures For two people, divide and choose is the classic solution. One person divides the resource into what they believe are equal halves, and the other person ch ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deterministic Algorithm
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently. Formally, a deterministic algorithm computes a mathematical function; a function has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output. Formal definition Deterministic algorithms can be defined in terms of a state machine: a ''state'' describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its ''initial state'' or ''start state''. If the machine is deterministic, this means that from this point onwards, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Subgame Perfect Equilibrium
In game theory, a subgame perfect equilibrium (or subgame perfect Nash equilibrium) is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game (i.e. of the subgame), no matter what happened before. Every finite extensive game with perfect recall has a subgame perfect equilibrium. Perfect recall is a term introduced by Harold W. Kuhn in 1953 and ''"equivalent to the assertion that each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves"''. A common method for determining subgame perfect equilibria in the case of a finite game is backward induction. Here one first considers the last actions of the game and determ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proportional Cake-cutting
A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/''n'' of the total. Two assumptions are usually made when proportionality is discussed: * The valuations of the partners are ''non-atomic'', i.e., there are no indivisible elements with positive value. * The valuations of the partners are ''additive'', i.e., when a piece is divided, the value of the piece is equal to the sum of its parts. Formal definitions The cake is denoted by C. There are n people. Each person i has a value function V_i. A partition of the cake, X_1\sqcup \cdots \sqcup X_n = C, is called ''proportional'' if:V_i(X_i) \ge V_i(C)/n for every person i \in \. Procedures For two people, divide and choose is the classic solution. One person divides the resource into what they believe are equal halves, and the other person ch ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lone Divider
The lone divider procedure is a procedure for proportional cake-cutting. It involves a heterogenous 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 divide the cake among them such that each person receives a piece with a value of at least 1/''n'' of the total value according to his own subjective valuation. The procedure was developed by Hugo Steinhaus for ''n'' = 3 people. It was later extended by Harold W. Kuhn to ''n'' > 3, using thFrobenius–Konig theorem A description of the cases ''n'' = 3, ''n'' = 4 appears in and the general case is described in. Description For convenience we normalize the valuations such that the value of the entire cake is ''n'' for all agents. The goal is to give each agent a piece with a value of at least 1. Step 1. One player chosen arbitrarily, called the divider, cuts the cake into ''n'' piec ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V red, each edge has endpoints of differing colors, as is required in the graph coloring problem.. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denoting ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Matching
In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch his "thing" with that of another person. This term has been used in several different contexts. In unweighted bipartite graphs In an unweighted bipartite graph G = (''X''+''Y'', ''E''), an envy-free matching is a matching in which no unmatched vertex in ''X'' is adjacent to a matched vertex in ''Y''. Suppose the vertices of ''X'' represent people, the vertices of ''Y'' represent houses, and an edge between a person ''x'' and a house ''y'' represents the fact that ''x'' is willing to live in ''y''. Then, an EFM is a partial allocation of houses to people such that each house-less person does not envy any person with a house, since he/she does not like any allocated house anyway. Every matching that saturates ''X'' is envy-free, and every empty matching is envy-free. Moreover, if , ''NG''(''X''), ≥ , X ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Fair Cake-cutting")
