Related Courses

General Information


Ariel Procaccia
Phone number: (0265)85778
Office: Ross 22 (floor -1)
Hours: Any time, but please send email or call first

Time + Place

Second Semester, Wednesday, 12:00-13:45, at Levine 8


2 credit points
Course number: 67686
Target audience: 3rd year BSc / MSc / PhD students in the School of CS and Engineering
Prior requirements: Algorithms (67504) and Computability (67521)
Course requirements: [scribe or project] and [take home exam]

Course Description

While much research in Artificial Intelligence uses heuristics as the modus operandi, other researchers tend towards analytical analysis. This course is meant to give an in-depth look at some of the most fascinating topics in Artificial Intelligence, approaching them from a mathematical perspective. A significant part of the course will focus, specifically, on multiagent systems: groups of (usually selfish, heterogeneous) agents that argue, negotiate, reach agreements, and cooperate. Game theoretic tools will be central to many of the models with which we will deal, but no prior knowledge of Game Theory will be assumed. In addition, prior knowledge in Artificial Intelligence is not required.


Projects should be carried out by students not listed as scribes. The deadline is 18.7.08. Here are the full instructions.

Take home exam

A link to the exam is available; detailed instructions can be found inside. The deadline is 31.8.08.

Finals grades

The following file contains the scribe, project, exam, and final grades for the course. The final grade is the average of the project/scribe grade and the exam grade. Note that I did not grade a hardcopy of the exam, but you can see your score for each individual question. The following file contains a concise and elegant solution to the exam (beware of minor typos in q4). If you feel you have been seriously wronged, you can contact me by email, but the grades are really very high already.

Lecture Notes

For scribes: Lecture notes must be prepared in LaTex. Here is a sample LaTex file and the definitions that go with it. You might also need a LaTex tutorial.

Lecture 1, 14.5.08: Alpha-Beta Pruning
Scribe: Aviv Zohar.

Lecture 2, 21.5.08: Robotic Motion 1 (Coverage)
Ref: Multi-Robot Forest Coverage
Scribes: Reshef Meir, Yoni Peleg and Nir Pochter

Lecture 3, 28.5.08: Robotic Motion 2 (Search)
Ref: Improved Analysis of D*
Scribes: Dana Attias, Yair Movshovitz and Keren Haas

Lecture 4, 4.6.08: Constraint Satisfaction Problems 1
Refs: A Survey of Tractable CSPs | From Local to Global Consistency
Scribes: Bracha Hod and Zvi Vlodavsky

Lecture 5, 11.6.08: Constraint Satisfaction Problems 2
Ref: A Sufficient Condition for Backtrack-Free Search
Scribes: Dan Friedman, Rivka Oster, and Noam Aigerman (due 2.7.08)

Lecture 6, 18.6.08: Social Choice 1
Ref: The Proof of the Gibbard-Satterthwaite Theorem Revisited
Scribes: Ezra Resnick and Ariel Imber

Lecture 7, 25.6.08: Social Choice 2
Refs: The Computational Difficulty of Manipulation an Election | Universal Voting Protocol Tweaks to Make Manipulation Hard
Scribes: Amit Goldstein, Roi Schwarz, and Yoav Wilf

Lecture 8, 2.7.08: Fair Division 1
Ref: An Envy-Free Cake Division Protocol
Scribes: Hila Weisman, Liron Mordechy and Dafna Hirshfeld

Lecture 9, 9.7.08: Fair Division 2
Refs: Contract Types for Satisficing Task Allocation: I Theoretical Results | On Maximal Classes of Utility Functions for Efficient One-to-One Negotiation | Reaching Envy-Free States in Distributed Negotiation Settings
Scribes: Adi Ben Yoash, Avishay Maya, and Gilad Friedman

Lecture 10, 23.7.08: Fair Division 3
Refs: The Communication Requirements of Efficient Allocations and Supporting Lindahl Prices | On Approximately Envy-Free Allocations of Indivisible Goods
Scribes: Yuval Vardi, Yosef Prat, and Assaf Weiner

Lecture 11, 30.7.08: Coalition Formation
Ref: Complexity of Constructing Solutions in the Core Based on Synergies Among Coalitions
Scribes: Michael Zuckerman and Na'ama Zohary