This site uses only proprietary and third party technical cookies. By continuing to browse the site you are agreeing to our use of cookies. I agree I want to find out more
Browse the Department site:
Browse the Teaching site:

Programme of Course "Non-cooperative networks"

Code:

DT0174

Type of course unit:

Master Degree in Computer Science curriculum NEDAS: Compulsory
Master Degree in Computer Science curriculum SEAS: Elective
Master Degree in Computer Science curriculum UBIDIS: Elective

Level of course unit:

Postgraduate Degrees

Semester:

1st semester

Number of credits:

Master Degree in Computer Science: 3 (workload 75 hours)

Teachers:

Guido Proietti (GuidodotProiettiatunivaqdotit)

1. Course Objectives

The course is focused on the algorithmic aspects of non-cooperative networks, where selfish agents own network components and influence through their rational but self-interested behaviour the quality of implemented solution. The set of topics analyzed ranges from the study of the equilibria space of classic network games, up to algorithmic mechanism design for classic network optimization problems.

2. Course Contents and learning outcomes (Dublin Descriptors)

Topics of the course include:

  • Strategic equilibria theory in Non-Cooperative Networks (NCN): Nash equilibria and dominant stratgy equlibria. Selfish routing, Network Design games, Network Creation games.
  • Implementation theory in NCN: Algorithmic mechanism design (AMD). AMD for some basic graph optimization problems: Shortest path, Minimum Spanning Tree, Shortest-path Tree

On successful completion of this course, the student should

  • By the end of this module students will be able to understand the difference between a canonical and a strategic distributed system.
  • The aim is to make the student capable of abstracting models and formal algorithmic problems from real (i.e. non-cooperative) distributed computational problems, and designing efficient algorithmic solutions.
  • Through the presentation and the comparison of different solutions to a given probelm, students will be guided to learn and to identify independently their most efficient solution.
  • The course will encourage the development of the following skills of the student: capability of formally presenting and modelling concrete problems, focusing on their main features and discarding the inessential ones.
  • The course aims to develop in graduate students competencies and abilities necessary in their future studies, especially with respect to doctoral studies on algorithmic topics.

3. Course Prerequisites

Knowledge of basic courses of discrete mathematcs and algorithms.

4. Teaching methods and language

Lectures

Language:English[info]

Reference textbooks

  • Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, Algorithmic Game Theory. Cambridge University Press. 2011.

5. Assessment Methods

Mid-term written examination, followed by a final oral examination, which, for those who performed successfully in the mid-term examination, will be restricted to the second part of the course.

Course information last updated on: 20 ottobre 2016, 13:54