Allocation and Pricing of Substitutable Goods: Theory and Algorithm

Huaxia Rui, De Liu, Andrew Whinston

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Motivated by the thriving market of online display advertising, we study a problem of allocating numerous types of goods among many agents who have concave valuations (capturing risk aversion) and heterogeneous substitution preferences across types of goods. The goal is both to provide a theory for optimal allocation of such goods, and to offer a scalable algorithm to compute the optimal allocation and the associated price vectors. Drawing on the economic concept of Pareto optimality, we develop an equilibrium pricing theory for heterogeneous substitutable goods that parallels the pricing theory for financial assets. We then develop a fast algorithm called SIMS (standardization-and-indicator-matrix-search). Extensive numerical simulations suggest that the SIMS algorithm is very scalable and is up to three magnitudes faster than well-known alternative algorithms. Our theory and algorithm have important implications for the pricing and scheduling of online display advertisement and beyond.

Original languageEnglish (US)
Pages (from-to)767-783
Number of pages17
JournalProduction and Operations Management
Issue number5
StatePublished - May 2017

Bibliographical note

Funding Information:
We thank the department editor, Dr. Subodha Kumar, the anonymous senior editor, and the three anonymous reviewers for very constructive comments. We also thank seminar participants at UT Austin, Baidu Inc., Purdue University, Tsinghua University, Shanghai University of Finance and Economics, POMS Annual Conference, INFORMS Annual Meeting, Workshop on Information Systems and Economics, Workshop on Data Mining for Online Advertising, and Midwest Workshop on Control and Game theory for useful comments. Dr. De Liu received support for this research from National Science Foundation of China under Grant No. 71571044. Remaining errors are our sole responsibility.

Publisher Copyright:
© 2017 Production and Operations Management Society


  • display advertising
  • resource allocation
  • substitutable goods


Dive into the research topics of 'Allocation and Pricing of Substitutable Goods: Theory and Algorithm'. Together they form a unique fingerprint.

Cite this