Multiagent Systems: Spring 2006

Aims: Multiagent systems are systems consisting of several autonomous entities, called agents, that interact with each other to either further their own interests (competition) or in pursuit of a joint goal (cooperation). While classical Artificial Intelligence has concentrated on modelling (specific aspects of) single agents, the field of multiagent systems focusses on the interaction between different agents. This course will exemplify some of the core contributions to the theory of multiagent systems made by different disciplines, including logic, economics and computer science. It is an advanced course in the Master of Logic programme.

Lecturer: Ulle Endriss (ILLC, University of Amsterdam)
Examination: regular coursework + presentation of a paper at the end (details)
Timetable: Mondays 11am-1pm in I.001 (Diamantslijperij) and occasionally Fridays 3-5pm in P.016

This page will be updated throughout the semester, with links to the slides used in class, coursework assignments, and information on possible changes in the schedule. Check it regularly.

Syllabus: We will start with an overview of the MAS research area as a whole, but for most of the course we'll be concentrating on a small number of specific issues. Expect to learn about things such as negotiation, multiagent resource allocation, fair division, combinatorial auctions, mechanism design, and preference representation in combinatorial domains. While much of this originates in economics, we'll be discussing it mostly from a computational point of view. There's no specific background knowledge required to follow the course, other than what you might want to call "a certain mathematical maturity". The course will include a few introductory lectures on game theory and social choice.

References: There is no designated textbook for this course. The following papers give a good impression of the kind of problems that we'll be interested in throughout the semester:

C.H. Papadimitriou. Algorithms, Games, and the Internet. Proc. STOC-2001, ACM Press, 2001. Invited talk write-up.
J. Lang. Some Representation and Computational Issues in Social Choice. Proc. ECSQARU-2005, Springer-Verlag, 2005. Invited talk write-up. (alternative link)
Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

The book by Wooldridge can serve as a useful introduction to the area of multiagent systems as a whole (much of which we are not going to cover in this course):

M. Wooldridge. An Introduction to Multiagent Systems. Wiley, 2002.

Resources: The main conference in the area is AAMAS. Then there are many smaller conferences and workshops, and agent-related research also gets presented at the main AI conferences (IJCAI, ECAI, AAAI). Relevant journals include JAAMAS, AIJ, and JAIR. Generally useful sites for locating papers are DBLP and CiteSeer. JSTOR is good for some of the older economics papers. A useful mailing list is agents@cs.umbc.edu (join here). The European Network of Excellence AgentLink organises a regular summer school as well as various other activities.

Schedule: Classes will take place every Monday, unless specified otherwise on this website. By default, there is no class on Fridays, again, except specified otherwise (the Friday slot will be used for a few tutorials, for alternate dates for the lectures we miss due to holidays or me being away, and possibly for student paper presentations towards the end).

Week Content Coursework

6 February 2006
Introduction: This introductory lecture (slides, 4up) consists of two parts. In the first part, I have tried to give a broad overview of some of the main research directions in MAS. The textbook by Wooldridge and the collection edited by Weiss (both cited on slide 18) are good starting points to find out more about the field. Alternatively, you could also consult the following paper:

