Envy-free pricing

Last updated

Envy-free pricing [1] 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:

Contents

The no-envy conditions guarantee that the market is stable and that the buyers do not resent the seller. By definition, every market envy-free allocation is also agent envy-free, but not vice versa.

There always exists a market envy-free allocation (which is also agent envy-free): if the prices of all items are very high, and no item is sold (all buyers get an empty bundle), then there is no envy, since no agent would like to get any bundle for such high prices. However, such an allocation is very inefficient. The challenge in envy-free pricing is to find envy-free prices that also maximize one of the following objectives:

Envy-free pricing is related, but not identical, to other fair allocation problems:

Results

A Walrasian equilibrium is a market-envy-free pricing with the additional requirement that all items with a positive price must be allocated (all unallocated items must have a zero price). It maximizes the social welfare. ^ However, a Walrasian equilibrium might not exist (it is guaranteed to exist only when agents have gross substitute valuations). Moreover, even when it exists, the sellers' revenue might be low. Allowing the seller to discard some items might help the seller attain a higher revenue.

Maximizing the seller's revenue subject to market-envy-freeness

Many authors studied the computational problem of finding a price-vector that maximizes the seller's revenue, subject to market-envy-freeness.

Guruswami, Hartline, Karlin, Kempe, Kenyon and McSherry [1] (who introduced the term envy-free pricing) studied two classes of utility functions: unit demand and single-minded . They showed:

Balcan, Blum and Mansour [2] studied two settings: goods with unlimited supply (e.g. digital goods), and goods with limited supply. They showed that a single price, selected at random, attains an expected revenue which is a non-trivial approximation of the maximum social welfare:

Briest and Krysta [3] focused on goods with unlimited supply and single-minded buyers - each buyer wants only a single bundle of goods. They showed that:

Briest [4] focused on unit-demand min-pricing buyers. Each such buyer has a subset of wanted items, and he would like to purchase the cheapest affordable wanted-item given the prices. He focused on the uniform-budget case. He showed that, under some reasonable complexity assumptions:

Chen, Ghosh and Vassilvtskii [5] focused on items with metric substitutability - buyer i’s value for item j is vi − ci,j, and the substitution costs ci,j, form a metric. They show that

Wang, Lu and Im [6] study the problem with supply constraints given as an independence system over the items, such as matroid constraints. They focus on unit-demand buyers.

Chen and Deng [7] study multi-item markets: there are m indivisible items with unit supply each and n potential buyers where each buyer wants to buy a single item. They show:

Cheung and Swamy [8] present polytime approximation algorithms for single-minded agents with limited supply. They approximate the revenue w.r.t. the maximum social welfare.

Hartline and Yan [9] study revenue-maximization using prior-free truthful mechanisms. They also show the simple structure of nvy-free pricing and its connection to truthful mechanism design.

Chalermsook, Chuzhoy, Kannan and Khanna [10] study two variants of the problem. In both variants, each buyer has a set of "wanted items".

They also study the Tollbooth Pricing problem - a special case of single-minded pricing in which each item is an edge in a graph, and each wanted-items set is a path in this graph.

Chalermsook, Laekhanukit and Nanongkai [11] prove approximation hardness to a variant called k-hypergraph pricing. They also prove hardness for unit-demand min-buying and single-minded pricing. [12]

Demaine, Feige, Hajiaghayi and Salavatipour [13] show hardness-of-approximation results by reduction from the unique coverage problem.

Anshelevich, Kar and Sekar [14] study EF pricing in large markets. They consider both revenue-maximization and welfare-maximization.

Bilo, Flammini and Monaco [15] study EF pricing with sharp demands—where each buyer is interested in a fixed quantity of an item.

Colini-Baldeschi, Leonardi, Sankowski and Zhang [16] and Feldman, Fiat, Leonardi and Sankowski [17] study EF pricing with budgeted agents.

Monaco, Sankowski and Zhang [18] study multi-unit markets. They study revenue maximization under both market-envy-freeness and agent-envy-freeness. They consider both item-pricing and bundle-pricing.

Relaxed notions of envy-freeness

See also

Related Research Articles

<span class="mw-page-title-main">Double auction</span> Process of buying and selling goods

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.

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.

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.

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.

In economics and social choice theory, an envy-free matching (EFM) is a matching between people to "things", which is envy-free in the sense that no person would like to switch their "thing" with that of another person. This term has been used in several different contexts.

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.

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.

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.

