CPSC 689 - Special Topics in Multi-Agent Systems
Spring 2006
Professor: Dr. Thomas R. Ioerger
Office: 322C Bright Bldg.
Phone: 845-0161
email: ioerger@cs.tamu.edu
office hours: make appointment by email
Meeting: Tues/Thurs, 1:30-3:00, 320 Bright
Course Web Page: http://www.cs.tamu.edu/faculty/ioerger/cs689-spring06/index.html
Prerequisites: CPSC 625 (AI), CPSC 631 (Programming Environments in AI)
Textbooks
There will be no textbook used. The course will be based on research
papers that can be printed out.
For background material, here are some good textbooks on agents:
- Wooldridge, M. (2002). An Introduction to Multiagent Systems. Wiley.
- Ferber, J. (1999). Multi-Agent Systems. Addison-Wesley.
- Weiss, G. (1999). Multi-Agent Systems. MIT Press.
- Bradshaw, G. (1997). Software Agents. AAAI Press.
- Huhns, M. and Singh, P. (1998). Reading in Agents. Morgan Kaufmann.
- Wooldridge, M. and Rao, A. (1999). Foundations of Rational Agency. Applied Logic Series, Vol. 14, Kluwer.
- Wooldridge, M. (2000). Reasoning about Rational Agents. MIT Press.
Goals of this Course
To learn about extended topics in Multi-Agent Systems, including
multi-agent interactions, cooperation, and distributed
decision-making. Two focal themes will be: utility-maximization for
self-interested agents, and coordination through market-based
mechanisms.
- Game Theory, Strategic Decision-Making in Competitive Environments
- Negotiation
- Auctions (market-based models)
- Coalition Formation
- Voting (consensus mechanisms)
Assignments, Projects, Exams, and Grading
The primary work for the course will consist of reading and discussing
journal papers from the research literature. Students will have to
give presentations and lead discussions on 2 papers from a selected
list. The grade will be based on the quality of the presentations
(60%) and class participation (40%).
Schedule:
The schedule is presented as weekly topics. Each week will consist of a
student-presentation on Tues, followed by a class discussion on Thurs.
Tues, Jan 24: Sandholm (1999)
Tues, Jan 31: Zlotkin and Rosenschein (1989) (negotiation); Sandholm and Lesser (2002) (leveled commitments; see also: Sandholm, Sikka, Norden (1999))
Tues, Feb 7:
Sandholm and Lesser (1997)
Tues, Feb 14:
Sandholm et al. (1999)
Tues, Feb 21:
Shehory and Kraus (1998)
Tues, Feb 28: payoff distribution:
Kraus, Shehory and Taase (2004);
Zlotkin and
Rosenschein (1994)
Tues, Mar 7: combinatorial auctions: Walsh and
Wellman, 1998; Walsh,
Wellman, and Ygge, 2000; Sandholm,
Suri, Gilpin, and Levine, 2002
Tues, Mar 14: (Spring Break)
Tues, Mar 21: MDPs: Russell and Norvig, pp. 613-628, Littman et al. (complexity), Littman (Markov games)
Tues, Mar 28: Boutilier, Brafman, and Geib (1997) (MDPs and planning)
Tues, Apr 4: Nair and Tambe (2005) (hybrid BDI-POMDP)
Tues, Apr 11: Gmytrasiewicz and Durfee (2001), Gmytrasiewicz and Durfee (2000) (recursive modeling method, RMM)
Tues, Apr 18: Sen and Sekaran (1998) (learning coordination knowledge)
Tues, Apr 25: Ephrati and Rosenschein (1996) (deriving consensus, Clarke tax)
References:
- Sandholm, T. (1999). Distributed Rational Decision Making. in
Multi-Agent Systems (chapter 5). G. Weiss, ed. MIT Press: Cambridge,
MA.
- Sen, S. and Sekaran, M. (1998). Individual learning of
coordination knowledge. Journal of Experimental & Theoretical
Artificial Intelligence, 10:333-356.
- Zlotkin, G. and Rosenschein, J.S. (1989).
Negotiation and Task Sharing Among Autonomous Agents in Cooperative Domains.
IJCAI, 912-917.
- Sandholm, T. and Lesser, V. (2002). Leveled-commitment
contracting: A backtracking instrument for mulitagent systems. AI
Magazine, 23(3):89-100.
- Sandholm, T., Sikka, S., and Norden, S. (1999).
Algorithms for optimizing leveled commitment contracts.
IJCAI, 535-540.
- Sandholm, T., Larson, K., Andersson, M., Shehory, O., and Tohme,
F. (1999). Coalition Structure Generation with Worst Case
Guarantees. Artificial Intelligence, 111(12) , 209-238.
- T. Sandholm and V. R. Lesser. Coalitions among computationally bounded
agents. Artificial Intelligence, 94(1-2):99-137, 1997.
- Shehory, O., and Kraus, S. 1998. Methods for task allocation via agent
coalition formation. Artificial Intelligence, 101(1-2):165-200.
- Zlotkin, G., and Rosenschein, J.S. (1994), "Coalition, Cryptography, And Stability: Mechanisms For Coalition Formation In Task Oriented Domains", Proceedings of the Twelfth National Conference on Artificial Intelligence, pp. 432-437.
- Kraus, S. and Shehory, O. and Taase, G. (2004). The Advantages of
Compromising in Coalition Formation with Incomplete Information.
Third International Joint Conference on Autonomous Agents and
Multiagent Systems, pp. 588-595.
- Walsh, W. and Wellman, M. (1998). A market protocol for decentralized task
allocation. Proceedings of the Third International Conference on
Multi-Agent Systems, 325-332.
- Walsh, W.E., Wellman, M.P., and Ygge, F. (2000). Combinatorial
auctions for supply chain formation. Proceedings of ACM Conference
on Electronic Commerce, 260-269.
- Sandholm, T., Suri, S., Gilpin, A. and Levine, D. (2002). Winner
determination in combinatorial auction generalizations. Proceedings
of the First International Joint Conference on Autonomous Agents and
Multiagent Systems, 69-76.
- Boutilier, C., Brafman R.I., and Geib C. (1997). Prioritized goal
decomposition of Markov decision processes: Toward a synthesis of
classical and decision theoretic planning. Proceedings of the
15th International Joint Conference on Artificial Intelligence,
1156-1162.
- Gmytrasiewicz, P.J., and Durfee, E.H. (2001). Rational
communication in multi-agent environments. Autonomous Agents and
Multi-Agent Systems, 4:233-272.
- Gmytrasiewicz, P.J., and Durfee, E.H. (2000). Rational
coordination in multi-agent environments. Autonomous Agents and
Multi-Agent Systems, 3:319-350.
- Nair, R. and Tambe, M. (2005). Hybrid bdi-pomdp framework for
multiagent teaming. Journal of AI Research, 23:367-413.
- Ephrati, E. and Rosenschein, J. (1996). Deriving consensus in
multiagent systems. Artificial Intelligence, 87:21-74.
Other Links
- weblog discussion on complexity of finding Nash equilibria
-
Conitzer and Sandholm (2002). Complexity Results about Nash Equilibria.
-
Sandholm,
Gilpin, and Conitzer (2005). Mixed-Integer Programming Methods for
Finding Nash Equilibria.
- for basic background on Linear Programming, read Ch. 29 of 2nd
ed. of Introduction to Algorithms by Cormen, Leiserson, Rivest,
and Stein
- Interior Point Methods
- Lemske-Howe
method for finding mixed Nash equilibria
- Nudelman
and Shoham (2005) paper on heuristic search for Nash equilibria
- AI
Magazine article on Anytime Algorithms by Shlomo Zilberstein
(1995)
-
Approximation Algorithms for NP-hard Optimization Problems
- other classic papers on planning under uncertainty: Hanks and McDermott (1994), Blythe (1999)
- Jim, K. and Giles, L. (2000). Talking Helps: Evolving Communicating Agents for the Predator-Prey Pursuit Problem. Artificial Life, 6:237-254.