Quicklinks
Course overview
Prerequisites
Brief schedule
Grading
Reading
Expectations
A slightly fancier introduction
Paper presentation
Project
Acknowledgements
Course overview
- This is a research-oriented seminar course on the theory and application of computational techniques and computational thinking in preference representation and aggregation. Applications include but not limited to:
- voting
- fair division
- rating systems
- recommender systems
- learning to rank
- Instructor: Lirong Xia (xial@cs.rpi.edu). Please call me Lirong.
- Time: Monday Thursday 12:00 pm-1:50 pm
- Location: CARNEG 206
- Office hours: by appointment
Prerequisites
- A qualified student should have taken undergraduate-level courses on
- Linear algebra
- Algorithm design (e.g. CSCI-2300 Introduction to Algorithms)
- Probability or statistics
- One of the following:
- Artificial Intelligence (e.g. CSCI-4150 Introduction to Artificial Intelligence)
- Machine learning (e.g. CSCI-4100/6100 Machine and Computational Learning)
- Optimization
- Microeconomics theory
- A student with strong backgrounds and skills in mathematics, computational complexity theory, algorithm design, or statistics will be likely to enjoy the course (especially working on your project). If you are unsure about your qualification please contact me.
Brief schedule
-
The course will have the following three parts:
- I will give lectures on basic concepts in social choice, game theory, and mechanism design.
- Students present and discuss selected papers. Here is a list of papers (available soon). Please contact me early to discuss your interests in presentation.
- Student research project presentation. A list of potential topics can be found here (available soon). You are also encouraged to work on your own topic related to the course. Please contact me early to discuss your research interests and appropriate topics. Tentative project due dates are
- 10-28 before class: project proposals (2 pages max)
- 12-7 before noon: final report due
- We will mainly use piazza for announcement and discussions. Please sign up here.
Grading
- Notice: The grade is largely determined by the quality of paper presentation and the project. One effective way to improve the quality (and thus your final grades!) is to discuss with me EARLY. Don't wait until the last minute.
Reading
There is no textbook. The best article for comprehensive reading is the following survey.
Also you may find the following books useful, especially the first by Shoham and Leyton-Brown (thus SLB). All of them have free non-printable versions for download.
- Y. Shoham and K. Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, 2009.
- N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, Algorithmic Game Theory, 2007.
- M. J. Osborne and A. Rubinstein, A Course in Game Theory, 1994.
Expectation
- After the course a student should learn main principles and techniques in computational social choice, and will be able to understand and design new systems to handle preferences. A good final project should be either
- a practical system on preference handling, or
- a publishable article at a good academic conference/journal.
- Teamwork in small groups is encouraged. However, combining the course project with your own research interests is even better.
A slightly fancier introduction
In many situations agents have conflicting preferences but have to make a joint decision. Social choice theory studies the representation and aggregation of individual preferences. It dates back to the 4th century B.C., and prospered since the 18th century.
In the past few decades, rapid developments in computer science and internet technologies have brought fresh air to social choice by introducing not only many new applications, but also a computational point of view on preference representation and aggregation. Computational social choice emerged as a result and has attracted much attention of researchers in artificial intelligence, economics, and theory of computation.
More information about computational social choice can be found here.
Similar courses at:
Paper presentation
Each team must give 2 presentations on selected topics. A topic may contain one or more related papers.
How to apply for topics (papers)?
Send me an email with a full order over all topics. (You can give a full order over a subset of topics, but then randomization will be used to determine the rest of your preferences. So it is always better to give a full order).
After all teams submit their preferences, we will use a balanced sequential allocation mechanism (c.f. Harvard Business School mechanism) to assign the slots. Suppose we have k teams (and 2k topics to assign). Let T1 denote the earliest team to report preferences, T2 denote the second earliest, etc.
- The first k papers will be assigned in the following way: for each i = 1 to k, assign to Ti the paper that (1) is not yet assigned, and (2) on top of Ti's preferences (among all unassigned papers)
- The remaining k papers will be assigned in the following way: for each i = k to 1, assign to Ti the paper that (1) is not yet assigned, and (2) on top of Ti's preferences (among all unassigned papers)
So the order for teams to "choose" papers is: (T1, T2,...Tk, Tk, Tk-1,...T1)
If a team only contains one student, then the team does not need to choose a second paper.
Each paper is initially assigned a time. After all papers are assigned, you can use Piazza to "trade" the time with other classmates, but only do it when you feel necessary.
Hints: the earlier you submit your preferences the higher possibility you can pick your favorite topic.
How to read a paper?
At least you should ask yourself the following two types of quesitons
Basic questions:
- What is the problem the authors tried to address?
- Why we want to study this problem? How general it is?
- How was the problem addressed?
Advance questions:
- Appreciate the work: what is the main contribution? Why it is non-trivial?
- Critical thinking: anything you are not very satisfied with? Can you do better?
More general reading question can be found here. Prof. Michael Mitzenmacher has a nice blog on paper reading.
How to prepare reading questions?
coming soon
How to give a presentation?
coming soon
How to lead a discussion?
coming soon.
Project
Deadlines
- 10-28 before class: project proposals (2 pages max)
- 12-7 before noon: final report due
Acknowledgements
Thanks Felix Brandt, Yiling Chen, Ulle Endriss, Vincent Conitzer, David Parkes, Ariel Procaccial, Sven Seuken, Yi Zhang for offering tremendous helps on developing the course!