Timezone: »

Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes
Yuval Emek · Ron Lavi · Rad Niazadeh · Yangguang Shi

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #425

In this paper, a rather general online problem called \emph{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. As the existing online learning techniques do not yield vanishing-regret mechanisms for this problem, we develop a novel online learning framework defined over deterministic Markov decision processes with \emph{dynamic} state transition and reward functions. We then prove that if the Markov decision process is guaranteed to admit an oracle that can simulate any given policy from any initial state with bounded loss --- a condition that is satisfied in the DRACC problem --- then the online learning problem can be solved with vanishing regret. Our proof technique is based on a reduction to online learning with \emph{switching cost}, in which an online decision maker incurs an extra cost every time she switches from one arm to another. We formally demonstrate this connection and further show how DRACC can be used in our proposed applications of stateful pricing.

Author Information

Yuval Emek (Technion - Israel Institute of Technology)
Ron Lavi (Technion)
Rad Niazadeh (University of Chicago Booth School of Business)

Rad Niazadeh is an Assistant Professor of Operations Management at the University of Chicago Booth School of Business. He studies the interplay between algorithms, incentives and learning in online marketplaces and platforms. Prior to joining Booth, he was a Motwani postdoctoral fellow at Stanford University, Department of Computer Science, and a visiting faculty in the market algorithms group at Google Research NYC. He received his PhD in Computer Science from Cornell University. Rad has received the INFORMS Revenue Management and Pricing Dissertation Award (honorable mention), the Google PhD Fellowship in Market Algorithms, Stanford Motwani fellowship, and Cornell Jacobs fellowship.

Yangguang Shi (Technion - Israel Institute of Technology)

More from the Same Authors