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:
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.
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.
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. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.
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.
In economics and computer science, the house allocation problem is the problem of assigning objects to people with different preferences, such that each person receives exactly one object. The name "house allocation" comes from the main motivating application, which is assigning dormitory houses to students. Other commonly used terms are assignment problem and one-sided matching. When agents already own houses, the problem is often called a housing market. In house allocation problems, it is assumed that monetary transfers are not allowed; the variant in which monetary transfers are allowed is known as rental harmony.
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. Society for Industrial and Applied Mathematics. 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.