{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T13:40:15Z","timestamp":1765546815422,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2021,9,26]],"date-time":"2021-09-26T00:00:00Z","timestamp":1632614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In general, the unit-demand envy-free pricing problem has proven to be APX-hard, but some special cases can be optimally solved in polynomial time. When substitution costs that form a metric space are included, the problem can be solved in O(n4) time, and when the number of consumers is equal to the number of items\u2014all with a single copy so that each consumer buys an item\u2014a O(n3) time method is presented to solve it. This work shows that the first case has similarities with the second, and, by exploiting the structural properties of the costs set, it presents a O(n2) time algorithm for solving it when a competitive equilibrium is considered or a O(n3) time algorithm for more general scenarios. The methods are based on a dynamic programming strategy, which simplifies the calculations of the shortest paths in a network; this simplification is usually adopted in the second case. The theoretical results obtained provide efficiency in the search for optimal solutions to specific revenue management problems.<\/jats:p>","DOI":"10.3390\/a14100279","type":"journal-article","created":{"date-parts":[[2021,9,27]],"date-time":"2021-09-27T01:59:47Z","timestamp":1632707987000},"page":"279","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Short Communication: Optimally Solving the Unit-Demand Envy-Free Pricing Problem with Metric Substitutability in Cubic Time"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6680-4023","authenticated-orcid":false,"given":"Marcos M.","family":"Salvatierra","sequence":"first","affiliation":[{"name":"Institute of Computing, Federal University of Amazonas, Manaus 69067-005, Brazil"}]},{"suffix":"Jr.","given":"Mario","family":"Salvatierra","sequence":"additional","affiliation":[{"name":"Institute of Computing, Federal University of Amazonas, Manaus 69067-005, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1740-2618","authenticated-orcid":false,"given":"Juan G.","family":"Colonna","sequence":"additional","affiliation":[{"name":"Institute of Computing, Federal University of Amazonas, Manaus 69067-005, Brazil"}]}],"member":"1968","published-online":{"date-parts":[[2021,9,26]]},"reference":[{"key":"ref_1","first-page":"45","article-title":"Resource allocation and the public sector","volume":"7","author":"Foley","year":"1967","journal-title":"Yale Econ. Essays"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.tcs.2016.12.002","article-title":"Approximating the Revenue Maximization Problem with Sharp Demands","volume":"662","author":"Flammini","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","unstructured":"Br\u00e2nzei, S., Filos-Ratsikas, A., Miltersen, P.B., and Zeng, Y. (2017). Walrasian Pricing in Multi-Unit Auctions. arXiv."},{"key":"ref_4","unstructured":"Monaco, G., Sankowski, P., and Zhang, Q. (2015, January 25\u201331). Revenue Maximization Envy-free Pricing for Homogeneous Resources. Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI\u201915), Buenos Aires, Argentina."},{"key":"ref_5","unstructured":"Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., and McSherry, F. (2005, January 23\u201325). On Profit-maximizing Envy-free Pricing. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201905, Vancouver, BC, Canada."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1137\/080740970","article-title":"Optimal envy-free pricing with metric substitutability","volume":"40","author":"Chen","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Schrijver","year":"1981","journal-title":"Combinatorica"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.dam.2018.03.034","article-title":"On envy-free perfect matching","volume":"261","author":"Arbib","year":"2019","journal-title":"Discret. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM (JACM)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","article-title":"On a routing problem","volume":"16","author":"Bellman","year":"1958","journal-title":"Q. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Hartline, J.D., and Koltun, V. (2005). Near-optimal pricing in near-linear time. Workshop on Algorithms and Data Structures, Springer.","DOI":"10.1007\/11534273_37"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/j.disopt.2006.06.005","article-title":"A pricing problem under Monge property","volume":"5","year":"2008","journal-title":"Discret. Optim."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/s10589-009-9254-5","article-title":"Maximum utility product pricing models and algorithms based on reservation price","volume":"48","author":"Shioda","year":"2011","journal-title":"Comp. Opt. Appl."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2567923","article-title":"Envy-free pricing in multi-item markets","volume":"10","author":"Chen","year":"2014","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.cor.2015.11.013","article-title":"Efficient heuristic algorithms for maximum utility product pricing problems","volume":"69","author":"Myklebust","year":"2016","journal-title":"Comput. OR"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/3105786","article-title":"Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare","volume":"5","author":"Anshelevich","year":"2017","journal-title":"ACM Trans. Econ. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V.V. (2007). Algorithmic Game Theory, Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/10\/279\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:05:17Z","timestamp":1760166317000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/10\/279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,26]]},"references-count":17,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2021,10]]}},"alternative-id":["a14100279"],"URL":"https:\/\/doi.org\/10.3390\/a14100279","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,9,26]]}}}