|
Fair Division Among Groups
Fair division among groups (or families) is a class of fair division problems, in which the resources are allocated among ''groups'' of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are: * Several siblings inherited some houses from their parents and have to divide them. Each sibling has a family, whose members may have different opinions regarding which house is better. * A partnership is dissolved, and its assets should be divided among the partners. The partners are firms; each firm has several stockholders, who might disagree regarding which asset is more important. *The university management wants to allocate some meeting-rooms among its departments. In each department there are several faculty members, with differing opi ... [...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 Satellite, 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 mediation, mediator but certainly not an arbitration, 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kneser Graph
In graph theory, the Kneser graph (alternatively ) is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956. Examples The Kneser graph is the complete graph on vertices. The Kneser graph is the complement of the line graph of the complete graph on vertices. The Kneser graph is the odd graph ; in particular is the Petersen graph (see top right figure). The Kneser graph , visualized on the right. Properties Basic properties The Kneser graph K(n,k) has \tbinom vertices. Each vertex has exactly \tbinom neighbors. The Kneser graph is vertex transitive and arc transitive. When k=2, the Kneser graph is a strongly regular graph, with parameters ( \tbinom, \tbinom, \tbinom, \tbinom ). However, it is not strongly regular when k>2, as different pairs of nonadjacent vert ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-freeness
Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by any other agent. In other words, no person should feel envy. General definitions Suppose a certain resource is divided among several agents, such that every agent i receives a share X_i. Every agent i has a personal preference relation \succeq_i over different possible shares. The division is called envy-free (EF) if for all i and j: :::X_i \succeq_i X_j Another term for envy-freeness is no-envy (NE). If the preference of the agents are represented by a value functions V_i, then this definition is equivalent to: :::V_i(X_i) \geq V_i(X_j) Put another way: we say that agent i ''envies'' agent j if i prefers the piece of j over his own piece, i.e.: :::X_i \prec_i X_j :::V_i(X_i) 2 the problem is much harder. See envy-free cake-cutting. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pareto-efficient
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engineer and economist, who used the concept in his studies of economic efficiency and income distribution. The following three concepts are closely related: * Given an initial situation, a Pareto improvement is a new situation where some agents will gain, and no agents will lose. * A situation is called Pareto-dominated if there exists a possible Pareto improvement. * A situation is called Pareto-optimal or Pareto-efficient if no change could lead to improved satisfaction for some agent without some other agent losing or, equivalently, if there is no scope for further Pareto improvement. The Pareto front (also called Pareto frontier or Pareto set) is the set of all Pareto-efficient situations. Pareto originally used the word "optimal" for ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group Strategyproof
In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about what the others do, you fare best or at least not worse by being truthful. SP is also called truthful or dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. An SP game is not always immune to collusion, but its robust variants are; with group strategyproofness no group of people can collude to misreport their preferences in a way that makes every member better off, and with strong group strategyproofness no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off. Examples Typical examples of SP mechanisms are majority voting between two alternatives, second ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Leximin Order
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 elem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Egalitarian Rule
In social choice and operations research, the egalitarian rule (also called the max-min rule or the Rawlsian rule) is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the ''minimum utility'' of all individuals in society. It is a formal mathematical representation of the egalitarian philosophy. It also corresponds to John Rawls' principle of maximizing the welfare of the worst-off individual. Definition Let X be a set of possible `states of the world' or `alternatives'. Society wishes to choose a single state from X. For example, in a single-winner election, X may represent the set of candidates; in a resource allocation setting, X may represent all possible allocations. Let I be a finite set, representing a collection of individuals. For each i \in I, let u_i:X\longrightarrow\mathbb be a ''utility function'', describing the amount of happiness an individual ''i'' derives from each possible state. A '' social choice rule' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rental Harmony
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem. In the typical setting, there are n partners who rent together an n-room house for cost fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view to the main road, etc. The following two problems should be solved simultaneously: * (a) Assign a room to each partner, * (b) Determine the amount each partner should pay, such that the sum of payments equals the fixed cost. There are several properties that we would like the assignment to satisfy. * Non-negativity (NN): all prices must be 0 or more: no partner should be paid to get a room. * Envy-freeness (EF): Given a pricing scheme (an assignment of rent to rooms), we say that a partner ''prefers'' a given room if he ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Approval Voting
Approval voting is an electoral system in which voters can select many candidates instead of selecting only one candidate. Description Approval voting ballots show a list of the options of candidates running. Approval voting lets each voter indicate support for one or more candidates. Final tallies show how many votes each candidate received, and the winner is the candidate with the most support. Effect on elections Approval voting advocates Steven Brams and Dudley R. Herschbach predict that approval voting should increase voter participation, prevent minor-party candidates from being spoilers, and reduce negative campaigning. FairVote published a position paper arguing that approval voting has three flaws that undercut it as a method of voting and political vehicle (the group instead advocates for Instant-runoff voting). They argue that it can result in the defeat of a candidate who would win an absolute majority in a plurality election, can allow a candidate to win who ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Round-robin Item Allocation
Round robin is a procedure for fair item allocation. It can be used to allocate several indivisible items among several people, such that the allocation is "almost" envy-free: each agent believes that the bundle he received is at least as good as the bundle of any other agent, when at most one item is removed from the other bundle. In sports, the round-robin procedure is called a draft. Setting There are ''m'' objects to allocate, and ''n'' people ("agents") with equal rights to these objects. Each person has different preferences over the objects. The preferences of an agent are given by a vector of values - a value for each object. It is assumed that the value of a bundle for an agent is the sum of the values of the objects in the bundle (in other words, the agents' valuations are an additive set function on the set of objects). Description The protocol proceeds as follows: # Number the people arbitrarily from 1 to n; # While there are unassigned objects: #* Let each per ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Additive Valuation
In economics, additive utility is a cardinal utility function with the sigma additivity property. Additivity (also called ''linearity'' or ''modularity'') means that "the whole is equal to the sum of its parts." That is, the utility of a set of items is the sum of the utilities of each item separately. Let S be a finite set of items. A cardinal utility function u:2^S\to\R, where 2^S is the power set of S, is additive if for any A, B\subseteq S, :u(A)+u(B)=u(A\cup B)-u(A\cap B). It follows that for any A\subseteq S, :u(A)=u(\emptyset)+\sum_\big(u(\)-u(\emptyset)\big). An additive utility function is characteristic of independent goods. For example, an apple and a hat are considered independent: the utility a person receives from having an apple is the same whether or not he has a hat, and vice versa. A typical utility function for this case is given at the right. Notes * As mentioned above, additivity is a property of cardinal utility functions. An analogous property of ordinal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Truthful Mechanism
In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about what the others do, you fare best or at least not worse by being truthful. SP is also called truthful or dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. An SP game is not always immune to collusion, but its robust variants are; with group strategyproofness no group of people can collude to misreport their preferences in a way that makes every member better off, and with strong group strategyproofness no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off. Examples Typical examples of SP mechanisms are majority voting between two alternatives, second- ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.svg "Click for more on -> Kneser Graph")
