|
Fair Item Allocation
Fair item allocation is a kind of the fair division problem in which the items to divide are ''discrete'' rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios: * Several heirs want to divide the inherited property, which contains e.g. a house, a car, a piano and several paintings. * Several lecturers want to divide the courses given in their faculty. Each lecturer can teach one or more whole courses. *White elephant gift exchange parties The indivisibility of the items implies that a fair division may not be possible. As an extreme example, if there is only a single item (e.g. a house), it must be given to a single partner, but this is not fair to the other partners. This is in contrast to the fair cake-cutting problem, where the dividend is divisible and a fair division always exists. In some cases, the ind ... [...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 (fair division), 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. There are many different kinds of fair division problems, depending on the nature of goods to divide, the criteria for fairness, the nature of the players and their preferences, and other criteria for evaluating the quality of the division. The archetypal fair division algorithm is divide and choose. The research in fair division can be seen as an extension of this procedure to various more complex settings. Description In game theory, fair division is the problem of dividing a set of resources among several people who have an Entitlement (fair division), entitlem ... [...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 (economics), 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 e ... [...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] |
Fisher Market
Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients: * A set of m divisible products with pre-specified supplies (usually normalized such that the supply of each good is 1). * A set of n buyers. * For each buyer i=1,\dots,n, there is a pre-specified monetary budget B_i. Each product j has a price p_j; the prices are determined by methods described below. The price of a ''bundle'' of products is the sum of the prices of the products in the bundle. A bundle is represented by a vector x = x_1,\dots,x_m, where x_j is the quantity of product j. So the price of a bundle x is p(x)=\sum_^m p_j\cdot x_j. A bundle is ''affordable'' for a buyer if the price of that bundle is at most the buyer's budget. I.e, a bundle x is affordable for buyer i if p(x)\leq B_i. Each buyer has a preference relation over bundles, which can be represented by a utility function. The utility function of buyer i is denoted by u_i. The ''demand set'' of a buyer is the se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Picking Sequence
A picking sequence is a protocol for fair item assignment. Suppose ''m'' items have to be divided among ''n'' agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A picking-sequence is a sequence of ''m'' agent-names, where each name determines what agent is the next to pick an item. As an example, suppose 4 items have to be divided between Alice and Bob. Some possible picking sequences are: * AABB - Alice picks two items, then Bob picks the two remaining items. * ABAB - Alice picks one item, then Bob picks one item, then Alice again, then Bob again. This is more "fair" than AABB since it lets Bob more chance to get a better item. * ABBA - Alice picks one item, then Bob picks two items, then Alice receives the remaining item. This is intuitively even more "fair" than ABAB, since, in ABAB, Bob is always behind of Alice, while ABBA is more balanced. Advantages A picking-sequence has several merits as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Egalitarian Item Allocation
Egalitarian item allocation, also called max-min item allocation is a fair item allocation problem, in which the fairness criterion follows the egalitarian rule. The goal is to maximize the minimum value of an agent. That is, among all possible allocations, the goal is to find an allocation in which the smallest value of an agent is as large as possible. In case there are two or more allocations with the same smallest value, then the goal is to select, from among these allocations, the one in which the second-smallest value is as large as possible, and so on (by the leximin order). Therefore, an egalitarian item allocation is sometimes called a leximin item allocation. The special case in which the value of each item ''j'' to each agent is either 0 or some constant ''vj'' is called the santa claus problem: santa claus has a fixed set of gifts, and wants to allocate them among children such that the least-happy child is as happy as possible. Some related problems are: * ''Multi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Efficient Approximately Fair Item Allocation
When allocating objects among people with different preferences, two major goals are Pareto efficiency and fairness. Since the objects are indivisible, there may not exist any fair allocation. For example, when there is a single house and two people, every allocation of the house will be unfair to one person. Therefore, several common approximations have been studied, such as ''maximin-share fairness'' (MMS)'', envy-free item allocation, envy-freeness up to one item'' (EF1), ''proportional division, proportionality up to one item'' (PROP1), and Equitable division, equitability up to one item (EQ1). The problem of efficient approximately fair item allocation is to find an allocation that is both Pareto-efficient (PE) and satisfies one of these fairness notions. The problem was first presented at 2016 and has attracted considerable attention since then. Setting There is a finite set of objects, denoted by ''M''. There are ''n'' agents. Each agent ''i'' has a value-function ''Vi'', th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free Item Allocation
Envy-free (EF) item allocation is a fair item allocation problem, in which the fairness criterion is envy-freeness - each agent should receive a bundle that they believe to be at least as good as the bundle of any other agent. Since the items are indivisible, an EF assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will envy. One way to attain fairness is to use monetary transfers. When monetary transfers are not allowed or not desired, there are allocation algorithms providing various kinds of relaxations. Finding an envy-free allocation whenever it exists Preference-orderings on bundles: envy-freeness The undercut procedure finds a complete EF allocation for two agents, if-and-only-if such allocation exists. It requires the agents to rank bundles of items, but it does not require cardinal utility information. It works whenever the agents' preference relations are strictly monot ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
CoNP-complete
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly. Each co-NP-complete problem is the complement of an NP-complete problem. There are some problems in both NP and co-NP, for example all problems in P or integer factorization. However, it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete for more details. Fortune showed in 1979 that if any sparse language is co-NP-complete (or even just co-NP-hard), then , a critical foundation for Mahaney's theorem. Formal definition A decision prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Proportional Item Allocation
Proportional item allocation is a fair item allocation problem, in which the fairness criterion is proportionality - each agent should receive a bundle that they value at least as much as 1/''n'' of the entire allocation, where ''n'' is the number of agents. Since the items are indivisible, a proportional assignment may not exist. The simplest case is when there is a single item and at least two agents: if the item is assigned to one agent, the other will have a value of 0, which is less than 1/2. Therefore, the literature considers various relaxations of the proportionality requirement. Proportional allocation An allocation of objects is called proportional (PROP) if every agent ''i'' values his bundle at least 1/''n'' of the total. Formally, for all ''i'' (where ''M'' is the set of all goods): * V_i(X_i) \geq V_i(M)/n. A proportional division may not exist. For example, if the number of people is larger than the number of items, then some people will get no item at all and t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximin Share
Maximin share (MMS) is a criterion of fair item allocation. Given a set of items with different values, the ''1-out-of-n maximin-share'' is the maximum value that can be gained by partitioning the items into n parts and taking the part with the minimum value. An allocation of items among n agents with different valuations is called MMS-fair if each agent gets a bundle that is at least as good as his/her 1-out-of-''n'' maximin-share. MMS fairness is a relaxation of the criterion of proportionality - each agent gets a bundle that is at least as good as the equal split (1/n of every resource). Proportionality can be guaranteed when the items are divisible, but not when they are indivisible, even if all agents have identical valuations. In contrast, MMS fairness can always be guaranteed to identical agents, so it is a natural alternative to proportionality even when the agents are different. Motivation and examples Identical items. Suppose first that m identical items have to be al ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pareto Efficient
In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves at least one person in society better off without leaving anyone else worse off than they were before. A situation is called Pareto efficient or Pareto optimal if all possible Pareto improvements have already been made; in other words, there are no longer any ways left to make one person better off without making some other person worse-off. In social choice theory, the same concept is sometimes called the unanimity principle, which says that if ''everyone'' in a society ( non-strictly) prefers A to B, society as a whole also non-strictly prefers A to B. The Pareto front consists of all Pareto-efficient situations. In addition to the context of efficiency in ''allocation'', the concept of Pareto efficiency also arises in the context of ''efficiency in production'' vs. '' x-inefficiency'': a set of outputs of go ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
