Felix Brandt

Faculty of Informatics,TUM

Paul Goldberg

Dept. of Computer Science, Oxford University

Computational Social Choice (PDF)

Abstract:

Over the past few years there has been a lively exchange of ideas between computer science, in particular theoretical computer science and artificial intelligence, on the one hand and economics, in particular game theory and social choice, on the other. This exchange goes in both directions and has produced active research areas such as algorithmic game theory and computational social choice.

Social choice theory concerns the formal analysis and design of methods for aggregating possibly conflicting preferences such as in voting, assignment, or matching problems. Much of the work in classic social choice theory has focused on results concerning the formal possibility and impossibility of aggregation functions that combine desirable properties. 

This tutorial will provide an overview of central results in social choice theory with a special focus on axiomatic characterizations as well as computational aspects.

While some aggregation functions can be easily computed, others have been shown to be computationally intractable (e.g., NP-hard or #P-hard).

Topics to be covered in this tutorial include

 (i) rational choice theory,

 (ii) Arrow's impossibility theorem,

 (iii) tournament solutions (such as the top cycle, the uncovered set, the Banks set, or the tournament equilibrium set), and

 (iv) randomized social choice functions.

The overarching theme will be escape routes from negative results such as Arrow's impossibility theorem.

Algorithmic Game Theory (PDF)

Abstract:

Game theory studies mathematical models that aim to predict the outcome of interactions amongst self-interested entities.

A "solution concept" (such exact or approximate Nash equilibrium) is a model of the outcome of an interaction.

Some solution concepts appear to be hard to compute, an aspect that calls into question their realism. In the first half of this tutorial I will provide an overview of the alternative notions of computational hardness that are relevant for game-theoretic solution concepts.

For example, the complexity classes PPAD and PLS turn out to be relevant, since these computational challenges are frequently total search problems that belong to NP. I will discuss some of the open problems.

In cases where a solution can be found in polynomial time, it may still be asked whether there exist "natural" decentralised algorithms that find a solution. This is because a solution concept arguably remains unrealistic if it can be efficiently computed, but only using a highly centralised algorithm. In the second half of the tutorial I will present some results on learning dynamics for equilibrium computation, and also mention recent work on communication complexity and query complexity.