Dynamic Pricing in Competitive Markets
This work addresses revenue maximization for sellers in competitive markets, providing incremental algorithmic improvements with theoretical guarantees.
The paper tackles dynamic pricing in competitive markets with substitutable goods, achieving a $O(\\sqrt{T})$ regret bound for static markets under CES utility and $O(T^{1/4} / \\sqrt{\\alpha})$ regret for iso-elastic utilities, with extensions to dynamic supplies.
Dynamic pricing of goods in a competitive environment to maximize revenue is a natural objective and has been a subject of research over the years. In this paper, we focus on a class of markets exhibiting the substitutes property with sellers having divisible and replenishable goods. Depending on the prices chosen, each seller observes a certain demand which is satisfied subject to the supply constraint. The goal of the seller is to price her good dynamically so as to maximize her revenue. For the static market case, when the consumer utility satisfies the Constant Elasticity of Substitution (CES) property, we give a $O(\sqrt{T})$ regret bound on the maximum loss in revenue of a seller using a modified version of the celebrated Online Gradient Descent Algorithm by Zinkevich. For a more specialized set of consumer utilities satisfying the iso-elasticity condition, we show that when each seller uses a regret-minimizing algorithm satisfying a certain technical property, the regret with respect to $(1-α)$ times optimal revenue is bounded as $O(T^{1/4} / \sqrtα)$. We extend this result to markets with dynamic supplies and prove a corresponding dynamic regret bound, whose guarantee deteriorates smoothly with the inherent instability of the market. As a side-result, we also extend the previously known convergence results of these algorithms in a general game to the dynamic setting.