TY - JOUR
T1 - ONLINE ASSORTMENT AND MARKET SEGMENTATION UNDER BERTRAND COMPETITION WITH SET-DEPENDENT REVENUES
AU - Etesami, S. Rasoul
N1 - \ast Received by the editors February 22, 2021; accepted for publication (in revised form) March 6, 2022; published electronically June 16, 2022. An earlier version of this paper without proofs was presented at the 2020 IEEE Conference on Decision and Control [14]. https://doi.org/10.1137/21M1400134 Funding: This work is supported by the National Science Foundation CAREER Award under grant EPCN-1944403. \dagger Department of Industrial and Enterprise Systems Engineering, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA ([email protected]).
PY - 2022
Y1 - 2022
N2 - We consider an online assortment problem with [n] = { 1, 2, . . ., n} sellers, each holding exactly one item i ∊ [n] with initial inventory ci ∊ ℤ+, 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 St ⊆ [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 St at time t, it is assumed that the buyer will select an item from St 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 St offered at that time and is given by the Nash equilibrium of a Bertrand game among the sellers in St. This imposes a strong dependence/externality among the offered assortments, sellers' revenues, and inventory levels. Despite that challenge, we devise a constant competitive algorithm for the online assortment problem with homogeneous buyers. It answers a question in [Z. Zheng and R. Srikant, Optimal Search Segmentation Mechanisms for Online Platform Markets, preprint, arXiv:1908.07489, 2019] that considered the static version of the assortment problem with only one buyer and no inventory constraints. We also show that the online assortment problem with heterogeneous buyers does not admit a constant competitive algorithm. To compensate that issue, we then consider the assortment problem under an offline setting with heterogeneous buyers. Under a mild market consistency assumption, we show that the generalized Bertrand game admits a pure Nash equilibrium over general buyer-seller bipartite graphs. Finally, we develop an O(ln m)-approximation algorithm for optimal market segmentation of the generalized Bertrand game which allows the platform to derive higher revenues by partitioning the market into smaller pools.
AB - We consider an online assortment problem with [n] = { 1, 2, . . ., n} sellers, each holding exactly one item i ∊ [n] with initial inventory ci ∊ ℤ+, 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 St ⊆ [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 St at time t, it is assumed that the buyer will select an item from St 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 St offered at that time and is given by the Nash equilibrium of a Bertrand game among the sellers in St. This imposes a strong dependence/externality among the offered assortments, sellers' revenues, and inventory levels. Despite that challenge, we devise a constant competitive algorithm for the online assortment problem with homogeneous buyers. It answers a question in [Z. Zheng and R. Srikant, Optimal Search Segmentation Mechanisms for Online Platform Markets, preprint, arXiv:1908.07489, 2019] that considered the static version of the assortment problem with only one buyer and no inventory constraints. We also show that the online assortment problem with heterogeneous buyers does not admit a constant competitive algorithm. To compensate that issue, we then consider the assortment problem under an offline setting with heterogeneous buyers. Under a mild market consistency assumption, we show that the generalized Bertrand game admits a pure Nash equilibrium over general buyer-seller bipartite graphs. Finally, we develop an O(ln m)-approximation algorithm for optimal market segmentation of the generalized Bertrand game which allows the platform to derive higher revenues by partitioning the market into smaller pools.
KW - Bertrand game
KW - inventory management
KW - multinomial logit model
KW - online assortment
KW - optimal market segmentation
KW - pure Nash equilibrium
KW - revenue management
UR - http://www.scopus.com/inward/record.url?scp=85135243462&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85135243462&partnerID=8YFLogxK
U2 - 10.1137/21M1400134
DO - 10.1137/21M1400134
M3 - Article
AN - SCOPUS:85135243462
SN - 0895-4801
VL - 36
SP - 1436
EP - 1466
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -