CS 886: Multiagent Systems

Fall 2008
Schedule: Monday and Wednesday, 10:00-11:30
Room: MC 2036A

Site menu:

• Home
• Schedule
• Paper List
• Reviews
• Project Information
• News

Papers

Reference Text Book

• K. Leyton-Brown and Y. Shoham, Essentials of Game Theory: A Concise Multidisciplinary Introduction, Morgan and Claypool, 2008.

Introductory Papers

• Y. Shoham, Computer Science and Game Theory, Communications of the ACM, Volume 51, Issue 8, pp. 74-79, 2008
• R. Dash, N. Jennings, and D. Parkes, Computational Mechanism Design: A Call to Arms, IEEE Intelligent Systems, Volume 18, Number 6, pp. 40-47, 2003.
• H. Varian, Mechanism Design for Computerized Agents, Proceedings of USENIX Workshop on Electronic Commerce, New York, July, 1995.

Game Representations

• A. Jiang, K. Leyton-Brown, and N. Bhat, Action Graph Games, UBC CS Technical Report TR-2008-12, 2008
See also
• N. Bhat and K. Leyton-Brown, Computing Nash Equilibria of Action-Graph Games, Proceedings of 20th Conference on Uncertainty in Artificial Intelligence (UAI 2004), pp. 35-42, Banff, Canada, July 2004.
• M. Kearns, M. Littman, and S. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence (UAI 2001), Seattle, WA, pp. 253-260, August 2001.
See also
• M. Kearns, Graphical Games, Chapter 7 in Algorithmic Game Theory (eds. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani), Cambridge University Press, 2007.
• D. Koller and B. Milch, Multiagent influence diagrams for representing and solving games, Games and Economic Behavior, 45(1), p 181-221, 2003.

Equilibria and Computation

• V. Conitzer and T. Sandholm, New Complexity Results about Nash Equilibria. Games and Economic Behavior, Vol. 63, Issue 2, pp. 621-641, 2008.
• A. Gilpin and T. Sandholm, Lossless Abstraction of Imperfect Information Games. Journal of the ACM, Vol. 54, Number. 5, 2007.
• R. Porter, E. Nudelman, and Y. Shoham, Simple Search Methods for Finding a Nash Equilibrium, Games and Economic Behavior, Vol. 63, Issue 2. pp. 642-661, 2008.

Social Choice and Voting

• Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet, A Short Introduction to Computational Social Choice, Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-2007), LNCS, volume 4362, Springer-Verlag, January 2007. (Not for Presentation)
• C. Dwork, R. Kumar, M. Naor, D. Sivakumar, Rank Aggregation Methods for the Web, Proceedings of the 10th International Conference on the World Wide Web (WWW 2001), Hong Kong, pp. 613-622, 2001.
• A. Altman and M. Tennenholtz, Axiomatic Foundations for Ranking Systems, Journal of Artificial Intelligence Research, Vol. 31, pp. 473-495, 2008.
• V. Conitzer and T. Sandholm, Common Voting Rules as Maximum Likelihood Estimators, Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI-05), pp. 145-152, Edinburgh, Scotland, UK, 2005.
• A. D. Procaccia and J. S. Rosenschein, Junta Distributions and the Average-Case Complexity of Manipulating Elections, Journal of Artificial Intelligence Research, Volume 28, pp. 157-181, 2007.
• U Endriss, N Maudet, F Sadri, and F Toni, Negotiating Socially Optimal Allocations of Resources, Journal of Artificial Intelligence Research, Vol 25, pp. 315-348, 2006
• D. Abraham, A. Blum, and T. Sandholm, Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges, ACM Conference on Electronic Commerce (EC 2007), San Diego, 2007.

Mechanism Design and Auctions

• N. Nisan and A. Ronen, Algorithmic Mechanism Design, Games and Economic Behavior, Vol. 35, pp. 166-196, 2001.
• D. Lehmann, L O'Callaghan, and Y. Shoham, Truth Revelation in Approximately Efficient Combinatorial Auctions, Journal of the ACM, Vo. 49 Issue. 5, pp. 577-602, 2002.
• M. Benisch, N. Sadeh, and T. Sandholm, A Theory of Expressiveness in Mechanisms, Proceedings of the Twenty Third AAAI Conference, Chicago, IL, pp. 17-23, 2008. (See also CMU Technical Report CMU-CS-07-178, 2007).
• M. Yokoo, Y. Sakurai, and S. Matsubara, The Effect of False-name Bids in Combinatorial Auctions: New Fraud in Internet Auctions, Games and Economic Behavior, Volume 46, Issue 1, pp. 174-188, 2004.
• T. Sandholm, Algorithm for Optimal Winner Determination in Combinatorial Auctions, Artificial Intelligence, 135, pp. 1-54, 2002.
See also
• T. Sandholm, Optimal Winner Determination Algorithms, In Combinatorial Auctions (editors, P. Cramton, Y. Shoham and R. Steinberg), The MIT Press, Cambridge, MA, 2006.
• R. Cavallo and D. Parkes, Efficient Metadeliberation Auctions, Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI'08), Chicago, July 2008.
See also
• D. Parkes, Online Mechanism Design, In Algorithmic Game Theory (eds. Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani), Cambridge University Press, 2007.
• A. Goldberg, J. Hartline, A. Karlin, M. Saks, and A. Wright, Competitive Auctions, Games and Economic Behavior, 55, pp. 242-269, 2006.

