论文标题
在Bertrand竞争下的在线分类和市场细分，并获得一套依赖的收入
Online Assortment and Market Segmentation under Bertrand Competition with Set-Dependent Revenues
论文作者
论文摘要
We consider an online assortment problem with $[n]:=\{1,2,\ldots,n\}$ sellers, each holding exactly one item $i\in[n]$ with initial inventory $c_i\in \mathbb{Z}_+$, and a sequence of homogeneous buyers arriving over a finite time horizon $t=1,2,\ldots,m$.有一个在线平台，其目标是在$ t $时向到达买家提供子集$ s_t \ subseteq [n] $，以最大程度地提高整个地平线的预期收入，同时尊重库存约束。考虑到时间$ t $的分类$ s_t $，假设买方将根据众所周知的多项式Logit模型从$ s_t $中选择一个项目，这是经济文献中良好的选择模型。在此型号中，从给定时间出售项目$ i $获得的收入$ t $严重取决于当时提供的分类$ s_t $，并且由卖方在$ s_t $中的卖方中的NASH平衡给出。这在提供的分类，卖方的收入和库存水平之间实现了强烈的依赖/外部性。尽管有挑战，我们还是为与同质买家的在线分类问题设计了一种持续的竞争算法。我们还表明，异质买家的在线分类问题不承认持续的竞争算法。为了弥补这一问题，我们随后考虑了与异构买家的离线设置下的分类问题。在一个温和的市场一致性假设下，我们表明，广义的Bertrand游戏承认了对普通买家双方图的纯粹纳什均衡。最后，我们开发了一种$ O（\ ln m）$ - 近似算法，以最佳的市场细分市场细分，该算法可以通过将市场分配到较小的池中来获得更高的收入。
We consider an online assortment problem with $[n]:=\{1,2,\ldots,n\}$ sellers, each holding exactly one item $i\in[n]$ with initial inventory $c_i\in \mathbb{Z}_+$, and a sequence of homogeneous buyers arriving over a finite time horizon $t=1,2,\ldots,m$. There is an online platform whose goal is to offer a subset $S_t\subseteq [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 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. We also show that the online assortment problem with heterogeneous buyers does not admit a constant competitive algorithm. To compensate for 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.
