Foundations of Multi-Agent Systems

Owner	Bachelor Kunstmatige Intelligentie
Coordinator	F.R. Velazquez Quesada
Part of	Minor Kunstmatige Intelligentie, year 1Minor Logic and Computation, year 1Bachelor Kunstmatige Intelligentie, year 3Bachelor Bèta-gamma, major Kunstmatige Intelligentie, year 3Bachelor Future Planet Studies, major Kunstmatige Intelligentie, year 3

Course manual 2019/2020

Course content

A multi-agent system (MAS) is a system consisting of several autonomous entities, called agents, that interact with each other. This interaction can take many different forms: from the agents working on their own individual interests (competition) to them making collective decisions (e.g., voting or sharing goods). As such, MASs can be studied from many different perspectives. For example, while competitive interaction is paradigmatically studied in game theory, collective decision making is the main subject of (computational) social choice. Logical frameworks have been also developed for reasoning about MASs with the provided tools allowing us not only to represent diverse attitudes towards information (e.g., knowledge, beliefs, preferences and intentions, both for individuals and for groups) but also to represent the diverse actions that affect them (e.g., several forms of inference, different types of communication).

This course introduces basic tools for formal representations of interaction in MASs.

1. Game theory.

Non-cooperative game theory: games in normal form and in extensive form. Basic solution concepts in both cases (e.g., Nash equilibrium, backward induction).

2. Computational social choice.

Basics of voting (i.e., preference aggregation) and fair division (i.e., how to share divisible items).

3. Logical foundations.

Logics for representing preferences, and their use in describing solution concepts in game theory. Logics for coalitions and their use in describing group capabilities.

Study materials

Literature

• F. R. Velázquez-Quesada. Lecture notes on theoretical foundations of multi-agent systems. Current version available from http://bit.ly/33z4VNr, 2019.

• Optional: Yoav Shoham and Kevin Leyton-Brown. Multiagent Systems. Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009. Available online from http://www.masfoundations.org/download.html

• Complementary.

  * For the whole course: Michael Wooldridge, 'An Introduction to MultiAgent Systems' (2nd edition), Wiley, 2009. ISBN 978-0-470-51946-2. http://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/imas/IMAS2e.html

   

• * For game theory: K. Leyton-Brown and Y. Shoham. Essentials of Game Theory: A Concise Multidisciplinary Introduction. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers, 2008. ISBN 978-1-598-29593-1. doi: 10.2200/S00108ED1V01Y200802AIM003.

• * For computational social choice: F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors. 'Handbook of Computational Social Choice'. Cambridge University Press, USA, 2016. ISBN 978-1-107-06043-2.

Other

• Additional material will be posted online before its discussion. When available, slides will be posted online after the lecture.

Objectives

• use tools from game theory and computational social choice for representing basic multi-agent competitive and decision-making interactions
• use logical frameworks for representing and reasoning about preferences and coalitions in multi-agent systems.

Teaching methods

• Hoorcollege
• Laptopcollege
• Lecture
• Self-study

The course consists only of lectures (hoorcolleges). Some examples and exercises will be discussed during the lectures, but the students are expected to work on most of them on their own (homeworks).

Learning activities

Attendance

Programme's requirements concerning attendance (OER-B):

• For practical trainings and tutorials with assignments attendance is obligatory. The requirements for attendance might differ between courses and are stated in the course manual. When students do not meet the requirements for attendance, he or she cannot finish the course with a pass mark.
  

Assessment

Item and weight	Details
Final grade
0.5 (50%) Tentamen	Must be ≥ 5.5
0.5 (50%) Homeworks 1 through 6	Must be ≥ 5.5

Students have to hand in the answers to six homework assignments (typed in LaTeX and submitted electronically), which together will contribute to 50% of the final grade. A final exam will contribute to the remaining 50%. IMPORTANT: in order to approve the course, the student should get an approval grade (greater or equal than 5,5) for *both* (i) the average of the homeworks and (ii) the final exam.

Inspection of assessed work

Contact the course coordinator to make an appointment for inspection.

Assignments

A set of exercises will be posted each week (on Wednesday afternoon), and the students should submit their solutions (in groups of maximum two persons, with the groups fixed through the whole course) before noon of next Monday. Solutions must be typed up professionally (LaTeX) and submitted as a PDF file via Canvas. Solutions must be correct, but they also should be short and understandable.

Fraud and plagiarism

The 'Regulations governing fraud and plagiarism for UvA students' applies to this course. This will be monitored carefully. Upon suspicion of fraud or plagiarism the Examinations Board of the programme will be informed. For the 'Regulations governing fraud and plagiarism for UvA students' see: www.student.uva.nl

Course structure

Timetable

The schedule for this course is published on DataNose.

Additional information

• The course consists of only lectures (hoorcolleges).
• The course will be taught in English.
• Prior knowledge: students have completed the second year bachelor AI course on Computationele Logica, and have enough mathematical maturity to deal with formal frameworks. In particular, they are familiar with the basic ingredients of modal logic, epistemic logic and dynamic epistemic logic to model MAS scenarios.

Processed course evaluations

Below you will find the adjustments in the course design in response to the course evaluations.

Contact information

Coordinator

• F.R. Velazquez Quesada