|
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] |
Pareto Efficiency
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 (strict inequality, non-strictly) prefers A to B, society as a whole also non-strictly prefers A to B. The Pareto frontier, 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 productive efficiency, ''efficiency in prod ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lorenz Dominant
Lorenz is an originally German name derived from the Roman surname Laurentius, which means "from Laurentum". Given name People with the given name Lorenz include: * Prince Lorenz of Belgium (born 1955), member of the Belgian royal family by his marriage with Princess Astrid of Belgium * Lorenz Böhler (1885–1973), Austrian trauma surgeon * Lorenz Hart (1895–1943), American lyricist, half of the famed Broadway songwriting team Rodgers and Hart * Lorenz Lange (1690–1752), Russian official in Siberia * Lorenz Oken (1779–1851), German naturalist * Lorenz of Werle (1338/40–1393/94), Lord of Werle-Güstrow Surname People with the name surname Lorenz include: * Adolf Lorenz (1854–1946), Austrian surgeon * Alfred Lorenz (1868–1939), Austrian-German musical analyst * Angela Lorenz (born 1965), American artist * Barbara Lorenz, make-up artist * Carl Lorenz (1913–1993), German cyclist * Christian Lorenz (born 1966), German musician * Edward Norton Lorenz (1917–2 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Basis Of A Matroid
In mathematics, a basis of a matroid is a maximal independent set of the matroid—that is, an independent set that is not contained in any other independent set. Examples As an example, consider the matroid over the ground-set R2 (the vectors in the two-dimensional Euclidean plane), with the following independent sets: It has two bases, which are the sets , . These are the only independent sets that are maximal under inclusion. The basis has a specialized name in several specialized kinds of matroids: * In a graphic matroid, where the independent sets are the forests, the bases are called the '' spanning forests'' of the graph. * In a transversal matroid, where the independent sets are endpoints of matchings in a given bipartite graph, the bases are called ''transversals''. * In a linear matroid, where the independent sets are the linearly-independent sets of vectors in a given vector-space, the bases are just called ''bases'' of the vector space. Hence, the concept ... [...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] |
Adjusted Winner Procedure
Adjusted Winner (AW) is an algorithm for envy-free item allocation. Given two parties and some discrete goods, it returns a partition of the goods between the two parties that is: # Envy-free: Each party believes their share of the goods is as good as or better than their opponent's; # Equitable: The "relative happiness levels" of both parties from their shares are equal; # Pareto-optimal: no other allocation is better for one party and still at least as good for the other party; and # Involves splitting at most one good between the parties. It is the only procedure that can satisfy all four properties simultaneously. Despite this, however, there are no accounts of the algorithm actually being used to resolve disputes. The procedure was designed by Steven Brams and Alan D. Taylor, and published in their book on fair division and later in a stand-alone book. Adjusted Winning was previously patented in the United States, but expired in 2016., ''Computer-based method for the f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Envy-free
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] |
First Welfare Theorem
There are two fundamental theorems of welfare economics. The first states that in economic equilibrium, a set of complete markets, with complete information, and in perfect competition, will be Pareto optimal (in the sense that no further exchange would make one person better off without making another worse off). The requirements for perfect competition are these: # There are no externalities and each actor has perfect information. # Firms and consumers take prices as given (no economic actor or group of actors has market power). The theorem is sometimes seen as an analytical confirmation of Adam Smith's "invisible hand" principle, namely that ''competitive markets ensure an efficient allocation of resources''. However, there is no guarantee that the Pareto optimal market outcome is equitative, as there are many possible Pareto efficient allocations of resources differing in their desirability (e.g. one person may own everything and everyone else nothing). The second theorem s ... [...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] |
Competitive Equilibrium
Competitive equilibrium (also called: Walrasian equilibrium) is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated. Definitions A competitive equilibrium (CE) consists of two elements: * A price function P. It takes as argument a vector representing a bundle of commodities, and returns a positive real number that represents its price. Usually the price function is linear - it is represented as a vector of prices, a price for each commodity type. * An allocation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fractionally Pareto Optimal
In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called ''discrete'' if each item is wholly allocated to a single agent; it is called ''fractional'' if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete ''or fractional'' allocation.Barman, S., Krishnamurthy, S. K., & Vaish, R., "Finding Fair and Efficient Allocations", ''EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation'', June 2018. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO. Formal definitions There is a set of ''n'' agents and a set of ''m'' objects. An ''allocation'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pseudo-polynomial Time
In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the ''numeric value'' of the input (the largest integer present in the input)—but not necessarily in the ''length'' of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An NP-complete problem with known pseudo-polynomial time algorithms is called weakly NP-complete. An NP-complete problem is called strongly NP-complete if it is proven that it cannot be solved by a pseudo-polynomial time algorithm unless . The strong/weak kinds of NP-hardness are defined ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Truthful Mechanism
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly- dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private information (e.g. their type or their value to some item), and the strategy space of each player consists of the possible information values (e.g. possible types or values), a truthful mechanism is a game in which revealing the true information is a weakly-dominant strategy for each player. An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. A SP mechanism is immune to manipulations by individual players (but not by coalitions). In contrast, in a group strategyproof mechanism, no group of people can collude to misreport their preferences in a way that makes every member better off. In a strong group strategyproof mechanism, no group of people can c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
