Algorithmic Game Theory

You are here

Credits
6
Types
Specialization complementary (Advanced Computing)
Requirements
This subject has not requirements, but it has got previous capacities
Department
CS
As Computer Science struggles to understand the Internet and its capabilities, computer scientists are incorporating concepts and methodologies from Economics and Game Theory into their discipline. In the past decades, there has been a tremendous growth in research, centered around the following questions: What game-theoretic tools are applicable to computer systems? How far is the performance of a system from optimality due to the conflict of interests of its users and administrators? How can we design a system whose performance is robust with respect to the potential conflict of interests inside the system?

The course aims to tackle some of the fundamental problems at the interface of Computer Science and Game theory, with an emphasis on algorithms and computational complexity. Our main focus will be on algorithms for equilibria, the computational complexity of finding equilibria, the algorithmic tools in mechanism design for auctions, the stategic behavior models for large networks, and the price of anarchy. Incorporating also some notions from cooperative game theory.

Teachers

Person in charge

  • Maria Jose Serna Iglesias ( )

Others

  • Maria del Carme Alvarez Faura ( )

Weekly hours

Theory
2.5
Problems
1.5
Laboratory
0
Guided learning
0.5
Autonomous learning
8

Competences

Technical Competences of each Specialization

Advanced computing

  • CEE3.1 - Capability to identify computational barriers and to analyze the complexity of computational problems in different areas of science and technology as well as to represent high complexity problems in mathematical structures which can be treated effectively with algorithmic schemes.
  • CEE3.2 - Capability to use a wide and varied spectrum of algorithmic resources to solve high difficulty algorithmic problems.
  • CEE3.3 - Capability to understand the computational requirements of problems from non-informatics disciplines and to make significant contributions in multidisciplinary teams that use computing.

Generic Technical Competences

Generic

  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
  • CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.
  • CG5 - Capability to apply innovative solutions and make progress in the knowledge to exploit the new paradigms of computing, particularly in distributed environments.

Transversal Competences

Reasoning

  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.

Basic

  • CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.
  • CB8 - Capability to communicate their conclusions, and the knowledge and rationale underpinning these, to both skilled and unskilled public in a clear and unambiguous way.
  • CB9 - Possession of the learning skills that enable the students to continue studying in a way that will be mainly self-directed or autonomous.

Objectives

  1. Become acquainted with the main techniques and problems in the algorithmic game theory domain and identify their major properties.
    Related competences: CG1, CEE3.1, CEE3.2, CB8, CB9, CTR6,
  2. Examine conditions under which cooperation and antagonism appear. Perform an analysis and extract the fundamental properties of problems from different domains in order to assess the suitability of a game theoretical analysis and its limitations.
    Related competences: CG1, CG3, CEE3.1, CEE3.2, CEE3.3, CB6, CB9, CTR6, CG5,

Contents

  1. Introduction to Algorithmic game theory
    Centralized versus decentralized decisions. Games and Internet. Game types, strategies and equilibria.
  2. Strategic games and computational aspects of Nash equilibria
    Strategic games, pure and mixed strategies. Solution concepts. Pure Nash equilibria and the complexity of its computation. Pure Nash equilibria versus local optima: Potential games. Mixed strategies and Nash equilibria. The complexity of computing a Nash equilibria.
  3. Price of anarchy and price of stability
    Definitions. Social cost. Best and worst Nash equilibria. Network Games: utility-based resource allocation. Selfish routing and Congestion games. Network formation games. Other examples
  4. Cooperative game theory
    Cooperative and simple games. Types of coalition. Power indices. Examples: voting games, combinatorial games and influence games on social networks.
  5. Computational social choice
    The problem of aggregating preferences. Voting rules. Manipulation, control and bribery in voting systems.

Activities

Activity Evaluation act


Theory
28h
Problems
16h
Laboratory
0h
Guided learning
4h
Autonomous learning
56h

Final Exam

Theory questions and problem-solving exam
Objectives: 1 2
Week: 15 (Outside class hours)
Type: final exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
15h

