Prior-free online mechanisms for queueing with arrivals
- PDF / 456,507 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 164 Views
Prior-free online mechanisms for queueing with arrivals Sambuddha Ghosh1 · Yan Long2 · Manipushpak Mitra3 Received: 9 September 2019 / Accepted: 31 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Agents from a finite population arrive at various discrete times, and exit after they use a server for one period each. Each agent has a per-period cost of queueing, which constitutes his private information. Among direct mechanisms that are prior-free, i.e. independent of distributions of arrivals and costs, and online, i.e. charge only those present in the system, we characterize the class of dynamically strategy-proof mechanisms with least total waiting cost. The budget is balanced eventually under a mild condition on the arrival sequence, while a canonical mechanism that achieves budget balance in each period is also characterized under a stronger condition. Keywords Queueing with arrivals · Prior-free mechanism design · Online mechanism design · online VCG mechanism · Dynamically strategy-proof · Budget balance JEL Classification C44 · C78 · D47 · D82
We are grateful to Hervé Moulin for initiating the project with Mitra, and for offering helpful suggestions subsequently. We thank the associate editor and the referees for suggestions that greatly improved the paper. Seminar audiences at Boston University, Microsoft Research (New England), MIT, Seoul National University, Shanghai University of Finance and Economics, University of New South Wales, and ZEW Mannheim also gave valuable comments. In particular, suggestions from Jimmy Chan, Gabriele Gratton, Bart Lipman, Suresh Mutuswami, Juan Ortner, Ludovic Renou, Souvik Roy, Jay Sethuraman, Juuso Toikka, and Alexander Westkamp are gratefully acknowledged. Ghosh gratefully acknowledges the following research grants: National Natural Science Foundation of China Grant 71850410543, and SUFE Theoretical Economics Gaofeng II Discipline Innovation Project 2018110721.
B
Yan Long [email protected] Sambuddha Ghosh [email protected] Manipushpak Mitra [email protected]
1
The School of Economics, Shanghai University of Finance and Economics, Shanghai, China
2
The School of Economics, Huazhong University of Science and Technology, Wuhan, China
3
Economic Research Unit, Indian Statistical Institute, Kolkata, India
123
S. Ghosh et al.
1 Introduction In queueing problems agents wish to use a service facility, but have to wait their turn. Examples of this abound—ships waiting to load/unload cargo at a port, airlines waiting to use the runway for take-off/landing, researchers waiting to use a supercomputer, electric vehicles waiting to be re-charged at a power station, consumers waiting to be picked up by a ride-hailing service, and patients waiting for hospital beds. Our model of queueing with arrivals has the following features—(a) agents arrive at a service facility at various discrete points of time; (b) each agent requires one period of service, and exits permanently thereafter; (c) in each period the facility provides exactly one
Data Loading...