M. Wooldridge and N.R. Jennings. Intelligent Agents: Theory and Practice. Knowledge Engineering Review, 10(2):115-152, 1995. (authors' version)

In the second part of today's lecture, I have introduced the general problem of finding a "good" allocation of a given number of goods amongst a given number of agents. In a nutshell, in the remainder of the course we are going to be concerned with developing the rather vague ideas mentioned today in a rigorous manner.

13 February 2006
Social Choice and Welfare: This lecture (slides, 4up) has been an introduction to Social Choice Theory and Welfare Economics. In particular, I have introduced the concepts of a social welfare ordering (SWO) and that of a collective utility function (CUF), and we have discussed some of their properties. This line of work is relevant to MAS, because it provides us with well-defined metrics for assessing the quality of an allocation of resources negotiated by the agents in a given system. The lecture has concentrated on some of the fundamental results in the field, such as the representability of certain SWOs by means of CUFs and the axiomatisation of certain SWOs.

We have largely followed the first two chapters of the book by Moulin. The actual SWOs and CUFs introduced, and a few more, are listed in the "MARA Survey". This paper also discusses their relevance to multiagent resource allocation in some more detail than we have done in class.

H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988.

Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

Coursework #1
(Deadline: 20/02/2006)

20 February 2006
Game Theory: This lecture (slides, 4up) has been an introduction to Game Theory. More specifically, we have discussed non-cooperative strategic games with perfect information. We have defined the concepts of dominant strategies, pure Nash equilibria, and mixed Nash equilibria, and we have seen how to compute the mixed Nash equilibria of a simple game. Most books on Game Theory would cover the material of today's class. One that is particularly accessible is the textbook by Osborne:

M.J. Osborne. An Introduction to Game Theory. Oxford University Press, 2004.

Game Theory is relevant to MAS, because negotiating agents are naturally modelled as rational players in the game-theoretical sense. Importantly, we have seen an example for a stability-efficiency dilemma: the stable solution suggested by the game-theoretical analysis based on the rational interests of the individual agents is not the same as the solution that would be considered efficient (in this case, Pareto optimal) from a social point of view.
Coursework #2
(Deadline: 27/02/2006)

27 February 2006
Bilateral Negotiation: This lecture (slides, 4up) has been an introduction to modelling negotiation between two rational agents. We have introduced the Monotonic Concession Protocol (MCP) and the associated Zeuthen Strategy, and we have analysed the efficiency and the stability of the resulting negotiation mechanism. We have also seen that a very simple one-shot protocol achieves the same (even better) results as the intuitively appealing mechanism given by the MCP. Finally, we have briefly discussed ways of manipulating such protocols in the context of task-oriented domains by misinforming the other agent about the set of potential agreements.

The book by Rosenschein and Zlotkin is the main reference in this area. If you have difficulties getting hold of a copy, you may also try some of their related papers. The paper by Harsanyi explains how the Zeuthen Strategy may be derived from more fundamental postulates about the negotiation behaviour of rational agents.

J.S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.

J.C. Harsanyi. Approaches to the Bargaining Problem before and after the Theory of Games. Econometrica, 24(2):144-157, 1956.

Tutorial: There will be a tutorial on FRIDAY the 3rd of March. We are going to go through the solutions for the first two coursework assignments.

6 March 2006
Basic Auction Theory: This lecture (slides, 4up) has presented four basic protocols for running an auction to sell a single item to one of number of potential buyers. The main result discussed is the Revenue-equivalence Theorem, which states that, under certain conditions, all four protocols give the same expected revenue to the auctioneer. We have also seen that the second-price Vickrey auction, in particular, has very attractive properties from a game-theoretical point of view, although all four protocols are vulnerable to different kinds of manipulation. Here are links to the papers cited on slide 17:

W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. Journal of Finance, 16(1):8-37, 1961.

R.P. McAfee and J. McMillan. Auctions and Bidding. Journal of Economic Literature, 25:699-738, 1987.

T.W. Sandholm. Distributed Rational Decision Making. In G. Weiss (ed.), Multiagent Systems, MIT Press, 1999. (author's version)

In the second part of today's lecture I have introduced the papers I suggest as possible topics for your term paper (small changes in this list are still possible). Please have a look through this list and get in touch to discuss your interests. By the beginning of the second block everyone should have settled on a topic.
Coursework #3
(Deadline: 13/03/2006)

13 March 2006
Combinatorial Auctions: This lecture (slides, 4up) has been about combinatorial auctions. These are auctions where several goods get allocated amongst a number of bidders. We have concentrated on the computational and algorithmic aspects of combinatorial auctions. In particular, we have seen that winner determination is an NP-hard optimisation problem, but we have also seen how a combination of well-known search techniques from Artificial Intelligence together with domain-specific heuristics can often solve the problem in practice. From the cited literature, I particularly recommend reading the paper by Rothkopf et al. for an introduction and for a discussion of tractable subclasses of the general winner determination problem, and the review article by Sandholm for a discussion of search techniques and heuristics:

M.H. Rothkopf, A. Pekec, and R.M. Harstad. Computationally Manageable Combinational Auctions. Management Science, 44(8):1131-1147, 1998.

T.W. Sandholm. Optimal Winner Determination Algorithms. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (author's version)

20 March 2006
Mechanism Design: This lecture (slides, 4up) has been about the design of mechanisms for collective decision making that favour a particular desired outcome despite agents pursuing their individual interests. We have introduced the Vickrey-Clarke-Groves mechanism, which is a direct-revelation mechanism that makes reporting your true valuation a dominant strategy, and we have discussed this mechanism in the context of combinatorial auctions. Here are links to the introductory papers cited on slide 25:

L.M. Asubel and P. Milgrom. The Lovely but Lonely Vickrey Auction. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (authors' version)

H.R. Varian. Economic Mechanism Design for Computerized Agents. Proc. Usenix Workshop on Electronic Commerce, 1995. (author's version)

Coursework #4
(Deadline: 03/04/2006)

27 March 2006 NO CLASS (EXAM WEEK)

3 April 2006
Preference Representation: This lecture (slides, 4up) has been about preference representation in combinatorial domains. We have reviewed several alternative languages for representing the preferences of individual agents and discussed their expressive power and comparative succinctness. We have covered both utility functions and ordinal preference relations; the languages discussed include explicit representations, the k-additive form, weighted propositional formulas, and prioritised goals. Refer to the following papers for further details:

Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

J. Lang. Logical Preference Representation and Combinatorial Vote. Annals of Mathematics and Artificial Intelligence, 42(1-3):37-71, 2004.

Preference representation is relevant to MAS, because agents need to communicate their preferences to be able to make collective decisions. In combinatorial domains, in particular, concise forms of representation are crucial (for example, negotiation over n goods requires expressing preferences over 2ⁿ bundles).

10 April 2006
Bidding Languages This lecture (slides, 4up) has been about bidding languages for combinatorial auctions. These are languages for (cardinal) preference representation developed specifically for the purpose of transmitting the (declared) valuations of bidders in combinatorial auctions. We have discussed expressive power and succinctness results for different languages built from the basic operations of OR and XOR; and we have seen how dummy items can be used to express exclusiveness constraints without having to include XOR in the language. The excellent paper by Nisan gives an overview of the area:

N. Nisan. Bidding Languages for Combinatorial Auctions. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (author's version)

Coursework #5
(Deadline: 21/04/2006)

17 April 2006
Distributed Negotiation: This lecture (slides, 4up) has been about distributed approaches to negotiation in multiagent systems. We have first discussed the pros and cons of distributed and centralised (auction-based) approaches, respectively, and then briefly introduced the Contract Net protocol as a means of identifying potential deals in a multiagent system. Most part of the lecture has been devoted to the analysis of an abstract negotiation framework where agents can agree on multilateral deals over the exchange of bundles of resources in a distributed manner. The focus has been on understanding the relationship between the local view (what deals are agents going to negotiate, based on their individual preferences?) and the global view (how can we ensure that allocations evolve into a social optimum?). Refer to the following papers for further details:

Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

U. Endriss, N. Maudet, F. Sadri, and F. Toni. Negotiating Socially Optimal Allocations of Resources. Journal of Artificial Intelligence Research, 25:315-348, 2006.

(Class held on FRIDAY the 21st, because of Pasen.)

24 April 2006
Multiagent Resource Allocation: This lecture (slides, 4up) has given an overview of the Multiagent Resource Allocation (MARA) research area. As part of the specification of a MARA problem, we have discussed different types of resources, preference representation languages to specify the interests of individual agents, and social welfare measures as a means of describing what should be considered a good allocation. Under the heading of solution techniques for MARA problems, we have discussed centralised and distributed allocation procedures, complexity results, issues in mechanism design, and algorithm design for negotiation systems. We have also briefly discussed some typical application areas. This lecture has closely followed the MARA Survey:

Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.

This concludes the main "storyline" of the course. Note that we have already discussed most of the above topics in much more detail in previous lectures.

1 May 2006 NO CLASS (DAG VAN DE ARBEID)

8 May 2006 NO CLASS (AAMAS-2006)

15 May 2006
Papers at AAMAS-2006: In this lecture (slides, 4up) I have discussed some of the papers presented at last week's AAMAS conference. (Class held on FRIDAY the 19th.)
Email me a draft of your paper by 16/05/2006.

22 May 2006
Student Presentations: WEDNESDAY the 24th, 2-5.15pm, room P.327
Format: half an hour per talk (20-25 minutes + discussion); 15 minutes break after the third talk
Andi: Similarity Criteria for Issue Trade-offs in Negotiation (Faratin, Sierra, Jennings)
Bastiaan: Distributed Mechanism Design (Parkes, Shneidman)
Chris: Logic-based Preference Representation (Coste-Marquis, Lang, Liberatore, Marquis)
Joel: Complexity of Nash Equilibria (Papadimitriou et al.)
Jonathan: Merging Strategy-Proofness (Everaere, Konieczny, Marquis)
Karol: Agenda-based Negotiation (Fatima, Jennings, Wooldridge)

29 May 2006
NO CLASS (EXAM WEEK)
Deadline for submitting final papers: 09/06/2006

Week	Content	Coursework
6 February 2006	Introduction: This introductory lecture (slides, 4up) consists of two parts. In the first part, I have tried to give a broad overview of some of the main research directions in MAS. The textbook by Wooldridge and the collection edited by Weiss (both cited on slide 18) are good starting points to find out more about the field. Alternatively, you could also consult the following paper: M. Wooldridge and N.R. Jennings. Intelligent Agents: Theory and Practice. Knowledge Engineering Review, 10(2):115-152, 1995. (authors' version) In the second part of today's lecture, I have introduced the general problem of finding a "good" allocation of a given number of goods amongst a given number of agents. In a nutshell, in the remainder of the course we are going to be concerned with developing the rather vague ideas mentioned today in a rigorous manner.
13 February 2006	Social Choice and Welfare: This lecture (slides, 4up) has been an introduction to Social Choice Theory and Welfare Economics. In particular, I have introduced the concepts of a social welfare ordering (SWO) and that of a collective utility function (CUF), and we have discussed some of their properties. This line of work is relevant to MAS, because it provides us with well-defined metrics for assessing the quality of an allocation of resources negotiated by the agents in a given system. The lecture has concentrated on some of the fundamental results in the field, such as the representability of certain SWOs by means of CUFs and the axiomatisation of certain SWOs. We have largely followed the first two chapters of the book by Moulin. The actual SWOs and CUFs introduced, and a few more, are listed in the "MARA Survey". This paper also discusses their relevance to multiagent resource allocation in some more detail than we have done in class. H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, 1988. Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006.	Coursework #1 (Deadline: 20/02/2006)
20 February 2006	Game Theory: This lecture (slides, 4up) has been an introduction to Game Theory. More specifically, we have discussed non-cooperative strategic games with perfect information. We have defined the concepts of dominant strategies, pure Nash equilibria, and mixed Nash equilibria, and we have seen how to compute the mixed Nash equilibria of a simple game. Most books on Game Theory would cover the material of today's class. One that is particularly accessible is the textbook by Osborne: M.J. Osborne. An Introduction to Game Theory. Oxford University Press, 2004. Game Theory is relevant to MAS, because negotiating agents are naturally modelled as rational players in the game-theoretical sense. Importantly, we have seen an example for a stability-efficiency dilemma: the stable solution suggested by the game-theoretical analysis based on the rational interests of the individual agents is not the same as the solution that would be considered efficient (in this case, Pareto optimal) from a social point of view.	Coursework #2 (Deadline: 27/02/2006)
27 February 2006	Bilateral Negotiation: This lecture (slides, 4up) has been an introduction to modelling negotiation between two rational agents. We have introduced the Monotonic Concession Protocol (MCP) and the associated Zeuthen Strategy, and we have analysed the efficiency and the stability of the resulting negotiation mechanism. We have also seen that a very simple one-shot protocol achieves the same (even better) results as the intuitively appealing mechanism given by the MCP. Finally, we have briefly discussed ways of manipulating such protocols in the context of task-oriented domains by misinforming the other agent about the set of potential agreements. The book by Rosenschein and Zlotkin is the main reference in this area. If you have difficulties getting hold of a copy, you may also try some of their related papers. The paper by Harsanyi explains how the Zeuthen Strategy may be derived from more fundamental postulates about the negotiation behaviour of rational agents. J.S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994. J.C. Harsanyi. Approaches to the Bargaining Problem before and after the Theory of Games. Econometrica, 24(2):144-157, 1956. Tutorial: There will be a tutorial on FRIDAY the 3rd of March. We are going to go through the solutions for the first two coursework assignments.
6 March 2006	Basic Auction Theory: This lecture (slides, 4up) has presented four basic protocols for running an auction to sell a single item to one of number of potential buyers. The main result discussed is the Revenue-equivalence Theorem, which states that, under certain conditions, all four protocols give the same expected revenue to the auctioneer. We have also seen that the second-price Vickrey auction, in particular, has very attractive properties from a game-theoretical point of view, although all four protocols are vulnerable to different kinds of manipulation. Here are links to the papers cited on slide 17: W. Vickrey. Counterspeculation, Auctions, and Competitive Sealed Tenders. Journal of Finance, 16(1):8-37, 1961. R.P. McAfee and J. McMillan. Auctions and Bidding. Journal of Economic Literature, 25:699-738, 1987. T.W. Sandholm. Distributed Rational Decision Making. In G. Weiss (ed.), Multiagent Systems, MIT Press, 1999. (author's version) In the second part of today's lecture I have introduced the papers I suggest as possible topics for your term paper (small changes in this list are still possible). Please have a look through this list and get in touch to discuss your interests. By the beginning of the second block everyone should have settled on a topic.	Coursework #3 (Deadline: 13/03/2006)
13 March 2006	Combinatorial Auctions: This lecture (slides, 4up) has been about combinatorial auctions. These are auctions where several goods get allocated amongst a number of bidders. We have concentrated on the computational and algorithmic aspects of combinatorial auctions. In particular, we have seen that winner determination is an NP-hard optimisation problem, but we have also seen how a combination of well-known search techniques from Artificial Intelligence together with domain-specific heuristics can often solve the problem in practice. From the cited literature, I particularly recommend reading the paper by Rothkopf et al. for an introduction and for a discussion of tractable subclasses of the general winner determination problem, and the review article by Sandholm for a discussion of search techniques and heuristics: M.H. Rothkopf, A. Pekec, and R.M. Harstad. Computationally Manageable Combinational Auctions. Management Science, 44(8):1131-1147, 1998. T.W. Sandholm. Optimal Winner Determination Algorithms. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (author's version)
20 March 2006	Mechanism Design: This lecture (slides, 4up) has been about the design of mechanisms for collective decision making that favour a particular desired outcome despite agents pursuing their individual interests. We have introduced the Vickrey-Clarke-Groves mechanism, which is a direct-revelation mechanism that makes reporting your true valuation a dominant strategy, and we have discussed this mechanism in the context of combinatorial auctions. Here are links to the introductory papers cited on slide 25: L.M. Asubel and P. Milgrom. The Lovely but Lonely Vickrey Auction. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (authors' version) H.R. Varian. Economic Mechanism Design for Computerized Agents. Proc. Usenix Workshop on Electronic Commerce, 1995. (author's version)	Coursework #4 (Deadline: 03/04/2006)
27 March 2006	NO CLASS (EXAM WEEK)
3 April 2006	Preference Representation: This lecture (slides, 4up) has been about preference representation in combinatorial domains. We have reviewed several alternative languages for representing the preferences of individual agents and discussed their expressive power and comparative succinctness. We have covered both utility functions and ordinal preference relations; the languages discussed include explicit representations, the k-additive form, weighted propositional formulas, and prioritised goals. Refer to the following papers for further details: Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006. J. Lang. Logical Preference Representation and Combinatorial Vote. Annals of Mathematics and Artificial Intelligence, 42(1-3):37-71, 2004. Preference representation is relevant to MAS, because agents need to communicate their preferences to be able to make collective decisions. In combinatorial domains, in particular, concise forms of representation are crucial (for example, negotiation over n goods requires expressing preferences over 2ⁿ bundles).
10 April 2006	Bidding Languages This lecture (slides, 4up) has been about bidding languages for combinatorial auctions. These are languages for (cardinal) preference representation developed specifically for the purpose of transmitting the (declared) valuations of bidders in combinatorial auctions. We have discussed expressive power and succinctness results for different languages built from the basic operations of OR and XOR; and we have seen how dummy items can be used to express exclusiveness constraints without having to include XOR in the language. The excellent paper by Nisan gives an overview of the area: N. Nisan. Bidding Languages for Combinatorial Auctions. In P. Cramton et al. (ed.), Combinatorial Auctions, MIT Press, 2006. (author's version)	Coursework #5 (Deadline: 21/04/2006)
17 April 2006	Distributed Negotiation: This lecture (slides, 4up) has been about distributed approaches to negotiation in multiagent systems. We have first discussed the pros and cons of distributed and centralised (auction-based) approaches, respectively, and then briefly introduced the Contract Net protocol as a means of identifying potential deals in a multiagent system. Most part of the lecture has been devoted to the analysis of an abstract negotiation framework where agents can agree on multilateral deals over the exchange of bundles of resources in a distributed manner. The focus has been on understanding the relationship between the local view (what deals are agents going to negotiate, based on their individual preferences?) and the global view (how can we ensure that allocations evolve into a social optimum?). Refer to the following papers for further details: Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006. U. Endriss, N. Maudet, F. Sadri, and F. Toni. Negotiating Socially Optimal Allocations of Resources. Journal of Artificial Intelligence Research, 25:315-348, 2006. (Class held on FRIDAY the 21st, because of Pasen.)
24 April 2006	Multiagent Resource Allocation: This lecture (slides, 4up) has given an overview of the Multiagent Resource Allocation (MARA) research area. As part of the specification of a MARA problem, we have discussed different types of resources, preference representation languages to specify the interests of individual agents, and social welfare measures as a means of describing what should be considered a good allocation. Under the heading of solution techniques for MARA problems, we have discussed centralised and distributed allocation procedures, complexity results, issues in mechanism design, and algorithm design for negotiation systems. We have also briefly discussed some typical application areas. This lecture has closely followed the MARA Survey: Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaître, N. Maudet, J. Padget, S. Phelps, J.A. Rodríguez-Aguilar, and P. Sousa. Issues in Multiagent Resource Allocation. Informatica, 30:3-31, 2006. This concludes the main "storyline" of the course. Note that we have already discussed most of the above topics in much more detail in previous lectures.
1 May 2006	NO CLASS (DAG VAN DE ARBEID)
8 May 2006	NO CLASS (AAMAS-2006)
15 May 2006	Papers at AAMAS-2006: In this lecture (slides, 4up) I have discussed some of the papers presented at last week's AAMAS conference. (Class held on FRIDAY the 19th.)	Email me a draft of your paper by 16/05/2006.
22 May 2006	Student Presentations: WEDNESDAY the 24th, 2-5.15pm, room P.327 Format: half an hour per talk (20-25 minutes + discussion); 15 minutes break after the third talk Andi: Similarity Criteria for Issue Trade-offs in Negotiation (Faratin, Sierra, Jennings) Bastiaan: Distributed Mechanism Design (Parkes, Shneidman) Chris: Logic-based Preference Representation (Coste-Marquis, Lang, Liberatore, Marquis) Joel: Complexity of Nash Equilibria (Papadimitriou et al.) Jonathan: Merging Strategy-Proofness (Everaere, Konieczny, Marquis) Karol: Agenda-based Negotiation (Fatima, Jennings, Wooldridge)
29 May 2006	NO CLASS (EXAM WEEK)	Deadline for submitting final papers: 09/06/2006

Papers: During the second block you are supposed to write a paper about a recent result from the MAS literature and present your findings in a talk at the end of the semester. The main aim of your paper (and of your talk) should be to make an important recent result, related to the topics covered in the course, accessible to your class mates (and to me). Apart from that, your paper should also have some modest original content (don't try to develop a whole new theory of MAS in the space of half a semester). This could, for instance, be a new proof of an existing result, an improved presentation or formalisation of a particular model from the literature, pointing out an unexpected connection between two different lines of work, or casting an economics-related result in a fashion that is more accessible to "us" (people with a background in logic and/or AI). Any of the following papers would be a good starting point (and I'd also be happy to hear your own proposals). I've tried to link to the "official" versions of the papers wherever possible. From within the UvA network, you should be able to access all of the articles for free. Otherwise, try searching for the paper title or the authors.

S. Bouveret and J. Lang. Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity. Proc. IJCAI-2005, Morgan Kaufmann, 2005.
R.J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On Approximately Fair Allocations of Indivisible Goods. Proc. EC-2004, ACM Press, 2004.
P.E. Dunne. Extremal Behaviour in Multiagent Contract Negotiation. Journal of Artificial Intelligence Research, 23:41-78, 2005.
N. Nisan and A. Ronen. Algorithmic Mechanism Design. Games and Economic Behavior, 35(1-2):166-196, 2001.
V. Conitzer and T. Sandholm. Complexity of Mechanism Design. Proc. UAI-2002, Morgan Kaufmann, 2002.
X. Deng, C.H. Papadimitriou, and S. Safra. On the Complexity of Price Equilibria. Journal of Computer and System Sciences, 67(2):311-324, 2003.
C. Daskalakis, P.W. Goldberg, and C.H. Papadimitriou. The Complexity of Computing a Nash Equilibrium. Electronic Colloquium on Computational Complexity, Report TR05-115, 2005.
M. Yokoo, Y. Sakurai, S. Matsubara. Robust Combinatorial Auction Protocol against False-name Bids. Artificial Intelligence, 130(2):167-181, 2001.
M. Yokoo, Y. Sakurai, S. Matsubara. The Effect of False-name Bids in Combinatorial Auctions: New Fraud in Internet Auctions. Games and Economic Behavior, 46(1):174-188, 2004.
E. David, A. Rogers, J. Schiff, S. Kraus, and N.R. Jennings. Optimal Design of English Auctions with Discrete Bid Levels. Proc. EC-2005, ACM Press, 2005.
P. Winoto, G.I. McCalla, and J. Vassileva. Non-Monotonic-Offers Bargaining Protocol. Journal of Autonomous Agents and Multiagent Systems, 11(1):45-67, 2005.
S.S. Fatima, M. Wooldridge, and N.R. Jennings. An Agenda-based Framework for Multi-issue Negotiation. Artificial Intelligence, 152(1):1-45, 2004.
P. Faratin, C. Sierra, and N.R. Jennings. Using Similarity Criteria to Make Issue Trade-offs in Automated Negotiations. Artificial Intelligence, 142(2):205-237, 2002.
X. Zhang, V. Lesser, and R. Podorozhny. Multi-Dimensional, MultiStep Negotiation for Task Allocation in a Cooperative System. Journal of Autonomous Agents and Multiagent Systems, 10(1):5-40, 2005.
D.C. Parkes and J. Shneidman. Distributed Implementations of Vickrey-Clarke-Groves Mechanisms. Proc. AAMAS-2004, IEEE Press, 2004.
P. Everaere, S. Konieczny, and P. Marquis. On Merging Strategy-Proofness. Proc. KR-2004, AAAI Press, 2004.
M.S. Pini, F. Rossi, K.B. Venable, T. Walsh. Aggregating Partially Ordered Preferences: Impossibility and Possibility Results. Proc. TARK-2005, National University of Singapore, 2005.
S. Coste-Marquis, J. Lang, P. Liberatore, and P. Marquis. Expressive Power and Succinctness of Propositional Languages for Preference Representation. Proc. KR-2004, AAAI Press, 2004.
P.J. Modi, W.-M. Shen, M. Tambe, and M. Yokoo. ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees. Artificial Intelligence, 161(1-2):149-180, 2005.