Control 1

In class problem assignment
Objectives: 1 2
Week: 6
Type: problems exam
Theory
0h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Control 2

In class problem assignment

Week: 13
Type: problems exam
Theory
0h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Presentation of a research paper

Optional activity. Presentation of a scientific journal article describing a research topic in some of the topics covered in the course or in other related areas of interest to the student.
Objectives: 1 2
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Teaching methodology

There will be two kinds of classes: theoretical sessions and practical sessions. On average, two hours per week are dedicated to theory and one
hour per week to exercises. The teacher will allocate the hours in accordance to the subject matter.

The theory classes take the form of lectures in which the teacher sets out new concepts or techniques. Those are complemented with examples illustrating the introduced concepts. Sessions will consist of a presentation of the main topics of each content's item, mainly based in selected original research papers.
A high level of students' participation is expected at each session. Current lines of research in each topic will be discussed at the end of each topics' presentation.

The practical classes are used to carry out exercises in which students take an active part. Usually teachers set the exercises in advance. Students are
required to submit the exercises and then discuss the various solutions/alternatives in class.

Evaluation methodology

Grade = 20%(C1+C2)/2 + 40% FW + 40% FT


C1 , C2 = Graded in-class assignments. Each one is graded from 0 to 10.


FW = Paper presentation (graded from 0 to 10) in which each participant is required to present a research paper (previously assigned by the lecturer).
The presentation consists of:
3-5 minutes background on the topic of the paper, and motivation.
1-3 minute overview of the key ideas of the paper.
10 minutes presentation with most important details.
2-5 minutes conclusions and review of research problems or directions left in the paper.

FT = Final test graded from (0 to 10) including all the contents of AGT.

Bibliography

Basic:

Complementary:

Previous capacities

Basic knowledge of algorithm analysis methods (in particular asymptotic complexity).
Basic knowledge on algorithms. Linear Programming. Maximum flow. Local search. Graph and Network algorithms.
Basic knowledge on algebraic reasoning.
Basic knowledge on computational complexity, classes and reductions.

Addendum

Contents

There are no modifications to the contents of the teaching guide. No hi ha modificacions respecte als continguts de la guia docent. No hay modificaciones respecto a los contenidos de la guía docente.

Teaching methodology

There are no modifications to the methodology given in the teaching guide. The on-line classes will be complemented with voluntary activities that encourage participation in these classes and the assimilation of the topics of the course. No hi ha modificacions respecte a la metodologia de la guia docent. Les classes no presencial es complementaran amb activitats voluntàries que fomentin la participació en aquestes classes i l'assimilació dels continguts de l'assignatura. No hay modificaciones respecto a la metodología de la guía docente. Las clases no presenciales se complementarán con actividades voluntarias que fomenten la participación en estas clases y la asimilación de los contenidos de la asignatura.

Evaluation methodology

There are no modifications to the evaluation method. No hi ha modificacions respecte al mètode d'avaluació. No hay modificaciones al método de evaluación.

Contingency plan

In case of cancellation of the face-to-face teaching, the classes will continue on-line, in the same schedule, and they will be reinforced with communication tools that allow to maintain contact between students and between students and teachers in an agile way. The exams will be held in person, with delivery through the Racó and/or Atenea En cas de cancel·lació de tota activitat lectiva presencial les classes es continuaran de forma no presencial en el mateix horari i és reforçaran amb eines de comunicació que permetin mantenir el contacte entre els estudiants i entre estudiants i professors de forma àgil. Els exàmens es realitzaran de forma no presencial, amb entrega a través del Racó i/o d'Atenea. En caso de cancelación de toda actividad lectiva presencial las clases continuarán de forma no presencial en el mismo horario y se reforzarán con herramientas de comunicación que permitan mantener el contacto entre los estudiantes y entre estudiantes y profesores de forma ágil. Los exámenes se realizarán de forma no presencial, con entrega a través del Racó y/o de Atenea.