Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes

Yuval Emek (), Ron Lavi (), Rad Niazadeh () and Yangguang Shi ()
Additional contact information
Yuval Emek: Faculty of Data and Decision Sciences, Technion—Israel Institute of Technology, 3200003 Haifa, Israel
Ron Lavi: Faculty of Data and Decision Sciences, Technion—Israel Institute of Technology, 3200003 Haifa, Israel; Department of Economics, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom
Rad Niazadeh: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Yangguang Shi: Booth School of Business, University of Chicago, Chicago, Illinois 60637

Mathematics of Operations Research, 2024, vol. 49, issue 2, 880-900

Abstract: An online problem called dynamic resource allocation with capacity constraints ( DRACC ) is introduced and studied in the realm of posted price mechanisms. This problem subsumes several applications of stateful pricing, including but not limited to posted prices for online job scheduling and matching over a dynamic bipartite graph. Because existing online learning techniques do not yield vanishing regret for this problem, we develop a novel online learning framework over deterministic Markov decision processes with dynamic state transition and reward functions. Following that, we prove, based on a reduction to the well-studied problem of online learning with switching costs, that if the Markov decision process admits a chasing oracle (i.e., an oracle that simulates any given policy from any initial state with bounded loss), then the online learning problem can be solved with vanishing regret. Our results for the DRACC problem and its applications are then obtained by devising (randomized and deterministic) chasing oracles that exploit the particular structure of these problems.

Keywords: Primary: 68Q32; secondary: 68W27; online learning; stateful posted pricing; resource allocation (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.1375 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:880-900

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().