Dynamic Pricing in Competitive Markets
  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-\alpha)$ times optimal revenue is bounded as $O(T^{1/4} /
\sqrt{\alpha})$. 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.
