Mechanisms and Game Theory in Networks

You are here

Credits
6
Types
Specialization compulsory (Computer Networks and Distributed Systems)
Requirements
This subject has not requirements

Department
AC
Mail
The goal of this course is giving the student a background in the methodologies in the advanced design of mechanisms using non-lineal convex optimization and game theory. The program will cover from basic concepts related to convexity, convex optimization problems, Game Theory, Nash Equilibria, to applications of these methodologies to networking such as resource allocation, back-pressure models, power-control models compressive sensing, game theory in wireless networks, pricing models in networks, game theory in routing problems or incentives in P2P systems.

Teachers

Person in charge

  • Jose Maria Barceló Ordinas ( )

Weekly hours

Theory
4
Problems
0
Laboratory
0
Guided learning
0
Autonomous learning
7

Competences

Technical Competences of each Specialization

Computer networks and distributed systems

  • CEE2.1 - Capability to understand models, problems and algorithms related to distributed systems, and to design and evaluate algorithms and systems that process the distribution problems and provide distributed services.
  • CEE2.2 - Capability to understand models, problems and algorithms related to computer networks and to design and evaluate algorithms, protocols and systems that process the complexity of computer communications networks.
  • CEE2.3 - Capability to understand models, problems and mathematical tools to analyze, design and evaluate computer networks and distributed systems.

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.

Objectives

  1. Capacity to formulate a convex optimization problem
    Related competences: CEE2.3, CTR6,
  2. Capacity to apply convex optimization to networking problems.
    Related competences: CEE2.2, CEE2.1, CTR6,
  3. Capacity to understand what game theory is and how a game is solved.
    Related competences: CEE2.3, CTR6,
  4. Capacity to apply game theory to networking problems
    Related competences: CEE2.2, CEE2.1, CTR6,

Contents

  1. Convex Optimization basics
    Convex sets, convex functions, convex optimization problems (COP) and duality (Lagrange dual function, KKT optimality conditions), methods for solving COP's (General Descent Methods, Interior Point Methods)
  2. Convex Optimization Applications to networking
    Exxamples on Resource allocation in networks, back-pressure, Power control, Publish-subscribe in DTN, Compressive Sensing.
  3. Game Theory basics
    Strategic and Extensive Forms of a Game, Non cooperative Games (Nash pure and mixed equilibria, correlated equilibria), Cooperative Games (core of a game, Shapley values, Nash Arbitration scheme), cost-sharing (Braess Paradox, Price of Anarchy and Stability), Auctions.
  4. Game Theory Applications to Networking
    Wireless Networking games, Energy-Efficient Power Control games, pricing, P2P games

Activities

Convex Optimization basics

Theory
10
Problems
0
Laboratory
0
Guided learning
0
Autonomous learning
0
Objectives: 1
Contents:

Convex Optimization Applications to Networking

Theory
10
Problems
0
Laboratory
0
Guided learning
0
Autonomous learning
0
Objectives: 2
Contents:

Game Theory Basics

Theory
10
Problems
0
Laboratory
0
Guided learning
0
Autonomous learning
0
Objectives: 3
Contents:

Game Theory Applications to Networking

Theory
10
Problems
0
Laboratory
0
Guided learning
0
Autonomous learning
0
Objectives: 4
Contents:

Evaluations

Evaluations: exam and presentation from students
Theory
5
Problems
0
Laboratory
0
Guided learning
0
Autonomous learning
0

Studying materials and project's ralization

Theory
0
Problems
0
Laboratory
0
Guided learning
0
Autonomous learning
0

Teaching methodology

During the initial sessions of each topic, the main results will be explained in the blackboard. the student will solve some exercises to prove their skills in the topic. Finally, there will be some sessions devoted to discuss in the classroom models taken from research papers that apply the related topics.

Evaluation methodology

The evaluation is based on different activities

- Short projects and presentations in which the student has to deliver and defend the obtained results (P)
- A final exam (FE)

Each of the activities will be evaluated (0=
The final mark for the course (FM) will be:

FM= 0.60xP+0.4xFE

Where P=(1/N) x Sum (Pi) with i=1,...N

with Pi the projects and oral presentation mark. There will be a minimum of 2 practical projects and 1 oral presentation.

Bibliografy

Basic:

Web links

Previous capacities

None.