TOPICS IN COMPUTER SCIENCE IV: COMPUTATIONAL SOCIAL CHOICE
2016/2017, Semester 2
School of Computing (Computer Science)
Modular Credits: 4
Algorithmic Game Theory
Recent years have seen a dramatic rise in the use of algorithms for solving problems involving strategic decision makers. Deployed algorithms now assist in a variety of economic interactions, from kidney exchange and airport security, to allocating computational resources and dividing rent. We will explore foundational topics in computational social choice. Our exploration will begin from seemingly simple group decision making problems: selling items at an auction, dividing rent among roommates, allocating computational resources and more. These problems all require an interdisciplinary approach, combining ideas from economics, game theory and algorithmic analysis.
A good knowledge of algorithms and probability is required. Students who have taken courses equivalent to the ones below should be fine.
CS3230 Design and Analysis of Algorithms and (ST2334 Probability and Statistics or ST2131 Probability)
1. Handbook of Computational Social Choice by Brandt et al., available as a free downloadble PDF
2. Algorithmic Game Theory edited by Nisan et al., also available as a free PDF online.
3. Computational Aspects of Cooperative Game Theory, by Chalkiadakis et al., available free online.
Assessment consists of four components:
(i) Course participation: 10% (scribing/presenting/classroom participation)
(ii) Written assignments: 20% (4-5 written homework assignments)
(iii) Midterm: 30% (a written exam)
(iv) Project: 40% (an academic project to be conducted throughout the course, with a theoretical/empirical components; each student will submit a short paper at the end of the course describing the results)
More information on course project
Students will complete a small research project; the idea is to work throughout the semester on a topic related to the course material that will ideally result in publishable work.
Some examples of course projects include:
a. Implement an algorithm shown in class and analyse its performance on data
b. Expand on existing theoretical models and extend their theoretical results
c. Summarize the results of a few research papers, showing their main contributions and explain their analysis
d. Suggest a new problem domain in the field of computational social choice/fair division/mechanism design and prove a few preliminary results.
Students will present a 2 page summary mid-semester (a white paper showing progress), and a 4 page paper in publication format at the end of the semester.
Variable, depend on the choice of topics or departmental approval.
Workload Components : A-B-C-D-E
A: no. of lecture hours per week
B: no. of tutorial hours per week
C: no. of lab hours per week
D: no. of hours for projects, assignments, fieldwork etc per week
E: no. of hours for preparatory work by a student per week