Working Paper
Centralized vs. Decentralized Design in Multi-Item Pricing with Heterogeneous Customers
with Omar El Housni.
Abstract
We study a multi-item pricing problem, where a monopolistic seller faces heterogeneous customer segments and aims to set prices to maximize expected revenue. We consider two design models: in the decentralized model, the seller sets prices for all available items. In the centralized model, the seller decides a single item to offer and sets its price. Each customer segment has a valuation for each item and maximizes their utility, defined as the difference between the valuation and the price.
We investigate the cost of centralization, defined as the worst-case value of the ratio between the optimal expected revenues of the centralized and decentralized problems. We show that this ratio can be as small as the inverse of the number of customer segments in general, and this bound is tight. However, this worst-case gap shrinks when the valuation matrix exhibits additional structure. When customer preferences are described by a rank-one valuation matrix, we show that the expected revenues of the centralized and decentralized designs coincide, leading to no gap between the two models. More generally, if the valuation matrix has a block-rank-one structure with k clusters of customers exhibiting aligned preferences, the centralized revenue is within a 1/k factor of the decentralized revenue. These results show that centralized mechanisms are most effective in homogeneous markets, where customer preferences are aligned and the revenue loss from limiting choice is minimal.
On the algorithmic side, we observe that the centralized model admits a polynomial-time exact algorithm. In contrast, we show that the decentralized problem is NP-hard even in simple settings. Finally, we leverage the geometric structure of the decentralized problem to design a polynomial-time algorithm when the number of items is fixed.
Draft available upon request.