Related Research Articles
Competitive 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.
In mathematics, a submodular set function is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.
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:
A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms and prior-independent mechanisms.
Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients:
A Prior-independent mechanism (PIM) is a mechanism in which the designer knows that the agents' valuations are drawn from some probability distribution, but does not know the distribution.
Bayesian-optimal pricing is a kind of algorithmic pricing in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a Bayesian-optimal mechanism, in which the price is determined in advance without collecting actual buyers' bids.
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.
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.
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:
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
- ↑ Vondrak, Jan (2008-05-17). "Optimal approximation for the submodular welfare problem in the value oracle model". Proceedings of the fortieth annual ACM symposium on Theory of computing. STOC '08. Victoria, British Columbia, Canada: Association for Computing Machinery. pp. 67–74. doi:10.1145/1374376.1374389. ISBN 978-1-60558-047-0. S2CID 170510.
- ↑ Dobzinski, Shahar; Schapira, Michael (2006-01-22). "An improved approximation algorithm for combinatorial auctions with submodular bidders". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. SODA '06. Miami, Florida: Society for Industrial and Applied Mathematics. pp. 1064–1073. doi:10.1145/1109557.1109675. ISBN 978-0-89871-605-4. S2CID 13108913.
- ↑ Feige, Uriel; Vondrák, Jan (2010-12-09). "The Submodular Welfare Problem with Demand Queries". Theory of Computing. 6 (1): 247–290. doi: 10.4086/toc.2010.v006a011 . ISSN 1557-2862.
- ↑ Codenotti, Bruno; McCune, Benton; Varadarajan, Kasturi (2005-05-22). "Market equilibrium via the excess demand function". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. STOC '05. Baltimore, MD, USA: Association for Computing Machinery. pp. 74–83. doi:10.1145/1060590.1060601. ISBN 978-1-58113-960-0. S2CID 15453505.
- ↑ Goldberg, Paul W.; Lock, Edwin; Marmolejo-Cossío, Francisco (2020). Chen, Xujin; Gravin, Nikolai; Hoefer, Martin; Mehta, Ruta (eds.). "Learning Strong Substitutes Demand via Queries". Web and Internet Economics. Lecture Notes in Computer Science. Cham: Springer International Publishing. 12495: 401–415. arXiv: 2005.01496 . doi:10.1007/978-3-030-64946-3_28. ISBN 978-3-030-64946-3. S2CID 218487768.