Aims: In this project, you will select a topic emerging from Economics, Game Theory, or Social Choice, you will study and implement algorithms for this topic, and report how they perform in practice.
Background: It is well known to Computer Scientists that it is not faster computers but it is better algorithms that have driven the success of computers. One of the key areas of investigation for computing has been the whole area of social choice. How is it that a collection of individuals with varying preferences over a set of options can lead to a general decision of the community over those same options. Sometimes we want to find a winner and sometimes an order over the options. Most notably this is what is done every time we vote in an election and there is much discussion about the correct and fair form voting that we should use. The archetypal result in this theory is Arrows’s impossibility theorem – that there is no fair voting system. A related concept is a study of autonomous agents taking part in a competition for resources. Here participants all have their own strategies rather than an ordering over options and we have to decide what will happen. This situation occurs whenever people or machines are fighting over rare resources, or trying to beat each other in a strategic game. The archetypal result would be that there is no sensible way to determine the best strategy for players in a multi-player multi-objective game – and this was first shown by Nash. It is clear that social choice and economics includes many and varied situations. Some available topics that this project might choose to concentrate on include (you could choose more than one):
Computation of Nash equilibria (two-player games, polymatrix games, or net coordination games).
Dynamics, like best response and fictitious play, in games (net coordination games, networks of complements, Schelling games).
Fair division of indivisible items.
Fair division of divisible goods (Cake cutting algorithms, Rent division).
Stable Matching Algorithms.
Matching markets.
Simulation and calculation of results in many voting like systems
Early Deliverables
Report: A general report on algorithms for economics social choice, finishing with a determination of the project topic or topics.
Report: A full formal description of the problem and the solution concept.
Report: Known algorithms on the topic. How they work?
Proof of concept: A program that generates a (small) instance of the problem(s) you are studying and checks whether a given solution is indeed correct.
Proof of concept: Simple greedy heuristics for the topic.
Implementation of a known algorithm on the topic that works on some toy-examples of the problem.
Final Deliverables
A program developped with proper software engineering techniques
A nice and easy to use GUI for the chosen topic that allows interesting experiments (the GUI and its functionalities depend on the topic).
The program should work on at least three special cases of the problem.
Implementation and comparison of different heuristics and standard algorithms.
Final report should contain a section on the outcomes of the experiments done and conclusions drawn about which algorithms seem suitable in different situations.
Suggested Extensions
A more careful theory report, including notions of problem hardness, or running time for the algorithms.
More involved algorithms for the problem.
In depth analysis of the algorithms for specific classes of instances.
Nice analysis options for your problem including an implementation in some Discrete Event Simulation framework
An interactive Web page allowing people to explore and understand your topic using examples and simulation.
Reading
The table of contents of the Handbook of Computational Social Choice is very useful to see what kinds of project you might want to do
This course on Algorithmic Game Theory is worth having a skim over. At least the list of titles.
There is also a good book on Algorithmic Game Theory
Nash equilibrium: The Nash Equilibrium Wiki page is nice as an introduction.
Stable Marriage: The Stable Marriage Wiki page is also nice as an introduction.
Some fun Youtube videos about matching – worth watching even if you do not take this project: video one, or video two.
A more technical introduction to Networks of Complements.
A more technical introduction to Schelling games.
A more technical introduction to Coordination Games on Graphs.
A more technical introduction to Fair Allocation of Indivisible Goods.
A (slightly) more technical introduction to Cake cutting algorithms.
A more technical introduction to Matching Markets
Prerequisites: CS2860 Algorithms and Complexity and a general interest in the mathematics of Computer Science and in algorithms, game theory, and economics. Reasonable programming skills.
