Approximately Efficient Online Mechanism Design
Abstract
Online mechanism design (OMD) addresses the problem of sequential decision making in a stochastic environment with multiple self-interested agents. The goal in OMD is to make value-maximizing decisions despite this self-interest. In previous work we presented a Markov decision pro- cess (MDP)-based approach to OMD in large-scale problem domains. In practice the underlying MDP needed to solve OMD is too large and hence the mechanism must consider approximations. This raises the pos- sibility that agents may be able to exploit the approximation for selfish gain. We adopt sparse-sampling-based MDP algorithms to implement - efficient policies, and retain truth-revelation as an approximate Bayesian- Nash equilibrium. Our approach is empirically illustrated in the context of the dynamic allocation of WiFi connectivity to users in a coffeehouse.
Cite
Text
Parkes et al. "Approximately Efficient Online Mechanism Design." Neural Information Processing Systems, 2004.Markdown
[Parkes et al. "Approximately Efficient Online Mechanism Design." Neural Information Processing Systems, 2004.](https://mlanthology.org/neurips/2004/parkes2004neurips-approximately/)BibTeX
@inproceedings{parkes2004neurips-approximately,
title = {{Approximately Efficient Online Mechanism Design}},
author = {Parkes, David C. and Yanovsky, Dimah and Singh, Satinder P.},
booktitle = {Neural Information Processing Systems},
year = {2004},
pages = {1049-1056},
url = {https://mlanthology.org/neurips/2004/parkes2004neurips-approximately/}
}