Related Research Articles
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:
Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:
A sequential auction is an auction in which several items are sold, one after the other, to the same group of potential buyers. In a sequential first-price auction (SAFP), each individual item is sold using a first price auction, while in a sequential second-price auction (SASP), each individual item is sold using a second price auction.
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.
Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is a procedure for fair item assignment. It was developed by Eric Budish.
The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.
Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.
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 parts and taking the part with the minimum value. An allocation of items among 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 ( 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.
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.
Envy-free pricing is a kind of fair item allocation. There is a single seller that owns some items, and a set of buyers who are interested in these items. The buyers have different valuations to the items, and they have a quasilinear utility function; this means that the utility an agent gains from a bundle of items equals the agent's value for the bundle minus the total price of items in the bundle. The seller should determine a price for each item, and sell the items to some of the buyers, such that there is no envy. Two kinds of envy are considered:
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-freeness up to one item (EF1), proportionality up to one item (PROP1), and 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.
In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:
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. Therefore, an egalitarian item allocation is sometimes called a leximin 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.
Online fair division is a class of fair division problems in which the resources, or the people to whom they should be allocated, or both, are not all available when the allocation decision is made. Some situations in which not all resources are available include:
In algorithmic game theory, a branch of both computer science and economics, a demand oracle is a function that, given a price-vector, returns the demand of an agent. It is used by many algorithms related to pricing and optimization in online market. It is usually contrasted with a value oracle, which is a function that, given a set of items, returns the value assigned to them by an agent.
Fair division among groups 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:
Fair allocation of items and money is a class of fair item allocation problems in which, during the allocation process, it is possible to give or take money from some of the participants. Without money, it may be impossible to allocate indivisible items fairly. For example, if there is one item and two people, and the item must be given entirely to one of them, the allocation will be unfair towards the other one. Monetary payments make it possible to attain fairness, as explained below.
The welfare maximization problem is an optimization problem studied in economics and computer science. Its goal is to partition a set of items among agents with different utility functions, such that the welfare – defined as the sum of the agents' utilities – is as high as possible. In other words, the goal is to find an item allocation satisfying the utilitarian rule.
References
- ↑ Devanur, Nikhil R.; Goldner, Kira; Saxena, Raghuvansh R.; Schvartzman, Ariel; Weinberg, S. Matthew (2020-07-13). "Optimal Mechanism Design for Single-Minded Agents". Proceedings of the 21st ACM Conference on Economics and Computation. EC '20. Virtual Event, Hungary: Association for Computing Machinery. pp. 193–256. arXiv: 2002.06329 . doi:10.1145/3391403.3399454. ISBN 978-1-4503-7975-5. S2CID 211132939.
- ↑ Aziz, Haris (2019-12-04). "Strategyproof multi-item exchange under single-minded dichotomous preferences". Autonomous Agents and Multi-Agent Systems. 34 (1): 3. arXiv: 1905.10778 . doi:10.1007/s10458-019-09426-w. ISSN 1573-7454. S2CID 166228454.
- ↑ Brânzei, Simina; Lv, Yuezhou; Mehta, Ruta (2016-07-09). "To give or not to give: fair division for single minded valuations". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 123–129. arXiv: 1602.09088 . ISBN 978-1-57735-770-4.
- ↑ Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva (2004-01-01). "An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents". Internet Mathematics. 1 (2): 129–150. doi: 10.1080/15427951.2004.10129086 . ISSN 1542-7951.
- ↑ Chen, Ning; Deng, Xiaotie; Sun, Xiaoming (2004-12-01). "On complexity of single-minded auction". Journal of Computer and System Sciences. 69 (4): 675–687. doi: 10.1016/j.jcss.2004.04.012 . ISSN 0022-0000.
- ↑ De Keijzer, Bart; Kyropoulou, Maria; Ventre, Carmine (2020-06-29). Obviously Strategyproof Single-Minded Combinatorial Auctions. Saarbrücken, Germany [online]: Schloss Dagstuhl--Leibniz-Zentrum. doi:10.4230/LIPIcs.ICALP.2020.71. ISBN 978-3-95977-138-2.
- ↑ On profit-maximizing envy-free pricing | Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. 23 January 2005. pp. 1164–1173. ISBN 9780898715859 . Retrieved 2020-01-16.
{{cite book}}:|website=ignored (help) - ↑ Cheung, M.; Swamy, C. (2008-10-01). "Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 35–44. doi:10.1109/FOCS.2008.15. ISBN 978-0-7695-3436-7. S2CID 1318192.