Online Assortment and Market Segmentation under Bertrand Competition with Set-Dependent Revenues
share
We consider an online assortment problem with [n]:={1,2,...,n} sellers, each holding exactly one item i∈[n] with initial inventory c_i∈ℤ_+, and a sequence of homogeneous buyers arriving over a finite time horizon t=1,2,...,m. There is an online platform whose goal is to offer a subset S_t⊆ [n] of sellers to the arriving buyer at time t to maximize the expected revenue derived over the entire horizon while respecting the inventory constraints. Given an assortment S_t at time t, it is assumed that the buyer will select an item from S_t based on the well-known multinomial logit model, a well-justified choice model from the economic literature. In this model, the revenue obtained from selling an item i at a given time t critically depends on the assortment S_t offered at that time and is given by the Nash equilibrium of a Bertrand game among the sellers in S_t. This imposes a strong dependence/externality between the offered assortments, items revenues, and inventory levels. Despite these challenges, we devise a constant competitive algorithm for the online assortment problem with homogeneous buyers. This answers a question in a paper by Zheng and Srikant 2019, that considered the static version of this problem with only one buyer and no inventory constraints. We then consider this model under an offline setting with heterogeneous buyers. Under a mild market consistency assumption, we show that the generalized Bertrand game admits a pure strategy Nash equilibrium over arbitrary buyer-seller bipartite graphs. Finally, we develop an O(ln m)-approximation algorithm for optimal market segmentation of the generalized Bertrand game.
READ FULL TEXT