Allocation and Pricing of Substitutable Goods: Theory and Algorithm
受在线展示广告市场启发，研究多种可替代商品在众多风险厌恶且偏好异质的代理人中的最优分配与定价问题，提出可扩展的SIMS算法，其速度比已知算法快三个数量级。
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.