Envy-free pricing

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:

  • Agent envy means that some agent assigns a higher utility (a higher difference value-price) to a bundle allocated to another agent.
  • Market envy means that some agent assigns a higher utility (a higher difference value-price) to any bundle.

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:

  • The social welfare - the sum of buyers' utilities;
  • The seller's revenue (or profit) - the sum of prices paid by buyers.

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

  • In envy-free item allocation, monetary payments are not allowed.
  • In the rental harmony problem, monetary payments are allowed, and the agents are quasilinear, but all objects should be allocated (and each agent should get exactly one object).

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:

  • Computing market-envy-free prices to maximize the seller's revenue is APX-hard in both cases.
  • There is a logarithmic approximation algorithm for the revenue in both cases.
  • There are polynomial-time algorithms for some special cases.

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:

  • With unlimited supply, a random single price achieves a log-factor approximation to the maximum social welfare. This is true even with general (not monotone) valuations. For a single agent and m item types, the revenue is at least 4 log (2m) of the maximum welfare; for n buyers, it is at least O(log (n) + log (m)) of the maximum welfare.
  • With limited supply, for subadditive valuations, a random single price achieves revenue within 2O(√(log n loglog n)) of the maximum welfare.
  • In the multi-unit case, when no buyer requires more than a 1-ε fraction of the items, a random single price achieves revenue within O(log n) of the maximum welfare.
  • A lower bound for fractionally subadditive buyers: any single price has approximation ratio 2Ω(log1/4n).

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:

  • The problem is weakly NP-hard even when the wanted bundles are nested.
  • The problem is APX-hard even for very sparse instances.
  • There is a log-factor approximation algorithm.

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:

  • The unit-demand min-buying pricing problem with uniform budgets cannot be approximated in polytime for some ε> 0.
  • A slightly more general problem, in which consumers are given as an explicit probability distribution, is even harder to approximate.
  • All the results apply to single-minded buyers too.

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

  • With metric substitutability, the problem can be solved exactly in polynomial time.
  • When the substitution costs are only approximately a metric (i.e., they satisfy the triangle inequality approximately), the problem becomes NP-hard.

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:

  • A polytime algorithm to compute a revenue maximizing EF pricing when every buyer evaluates at most two items at a positive valuation (they use the Strong Perfect Graph Theorem).
  • The problem becomes NP-hard if some buyers are interested in at least three items.

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".

  • Unit-demand min-buying pricing: each buyer buys his cheapest wanted item if its price is ≤ the agent's budget; otherwise he buys nothing.
  • Single-minded pricing: each buyer buys all his wanted items if their price is ≤ the agent's budget; otherwise he buys nothing.

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
  • Chen and Rudra[19] consider a relaxation of Walrasian equilibrium, in which only the winners must be envy-free. The goal is to maximize the number of envy-free buyers.
  • Alon, Mansour and Tennenholtz[20] and Amanatidis, Fulla, Markakis and Sornat[21] consider a relaxation of market-envy-freeness, in which buyers are arranged in a social network, the prices should be similar only between nodes that are adjacent on the network, and the losers must not envy.
  • Flammini, Mauro and Tonelly[22][23] consider a relaxation of market-envy-freeness in which each agent sees only the items of neighboring agents (on a given social network).
  • Elbassioni, Fouz and Swamy[24] consider a relaxation of agent-envy-freeness, in which only the winners must not envy. They consider bundle-pricing.

See also
  • Demand oracle - an oracle that is often used in algorithms for envy-free pricing.

References
  1. 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. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.