Lecturer
Ariel Procaccia
email: arielpro@gmail.com
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
Bureaucracy
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
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 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