Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Complexity Classes of Envy-Free Pricing Problems: A Short Survey

  • Review
  • Published:
Operations Research Forum Aims and scope Submit manuscript

Abstract

Envy-free pricing problems model pricing situations where both seller’s revenue and buyers’ utilities are maximized. These problems imply a variety of theoretical approaches and practical applications in several fields of research and real-world situations. This paper aims to provide a comprehensive literature review on how distinct features change the computational complexity of envy-free pricing problems, showing a taxonomy of these problems and pointing out some prospects in the study of this topic.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data Availability

No datasets were generated or analyzed during the current study.

References

  1. Alimonti P, Kann V (1997) Hardness of approximating problems on cubic graphs. In: Bongiovanni GC, Bovet DP, Battista GD (eds) Algorithms and complexity, third Italian conference, CIAC ’97, Rome, Italy, March 12-14, 1997, Proceedings, Lecture Notes in Computer Science, vol 1203. Springer, pp 288–298. https://doi.org/10.1007/3-540-62592-5_80

  2. Alimonti P, Kann V (2000) Some apx-completeness results for cubic graphs. Theoret Comput Sci 237(1):123–134. https://doi.org/10.1016/S0304-3975(98)00158-3

    Article  Google Scholar 

  3. Anshelevich E, Kar K, Sekar S (2017) Envy-free pricing in large markets: approximating revenue and welfare. ACM Trans Econ Comput 5(3):16:1-16:42. https://doi.org/10.1145/3105786

    Article  Google Scholar 

  4. Arbib C, Karaşan O, Pinar M (2019) On envy-free perfect matching. Discret Appl Math 261:22–27. https://doi.org/10.1016/j.dam.2018.03.034, gO X Meeting, Rigi Kaltbad (CH), July 10-14, 2016

  5. Ausiello G, Marchetti-Spaccamela A, Crescenzi P et al (1999) Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. https://doi.org/10.1007/978-3-642-58412-1

    Article  Google Scholar 

  6. Bellman R (1958) On a routing problem. Q Appl Math 16(1):87–90. https://doi.org/10.1090/qam/102435

    Article  Google Scholar 

  7. Berge C (2001) The theory of graphs. Courier Corporation

  8. Berman P, Karpinski M (1999) On some tighter inapproximability results (extended abstract). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1644 LNCS:200–209. https://doi.org/10.1007/3-540-48523-6_17

  9. Berman P, Schnitger G (1992) On the complexity of approximating the independent set problem. Inf Comput 96(1):77–94. https://doi.org/10.1016/0890-5401(92)90056-L

    Article  Google Scholar 

  10. Böhnlein T, Kratsch S, Schaudt O (2021) Revenue maximization in stackelberg pricing games: beyond the combinatorial setting. Math Program 187(1–2):653–695. https://doi.org/10.1007/s10107-020-01495-0

    Article  Google Scholar 

  11. Bouhtou M, Grigoriev A, Hoesel Sv et al (2007a) Pricing bridges to cross a river. Naval Research Logistics (NRL) 54(4):411–420. https://doi.org/10.1002/nav.20216

  12. Bouhtou M, van Hoesel S, van der Kraaij AF et al (2007b) Tariff optimization in networks. INFORMS J Comput 19(3):458–469. https://doi.org/10.1287/ijoc.1060.0177

    Article  Google Scholar 

  13. Briest P, Krysta P (2006) Single-minded unlimited supply pricing on sparse instances. In: Proceedings of the annual ACM-SIAM symposium on discrete algorithms, pp 1093–1102. https://doi.org/10.1145/1109557.1109678

  14. Briest P, Krysta P (2011) Buying cheap is expensive: approximability of combinatorial pricing problems. SIAM J Comput 40(6):1554–1586. https://doi.org/10.1137/090752353

    Article  Google Scholar 

  15. Burkard RE, Klinz B, Rudolf R (1996) Perspectives of monge properties in optimization. Discret Appl Math 70(2):95–161. https://doi.org/10.1016/0166-218X(95)00103-X

    Article  Google Scholar 

  16. Chen N, Deng X (2014) Envy-free pricing in multi-item markets. ACM Transactions on Algorithms (TALG) 10(2):1–15. https://doi.org/10.1145/2567923

    Article  Google Scholar 

  17. Chen N, Ghosh A, Vassilvitskii S (2011) Optimal envy-free pricing with metric substitutability. SIAM J Comput 40(3):623–645. https://doi.org/10.1137/080740970

    Article  Google Scholar 

  18. Chen N, Deng X, Goldberg PW et al (2016) On revenue maximization with sharp multi-unit demands. J Comb Optim 31(3):1174–1205. https://doi.org/10.1007/s10878-014-9817-y

    Article  Google Scholar 

  19. Chudnovsky M, Robertson N, Seymour P et al (2006) The strong perfect graph theorem. Ann Math 164(1):51–229. https://doi.org/10.4007/annals.2006.164.51, cited by: 718; All Open Access, Bronze Open Access, Green Open Access

  20. Cormen TH, Leiserson CE, Rivest RL et al (2022) Introduction to algorithms. MIT press

  21. Deng X, Goldberg P, Sun Y et al (2017) Pricing ad slots with consecutive multi-unit demand. Auton Agent Multi-Agent Syst 31(3):584–605. https://doi.org/10.1007/s10458-016-9335-7, cited by: 1; All Open Access, Green Open Access

  22. Elbassioni K, Raman R, Ray S et al (2012) On the complexity of the highway problem. Theoret Comput Sci 460:70–77. https://doi.org/10.1016/j.tcs.2012.07.028

    Article  Google Scholar 

  23. Fazli M, Nikparto N, Saghafian M (2011) Envy free chain store pricing. In: 2011 CSI international symposium on Computer Science and Software Engineering (CSSE), pp 44–47. https://doi.org/10.1109/CSICSSE.2011.5963991

  24. Feige U, Peleg D, Kortsarz G (2001) The dense k-subgraph problem. Algorithmica 29:410–421. https://doi.org/10.1007/s004530010050

    Article  Google Scholar 

  25. Feldman M, Gravin N, Lucier B (2016) Combinatorial walrasian equilibrium. SIAM J Comput 45(1):29–48

    Article  Google Scholar 

  26. Flammini M, Mauro M, Tonelli M (2021) On fair price discrimination in multi-unit markets. Artif Intell 290. https://doi.org/10.1016/j.artint.2020.103388

  27. Garey M, Johnson D, Stockmeyer L (1976) Some simplified np-complete graph problems. Theoret Comput Sci 1(3):237–267. https://doi.org/10.1016/0304-3975(76)90059-1

    Article  Google Scholar 

  28. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman

  29. Günlük O (2008) A pricing problem under monge property. Discret Optim 5(2):328–336. https://doi.org/10.1016/j.disopt.2006.06.005

    Article  Google Scholar 

  30. Grigoriev A, van Loon J, Sviridenko M et al (2008) Optimal bundle pricing with monotonicity constraint. Oper Res Lett 36(5):609–614. https://doi.org/10.1016/j.orl.2008.04.008

    Article  Google Scholar 

  31. Grigoriev A, van Loon J, Sitters R et al (2009) Optimal pricing of capacitated networks. Networks 53(1):79–87. https://doi.org/10.1002/net.20260

    Article  Google Scholar 

  32. Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197. https://doi.org/10.1007/BF02579273

    Article  Google Scholar 

  33. Guruswami V, Hartline JD, Karlin AR et al (2005) On profit-maximizing envy-free pricing. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, SODA ’05, pp 1164–1173. http://dl.acm.org/citation.cfm?id=1070432.1070598

  34. Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 13(5):1194–1217. https://doi.org/10.1137/0913069

    Article  Google Scholar 

  35. Hartline JD, Koltun V (2005) Near-optimal pricing in near-linear time. In: Dehne F, López-Ortiz A, Sack JR (eds) Algorithms and data structures. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 422–431. https://doi.org/10.1007/11534273_37

  36. Jacquet Q, van Ackooij W, Alasseur C et al (2023) Quadratic regularization of bilevel pricing problems and application to electricity retail markets. Eur J Oper Res. https://doi.org/10.1016/j.ejor.2023.05.006

    Article  Google Scholar 

  37. Kitchenham B (2004) Procedures for performing systematic reviews. Keele, UK, Keele University 33(2004):1–26

    Google Scholar 

  38. Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76. http://www.jstor.org/stable/1907742

  39. Monaco G, Sankowski P, Zhang Q (2015) Revenue maximization envy-free pricing for homogeneous resources. In: Proceedings of the 24th international conference on artificial intelligence, IJCAI’15, pp 90–960. http://dl.acm.org/citation.cfm?id=2832249.2832262

  40. Nisan N, Roughgarden T, Tardos E et al (2007) Algorithmic game theory. Cambridge University Press, New York, NY, USA

    Book  Google Scholar 

  41. Ortega-Arranz H, Gonzalez-Escribano A, Llanos DR (2022) The shortest-path problem: analysis and comparison of methods. Springer Nature

  42. O’Searcoid M (2006) Metric spaces. Springer Science & Business Media

  43. Salvatierra MM, Salvatierra M, Colonna JG (2021) Short communication: optimally solving the unit-demand envy-free pricing problem with metric substitutability in cubic time. Algorithms 14(10). https://doi.org/10.3390/a14100279

  44. Trudeau RJ (2013) Introduction to graph theory. Courier Corporation

  45. Wohlin C (2014) Guidelines for snowballing in systematic literature studies and a replication in software engineering. In: Proceedings of the 18th international conference on evaluation and assessment in software engineering. Association for Computing Machinery, New York, NY, USA, EASE ’14. https://doi.org/10.1145/2601248.2601268

  46. Wolsey LA, Nemhauser GL (1999) Integer and combinatorial optimization, vol 55. John Wiley & Sons

    Google Scholar 

