A dual approach for dynamic pricing in multidemand markets

Bérczi, Kristóf and Bérczi-Kovács, Erika and Szögi, Evelin (2023) A dual approach for dynamic pricing in multidemand markets. SIAM JOURNAL ON DISCRETE MATHEMATICS, 37 (3). pp. 1771-1787. ISSN 0895-4801

Preview

Text Dual_approach_to_dynamic_pricing.pdf Download (405kB) | Preview

Abstract

Dynamic pricing schemes were introduced as an alternative to posted-price mechanisms. In contrast to static models, the dynamic setting allows to update the prices between buyer- arrivals based on the remaining sets of items and buyers, and so it is capable of maximizing social welfare without the need for a central coordinator. In this paper, we study the existence of optimal dynamic pricing schemes in combinatorial markets. In particular, we concentrate on multi-demand valuations, a natural extension of unit-demand valuations. The proposed approach is based on computing an optimal dual solution of the maximum social welfare problem with distinguished structural properties. Our contribution is twofold. By relying on an optimal dual solution, we show the exis- tence of optimal dynamic prices in unit-demand markets and in multi-demand markets up to three buyers, thus giving new interpretations of results of Cohen-Addad et al. and Berger et al., respectively. Furthermore, we provide an optimal dynamic pricing scheme for bi-demand valuations with an arbitrary number of buyers. In all cases, our proofs also provide efficient algorithms for determining the optimal dynamic prices.

Actions (login required)

Edit Item