42006 - Advanced Topics in Algorithms and Complexity (TAAC)

The aim of this course is to highliht the joint use of algorithmics and complexity in the study of a particular reserch area. The course will be organized in two or three modules whose contents  will be decided every year in order to keep up to date with challenging research topics.  Each module will cover one of the select topics. Next year the course will consist of two modules covering the definitions and the fundamental tools for the following topics:

• Game theory: Congestion games
• Adversarial queueuing theory: Stability of networks and protocols

This course is divided in two modules covering different  topics in algorithmics and complexity. These topics are:

• Game Theory: Congestion games
• Adversarial queueuing theory: Stability of networks and protocols


The aim of this first module is to give an introduction to  Game theory, mainly oriented
to model congestion problems on communication networks. It is intended that the students will learn
some basic notions of Game Theory like strategic games, rational behaviour of players and Nash equilibrium.
The module is focused on the study of congestion games, the existence of Nash equilibria depending on
different type of users and networks. In the case of the existence of Nash equilibria, we present algorithms to
compute one of them and we also classify the computational complexity of this problem showing that it depends on the type of users and networks.

1. Strategic games.

- Definition and examples.
- Pure and Mixed Nash Equilibria.
- Rational behaviour of players.

2. Congestion games.

- Definition and examples.
- Computational problems: existence and computation of a Nash equilibrium.
- Different types of congestion games.

3. Unweighted congestion games
- Users without weights: all the packets have the same weight.
- Potential games: the existence of a pure Nash equilibrium.
- The relationship between potential and congestion games.
- The computation of a pure Nash equilibrium:
* Users with the same source and destination: polynomial time.
* Users with different sources and destinations: local search.

4. W eighted congestion games
- Users with weights: all the packets might have different weight.
- Cases without  pure Nash equilibrium.
- The existence of pure Nash equilibrium and the complexity of the problem in different types of networks.

Module: Stability of networks and protocols

The aim of the second module is to give an introduction to the analysis if the behaviour of communication network in worse case scenarios.  The course will introduce the main componentes of a communication network: network topology, scheduling policy and network traffic  and the tools used in the adversarial queueuing theory to model the packet traffic as an adversary.  The module will focus in the study of stability properties under different notions, depending on the components of the system.  Besides classifying several classic protocols (like LIFO, FIFO, SIS among others) from the point of view of their stability we will  also analyze the  problems of network universal stability and  network stability under a protocol.

 

At the end of each module, students must take a written exam that will basically consist of solving exercises like those studied along the course. However, each module teacher might ask for additional exercises or projects. The final mark will be the average obtained from the sum of the marks of the three modules.

·M.J. Osborne. An introduction to Game Theory. Oxford University Press, 2004.
·R.W. Rosenthal. A Class of games Possessing Pure-Strategy Nash Equilibria. International Journal on Game Theory, 1973.
· D. Monderer, L.S. Shapley. Potential Games. Games and Economic Behaviour, 1996.
· I. Milchtaich. Congestion Games with Player-Specific Payoff Functions. Games and Economic Behaviour 13, 11--124, 1996.
· A. Fabrikant, C. Papadimitriou, K. Talwar. The complexity of pure Nash equilibria. STOC 2004, 604--612,2004.
· D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronikolas, P. Spirakis. Selfish Unsplittable Flows. ICALP 2004, 645-657,2004.