nips nips2004 nips2004-24 nips2004-24-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: David C. Parkes, Dimah Yanovsky, Satinder P. Singh
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 process (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 possibility 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 BayesianNash equilibrium. Our approach is empirically illustrated in the context of the dynamic allocation of WiFi connectivity to users in a coffeehouse. 1
[1] Eric Friedman and David C. Parkes. Pricing WiFi at Starbucks– Issues in online mechanism design. In Fourth ACM Conf. on Electronic Commerce (EC’03), pages 240–241, 2003.
[2] Matthew O. Jackson. Mechanism theory. In The Encyclopedia of Life Support Systems. EOLSS Publishers, 2000.
[3] Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for nearoptimal planning in large Markov Decision Processes. In Proc. 16th Int. Joint Conf. on Artificial Intelligence, pages 1324–1331, 1999. To appear in Special Issue of Machine Learning.
[4] Ron Lavi and Noam Nisan. Competitive analysis of incentive compatible on-line auctions. In Proc. 2nd ACM Conf. on Electronic Commerce (EC-00), 2000.
[5] Martin J Osborne and Ariel Rubinstein. A Course in Game Theory. MIT Press, 1994.
[6] David C. Parkes and Satinder Singh. An MDP-based approach to Online Mechanism Design. In Proc. 17th Annual Conf. on Neural Information Processing Systems (NIPS’03), 2003.
[7] M L Puterman. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, New York, 1994.