Coalitions

• T. Rahwan and N. Jennings, An algorithm for distributing coalitional value calculations among cooperating agents, Artificial Intelligence, Vol. 171, Number. 8-9. pp. 535-567, 2007.
• G. Chalkiadakis and C. Boutilier, Bayesian Reinforcement Learning for Coalition Formation Under Uncertainty, Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004), New York, pp. 1090-1097, 2004.
• M. Zuckerman, P. Faliszewski, Y. Bachrach, and E. Elkind, Manipulating the Quota in Weighted Voting Games, Proceedings of the Twenty Third AAAI Conference (AAAI 2008), Chicago, IL, pp. 215-221, 2008.
• P. Dunne, S. Kraus, W. van der Hoek, and M. Wooldridge, Cooperative Boolean Games, Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), pp. 1015-1022, 2008.

Multiagent Learning

• Y. Shoham, R. Powers, and T. Grenager, If Multiagent Learning is the Answer, What is the Question?, Artificial Intelligence, Vol. 171, Number 7, pp. 365-377, 2007. (Not for presentation)
• R. Brafman and M. Tennenholtz, R-MAX: A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning, Journal of Machine Learning Research, Vol. 3, pp. 213-231, 2002.
• R. Brafman and M. Tennenholtz, Efficient Learning Equilibrium, Artificial Intelligence, Vol. 159, Number. 1-2, pp. 27-47, 2004.
• J. Hu and M. Wellman, Nash Q-Learning for General-Sum Stochastic Games, Journal of Machine Learning Research, Vol.4, pp. 1039-1069, 2003.
• M. Bowling and M. Veloso, Multiagent Learning with a Variable Learning Rate, Artificial Intelligence, Vol. 136, pp. 215-250, 2002.
• R. Powers, Y. Shoham, and T. Vu, A General Criterion and an Algorithmic Framework for Learning in Multiagent Systems, Machine Learning, Vol. 67, pp. 45-76, 2007.

Applications and Other Interesting Papers

• Y. Blum and J. Rosenschein, Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality, Proceedings of the Twenty Third AAAI Conference (AAAI 2008), Chicago, IL, pp. 24-29, 2008.
• J. Grossklags, N. Christin, and J. Chuang, Security Investment (failures) in Five Economic Environments: A Comparison of Homogenous and Heterogeneous User Agents, Workshop on the Economics of Information Security (WEIS 2008) , June, 2008.
• X. Zhao and E. Johnson, Information Governance: Flexibility and Control Through Escalation and Incentives, Workshop on the Economics of Information Security (WEIS 2008) , June, 2008.
• S. Koenig, C. Tovey, X. Zheng and I. Sungur. Sequential Bundle-Bid Single-Sale Auction Algorithms for Decentralized Control. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 1359-1365, 2007.
• K. Dresner and P. Stone, A Multiagent Approach to Autonomous Intersection Management, Journal of Artificial Intelligence Research, Vol 31, pp. 591-656, 2008
• P Paruchuri, J Pearce, J Marecki, M Tambe, Fernando Ordonez, and Sarit Kraus. Playing Games for Security: An Efficient Exact Algorithm for Solving Bayesian Stackelberg Games, Proceedings of the Seventh International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-2008), Estoril, Portugal, May 2008.
• R. Jurca and B. Faltings, Obtaining Reliable Feedback for Sanctioning Reputation Mechanisms, Journal of Artificial Intelligence Research, Vol 29, pp. 391-419, 2007.
• R. Lin, S. Kraus, J. Wilkenfeld and J, Barry. Negotiating with Bounded Rational Agents in Environments with Incomplete Information Using an Automated Agent, Artificial Intelligence Journal, 172(6-7):823-851, 2008.
• A. Petcu, B. Faltings and D. C. Parkes, M-DPOP: Faithful Distributed Implementation of Efficient Social Choice Problems, Journal of Artificial Intelligence Research, Volume 32, pages 705-755, 2008.
• S. Lahaie, D. Parkes, and D. Pennock, An Expressive Auction Design for Online Display Advertising, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI 2008), Chicago, pp. 108-113.
• Ad Auctions: Please see papers from the Fourth Workshop on Ad Auctions, Chicago, July 2008.

Copyright © 2008 Kate Larson | Design by Andreas Viklund