Online Assortment with Limited Inventories and Set-Dependent Revenues
We consider an online assortment problem with [n]:={1,2,...,n} sellers, each holding exactly one item i∈[n] of initial inventory c_i∈Z_+, 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 particular, 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 played 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 the first constant factor competitive algorithm for the online platform. 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.
READ FULL TEXT