To access the course content, knowledge of the basics of probability, graph theory, linear programming, and duality theory is required.

Per l'accesso ai contenuti del corso si richiede la conoscenza di nozioni di probabilità, teoria dei grafi, programmazione lineare e teoria della dualità.

The course aims to provide an introduction to Algorithmic Game Theory: a cutting-edge discipline born at the intersection of Game Theory, Algorithm Theory, and Computational Complexity. The course will have a distinct mathematical focus, aiming to study the inefficiency of equilibrium solutions in various non-cooperative games that model a wide range of application scenarios of interest.

Il corso vuole fornire un'introduzione alla Teoria Algoritmica dei Giochi: una disciplina d'avanguardia, nata dall'intersezione tra Teoria dei Giochi e Teoria degli Algoritmi e della Complessità Computazionale. Il corso avrà un taglio marcatamente matematico e volto allo studio dell'inefficienza di soluzioni di equilibrio in vari giochi non cooperativi che modellano svariati scenari applicativi di interesse.

Knowledge and understanding: To develop knowledge of non-cooperative game models and the degree of (in)efficiency achieved by equilibrium solutions.

Applying knowledge and understanding: To be able to extend the acquired techniques to new models and problems.

Making judgements: To be able to develop qualitative and quantitative investigation techniques regarding the properties of equilibrium solutions.

Communication skills: To develop knowledge of the terminology and concepts typical of Game Theory.

Learning skills: Students will be encouraged to extend the proposed solutions to models and issues not covered during the lectures.

Conoscenze e comprensione: sviluppare la conoscenza di modelli di giochi non cooperativi e del grado di (in)efficienza raggiunto da soluzioni all'equilibrio. 

Capacità di applicare conoscenze e comprensione: essere in grado di estendere le tecniche acquisite a nuovi modelli e problemi.

Autonomia di giudizio: essere in grado di sviluppare tecniche di indagine qualitativa e quantitativa sulle proprietà di soluzioni all'equilibrio.

Abilità comunicative: sviluppare la conoscenza del lessico e delle nozioni tipiche della Teoria dei Giochi.

Capacità di apprendimento: gli studenti saranno stimolati a estendere le soluzioni proposte a modelli e problematiche non coperti durante le lezioni.

Lectures.

Lezioni frontali.

Oral exam.

Prova orale.

Introduction to Game Theory.

Potential games: congestion games and load balancing games.

Mixed strategies and Nash's Theorem.

The price of anarchy and the price of stability of pure Nash equilibria.

Price of anarchy and stability in network cost-sharing games.

Price of anarchy and stability in linear congestion games.

Approximation of best-response dynamics in linear congestion games.

Cut games: price of anarchy, price of stability, and approximation of best-response dynamics.

Moderately greedy players in cut games: price of anarchy and approximation of best-response dynamics.

Mitigating selfish behavior: taxes and Stackelberg strategies for linear congestion games.

Partially altruistic players in linear congestion games.

Packing games: price of anarchy and stability.

Isolation games: price of anarchy and stability.

Schelling games: existence and efficiency of equilibria.

Fractional hedonic games: existence and efficiency of equilibria.

Introduzione alla Teoria dei Giochi.

Giochi con potenziale: giochi di congestione e giochi di bilanciamento del carico.

Strategie miste e Teorema di Nash.

Il prezzo dell'anarchia e il prezzo della stabilità degli equilibri di Nash puri.

Prezzo dell'anarchia e della stabilità dei giochi di condivisione dei costi su reti.

Prezzo dell'anarchia e della stabilità dei giochi di congestione lineari.

Approssimazione dei turni di contromosse migliori nei giochi di congestione lineari.

Giochi di taglio: prezzo dell'anarchia, prezzo della stabilità e approssimazione dei turni di contromosse migliori.

Giocatori moderatamente avidi nei giochi di taglio: prezzo dell'anarchia e approssimazione dei turni di contromosse migliori.

Combattere il comportamento egoista: tasse e strategie di Stackelberg per i giochi di congestione lineari.

Giocatori parzialmente altruisti nei giochi di congestione lineari.

Giochi di impacchettamento: prezzo dell'anarchia e della stabilità.

Giochi di isolamento: prezzo dell'anarchia e della stabilità.

Giochi di Schelling: esistenza ed efficienza di equilibri.

Giochi edonici frazionari: esistenza ed efficienza di equilibri.

Lecture notes provided by the lecturer upon request.

Dispense fornite dal docente su richiesta.