Market equilibrium computation is a computational problem in the intersection of economics and computer science. The input to this problem is a market, consisting of a set of resources and a set of agents. There are various kinds of markets, such as Fisher market and Arrow–Debreu market, with divisible or indivisible resources. The required output is a competitive equilibrium, consisting of a price-vector, and an allocation, such that each agent gets the best bundle possible given the budget, and the market clears.

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 computational economics, a single-minded agent is an agent who wants only a very specific combination of items. The valuation function of such an agent assigns a positive value only to a specific set of items, and to all sets that contain it. It assigns a zero value to all other sets. A single-minded agent regards the set of items he wants as purely complementary goods.

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

  1. 1 2 Guruswami, Venkatesan; Hartline, Jason D.; Karlin, Anna R.; Kempe, David; Kenyon, Claire; McSherry, Frank (23 January 2005). On profit-maximizing envy-free pricing. Society for Industrial and Applied Mathematics. pp. 1164–1173. ISBN   978-0-89871-585-9.
  2. ↑ Balcan, Maria-Florina; Blum, Avrim; Mansour, Yishay (2008). "Item pricing for revenue maximization". In Fortnow, Lance; Riedl, John; Sandholm, Tuomas (eds.). Proceedings of the 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008. pp. 50–59. doi:10.1145/1386790.1386802. ISBN   9781605581699. S2CID   53038874.
  3. ↑ Briest, Patrick; Krysta, Piotr (2006-01-22). "Single-minded unlimited supply pricing on sparse instances". Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. SODA '06. Miami, Florida: Society for Industrial and Applied Mathematics. pp. 1093–1102. doi:10.1145/1109557.1109678. ISBN   978-0-89871-605-4. S2CID   4191038.
  4. ↑ Briest, Patrick (2008). "Uniform Budgets and the Envy-Free Pricing Problem". In Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor (eds.). Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 5125. Springer Berlin Heidelberg. pp. 808–819. CiteSeerX   10.1.1.205.433 . doi:10.1007/978-3-540-70575-8_66. ISBN   9783540705758.
  5. ↑ Chen, Ning; Ghosh, Arpita; Vassilvitskii, Sergei (2011). "SIAM (Society for Industrial and Applied Mathematics)". SIAM Journal on Computing. 40 (3): 623–645. CiteSeerX   10.1.1.193.6235 . doi:10.1137/080740970.
  6. ↑ Im, Sungjin; Lu, Pinyan; Wang, Yajun (2010). "Envy-Free Pricing with General Supply Constraints". In Saberi, Amin (ed.). Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. Berlin, Heidelberg: Springer. pp. 483–491. doi:10.1007/978-3-642-17572-5_41. ISBN   978-3-642-17572-5.
  7. ↑ Chen, Ning; Deng, Xiaotie (1 February 2014). "Envy-free Pricing in Multi-item Markets". ACM Transactions on Algorithms. 10 (2): 7:1–7:15. CiteSeerX   10.1.1.297.784 . doi:10.1145/2567923. ISSN   1549-6325. S2CID   15309106.
  8. ↑ 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.
  9. ↑ Devanur, Nikhil R.; Hartline, Jason D.; Yan, Qiqi (2015-03-01). "Envy freedom and prior-free mechanism design". Journal of Economic Theory. 156: 103–143. arXiv: 1212.3741 . doi:10.1016/j.jet.2014.08.001. ISSN   0022-0531. S2CID   17990320.
  10. ↑ Chalermsook, Parinya; Chuzhoy, Julia; Kannan, Sampath; Khanna, Sanjeev (2012). "Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply". In Gupta, Anupam; Jansen, Klaus; Rolim, José; Servedio, Rocco (eds.). Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Vol. 7408. Berlin, Heidelberg: Springer. pp. 73–84. doi:10.1007/978-3-642-32512-0_7. ISBN   978-3-642-32512-0.
  11. ↑ Chalermsook, P.; Laekhanukit, B.; Nanongkai, D. (2013-10-01). "Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 370–379. arXiv: 1308.2617 . doi:10.1109/FOCS.2013.47. ISBN   978-0-7695-5135-7. S2CID   972321.
  12. ↑ Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (2013-01-06). "Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More". Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings. Society for Industrial and Applied Mathematics. pp. 1557–1576. arXiv: 1212.4129 . doi:10.1137/1.9781611973105.112. ISBN   978-1-61197-251-1. S2CID   6556716 . Retrieved 2021-04-04.
  13. ↑ Demaine, Erik D.; Feige, Uriel; Hajiaghayi, MohammadTaghi; Salavatipour, Mohammad R. (2008-01-01). "Combination Can Be Hard: Approximability of the Unique Coverage Problem". SIAM Journal on Computing. 38 (4): 1464–1483. doi:10.1137/060656048. ISSN   0097-5397. S2CID   12248889.
  14. ↑ Anshelevich, Elliot; Kar, Koushik; Sekar, Shreyas (2017-08-09). "Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare". ACM Transactions on Economics and Computation. 5 (3): 16:1–16:42. doi:10.1145/3105786. ISSN   2167-8375. S2CID   7008965.
  15. ↑ Bilò, Vittorio; Flammini, Michele; Monaco, Gianpiero (2017-02-01). "Approximating the revenue maximization problem with sharp demands". Theoretical Computer Science. 662: 9–30. arXiv: 1312.3892 . doi: 10.1016/j.tcs.2016.12.002 . ISSN   0304-3975.
  16. ↑ Colini-Baldeschi, Riccardo; Leonardi, Stefano; Sankowski, Piotr; Zhang, Qiang (2014). "Revenue Maximizing Envy-Free Fixed-Price Auctions with Budgets". In Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). Web and Internet Economics. Lecture Notes in Computer Science. Vol. 8877. Cham: Springer International Publishing. pp. 233–246. doi:10.1007/978-3-319-13129-0_18. hdl: 11573/754515 . ISBN   978-3-319-13129-0.
  17. ↑ Feldman, Michal; Fiat, Amos; Leonardi, Stefano; Sankowski, Piotr (2012). "Revenue maximizing envy-free multi-unit auctions with budgets". Proceedings of the 13th ACM Conference on Electronic Commerce. EC '12. New York, NY, USA: ACM. pp. 532–549. doi:10.1145/2229012.2229052. ISBN   9781450314152. S2CID   15639601.
  18. ↑ Monaco, Gianpiero; Sankowski, Piotr; Zhang, Qiang (2015-07-25). "Revenue maximization envy-free pricing for homogeneous resources". Proceedings of the 24th International Conference on Artificial Intelligence. IJCAI'15. Buenos Aires, Argentina: AAAI Press: 90–96. ISBN   978-1-57735-738-4.
  19. ↑ Chen, Ning; Rudra, Atri (2008-09-01). "Walrasian Equilibrium: Hardness, Approximations and Tractable Instances". Algorithmica. 52 (1): 44–64. doi:10.1007/s00453-007-9103-9. ISSN   1432-0541. S2CID   18839423.
  20. ↑ Alon, Noga; Mansour, Yishay; Tenneholtz, Moshe (2013-06-16). "Differential pricing with inequity aversion in social networks". Proceedings of the fourteenth ACM conference on Electronic commerce. EC '13. Philadelphia, Pennsylvania, USA: Association for Computing Machinery. pp. 9–24. doi:10.1145/2492002.2482545. ISBN   978-1-4503-1962-1.
  21. ↑ Amanatidis, Georgios; Fulla, Peter; Markakis, Evangelos; Sornat, Krzysztof (2019-12-17). "Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results". arXiv: 1606.06664 [cs.GT].
  22. ↑ Flammini, Michele; Mauro, Manuel; Tonelli, Matteo (2019-04-01). "On social envy-freeness in multi-unit markets". Artificial Intelligence. 269: 1–26. doi: 10.1016/j.artint.2018.12.003 . ISSN   0004-3702. S2CID   19205358.
  23. ↑ "Inequity Aversion Pricing in Multi-Unit Markets". iris.gssi.it. Retrieved 2021-04-05.
  24. ↑ Elbassioni, Khaled; Fouz, Mahmoud; Swamy, Chaitanya (2010). "Approximation Algorithms for Non-single-minded Profit-Maximization Problems with Limited Supply". In Saberi, Amin (ed.). Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. Berlin, Heidelberg: Springer. pp. 462–472. arXiv: 1312.0137 . doi:10.1007/978-3-642-17572-5_39. ISBN   978-3-642-17572-5. S2CID   14124011.
  25. ↑ "Dynamic Envy-Freeness in Pricing" . Retrieved 2024-04-10.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.