Download references

Funding

This work was partially funded by the Academic Productivity Bonus Program of the University of Amazonas State through project 01.02.011304.026190/2022-07, partially supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES-PROEX) - Finance Code 001, and partially supported by Amazonas State Research Support Foundation - FAPEAM - through the POSGRAD 22-23 project.

Author information

Author notes

  1. Juan G. Colonna, Mario Salvatierra Jr., and Alcides de C. Amorim Neto contributed equally to this work.

Authors and Affiliations

  1. Normal Superior School, University of Amazonas State, Av. Djalma Batista, Manaus, 69050-010, Amazonas, Brazil

    Marcos Salvatierra & Alcides de C. Amorim Neto

  2. Institute of Computing, Federal University of Amazonas, Av. General Rodrigo Octavio Jordao Ramos, Manaus, 69067-005, Amazonas, Brazil

    Juan G. Colonna & Mario Salvatierra Jr.

Authors
  1. Marcos Salvatierra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juan G. Colonna
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mario Salvatierra Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Alcides de C. Amorim Neto
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

M.S. wrote the main manuscript text. J.C. contributed to the methodology and presentation of results. M.S. Jr contributed to the analysis of the mathematical results and A.A.N. reviewed the manuscript.

Corresponding author

Correspondence to Marcos Salvatierra.

Ethics declarations

Ethics Approval

Not applicable.

Consent to Participate

Not applicable.

Conflict of Interest

The authors declare no competing interests.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

We present a complete taxonomy of envy-free pricing problems whose complexity results were described in this paper. See Fig. 6.

Fig. 6
figure 6

Complete taxonomy of envy-free pricing problems surveyed in this paper

Full size image

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Salvatierra, M., Colonna, J.G., Salvatierra Jr., M. et al. On Complexity Classes of Envy-Free Pricing Problems: A Short Survey. Oper. Res. Forum 5, 103 (2024). https://doi.org/10.1007/s43069-024-00373-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s43069-024-00373-1

Keywords

MSC Classification

Search

Navigation