Abstract
We study a robust monopoly pricing problem with a minimax regret objective, where a seller endeavors to sell multiple goods to a single buyer, only knowing that the buyer’s values for the goods range over a rectangular uncertainty set. We interpret this pricing problem as a zero-sum game between the seller, who chooses a selling mechanism, and a fictitious adversary or ‘nature’, who chooses the buyer’s values from within the uncertainty set. Using duality techniques rooted in robust optimization, we prove that this game admits a Nash equilibrium in mixed strategies that can be computed in closed form. The Nash strategy of the seller is a randomized posted price mechanism under which the goods are sold separately, while the Nash strategy of nature is a distribution on the uncertainty set under which the buyer’s values are comonotonic. We further show that the restriction of the pricing problem to deterministic mechanisms is solved by a deteministic posted price mechanism under which the goods are sold separately.
Similar content being viewed by others
References
Bandi, C., Bertsimas, D.: Optimal design for multi-item auctions: a robust optimization approach. Math. Oper. Res. 39(4), 1012–1038 (2014)
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)
Bergemann, D., Schlag, K.: Pricing without priors. J. Eur. Econ. Assoc. 6(2–3), 560–569 (2008)
Bergemann, D., Schlag, K.: Robust monopoly pricing. J. Econ. Theory 146(6), 2527–2543 (2011)
Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464–501 (2011)
Bhargava, H.K.: Mixed bundling of two independently valued goods. Manag. Sci. 59(9), 2170–2185 (2013)
Bichler, M.: Market Design: A Linear Programming Approach to Auctions and Matching. Cambridge University Press, Cambridge (2017)
Carrasco, V., Luz, V.F., Kos, N., Messner, M., Monteiro, P., Moreira, H.: Optimal selling mechanisms under moment conditions. J. Econ. Theory 177, 245–279 (2018)
Carroll, G.: Robustness and separation in multidimensional screening. Econometrica 85(2), 453–488 (2017)
Daskalakis, C., Deckelbaum, A., Tzamos, C.: Mechanism design via optimal transport. In: Proceedings of the 14th ACM Conference on Electronic Commerce, pp. 269–286 (2013)
Daskalakis, C., Deckelbaum, A., Tzamos, C.: The complexity of optimal mechanism design. In: Proceedings of the 25th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 1302–1318 (2014)
Daskalakis, C., Deckelbaum, A., Tzamos, C.: Strong duality for a multiple-good monopolist. Econometrica 85(3), 735–767 (2017)
Fanzeres, B., Ahmed, S., Street, A.: Robust strategic bidding in auction-based markets. Eur. J. Oper. Res. 272(3), 1158–1172 (2019)
Giannakopoulos, Y., Koutsoupias, E.: Duality and optimality of auctions for uniform distributions. In: Proceedings of the 15th ACM Conference on Economics and Computation, pp. 259–276 (2014)
Gravin, N., Lu, P.: Separation in correlation-robust monopolist problem with budget. In: Proceedings of the Twenty-Ninth Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 2069–2080. SIAM (2018)
Guslitser, E.: Uncertainty-Immunized Solutions in Linear Programming. Master’s thesis, Technion-Israel Institute of Technology (2002)
Hart, S., Nisan, N.: Approximate revenue maximization with multiple items. J. Econ. Theory 172, 313–347 (2017a)
Hart, S., Nisan, N.: The Menu-size Complexity of Auctions. Technical report, The Hebrew University of Jerusalem (2017)
Lagarias, J.: Euler’s constant: Euler’s work and modern developments. Bull. Am. Math. Soc. 50(4), 527–628 (2013)
Li, X., Yao, A.C.C.: On revenue maximization for selling multiple independently distributed items. Proc. Natl. Acad. Sci. 110(28), 11232–11237 (2013)
Lopomo, G., Marx, L.M., Sun, P.: Bidder collusion at first-price auctions. Rev. Econ. Des. 15(3), 177–211 (2011)
Manelli, A.M., Vincent, D.R.: Bundling as an optimal selling mechanism for a multiple-good monopolist. J. Econ. Theory 127(1), 1–35 (2006)
Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981)
Myerson, R.B., Satterthwaite, M.A.: Efficient mechanisms for bilateral trading. J. Econ. Theory 29(2), 265–281 (1983)
Pınar, M.Ç., Kızılkale, C.: Robust screening under ambiguity. Math. Program. 163(1–2), 273–299 (2017)
Riley, J., Zeckhauser, R.: Optimal selling strategies: when to haggle, when to hold firm. Q. J. Econ. 98(2), 267–289 (1983)
Savage, L.J.: The theory of statistical decision. J. Am. Stat. Assoc. 46(253), 55–67 (1951)
Thanassoulis, J.: Haggling over substitutes. J. Econ. Theory 117(2), 217–245 (2004)
Vohra, R.V.: Optimization and mechanism design. Math. Program. 134(1), 283–303 (2012)
Wiesemann, W., Tsoukalas, A., Kleniati, P.M., Rustem, B.: Pessimistic bilevel optimization. SIAM J. Optim. 23(1), 353–380 (2013)
Acknowledgements
This research was funded by the SNSF grant BSCGI0_157733 and by the NUS Start-up Grant R-266-000-131-133.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Koçyiğit, Ç., Rujeerapaiboon, N. & Kuhn, D. Robust multidimensional pricing: separation without regret. Math. Program. 196, 841–874 (2022). https://doi.org/10.1007/s10107-021-01615-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-021-01615-4