Annonce

Les commentaires sont clos.

Repeated games and engineering economics (M. van der Schaar, W. Zane)

6 Mars 2012


Catégorie : Journée d étude


Repeated games and engineering economics

Instructors: Prof. Mihaela van der Schaar (IEEE Fellow, Distinguished Lecturer IEEE) and Prof. William Zane (Fellow of the Econometric Society), UCLA

Vous êtes invité(e)s à un séminaire un peu spécial, plus long que d'habitude, proposé par deux professeurs d'UCLA, sur la théorie des jeux. Vous pouvez assister à la première partie (activités locales EURASIP), d'une heure, qui sera une introduction avec des exemples d'applications. Elle sera suivie d'un cours approfondi de 7h (sous l'égide de l'IEEE ComSoc), le tout pouvant donner lieu pour les doctorants à une attribution de crédits ECTS par l'EDITE.

Le tutoriel aura lieu à Télécom ParisTech, 46 rue Barrault, 75634 Paris :

15 mars, 14h00-17h00, en Amphi B312
16 mars, 10h00-12h30 et 14h30-17h00, en Amphi B310

Le tutoriel sera en anglais. Pour cette raison, le sommaire et la description détaillée qui suivent sont en anglais aussi.

 

Repeated games and engineering economics

Instructors: Prof. Mihaela van der Schaar (IEEE Fellow, Distinguished Lecturer IEEE) and Prof. William Zane (Fellow of the Econometric Society), UCLA

Brief Description

This course is about the use of basic as well as advanced microeconomics and game theory concepts in the design, analysis and optimization of networks and distributed systems.

We show how the strategic interaction emerging among networked applications, machines or tasks can be modeled as non-cooperative (games in normal form, extended form, repeated games) or cooperative games (coalitional games, bargaining etc.), and how the various solution concepts of these games can be used to design, analyze and improve existing and emerging networks and distributed systems. We characterize the performance of these networks and distributed systems using different equilibrium concepts, such as Nash, Stackelberg, correlated, conjectural, Wardrop equilibriums etc. Advanced concepts such as repeated or stochastic games will be studied to model repeated, long-term interactions among network entities. We will also study how to build strategy-proof protocols using ideas from mechanism design. Special attention will be paid to how the networking games are affected by the network entities’ information availability, bounded rationality, and ability to gather knowledge.

In this context, we will consider networking games with public as well as private monitoring, and perfect or imperfect monitoring. The tools, methods and formalisms introduced in this course apply to a variety of network and distributed systems,which include multi-user wireless communications, sensor networks, cognitive radio networks, Internet 2, P2P networks, sponsored search, and cloud computing.

Full description

Interactions emerging among inter-connected applications, machines,  tasks can be modeled as a game, in which these applications, machines, tasks   can strategically interact with each other in order to compete for the   (dynamically) available network or system resourcesand improve their  achievable performance.

In this course, we discuss how different cooperative and non-cooperative games  among agents can be constructed to design, analyze, optimize,and shape the emerging interactions among users in different networks and system settings.

We also discuss how strategic agents can successfully compete with each other  for the limited and time-varying resources, by optimizing their decision  process and learning from their past interactionwith other agents.  Importantly, the interactions that are of interest in engineered systems, from  communication networks to computer systems, take place among agents having  limited and often asymmetric information about each other and the environment,  as well as different abilities to process this information. Hence, the  information-decentralization and the heterogeneity of agents play a key role  in shaping the resulting efficiency of the considered inter-agent  interactions. To determine their optimal actions in these distributed,  informationally-decentralized environments, agents will need to learn and  model directly or implicitly the other agents’ responses to their actions.  Hence, this coursewill also discuss how agents can make conjectures and learn  how to adjust their actions in order to coordinate or cooperate with other  agents in selecting efficient outcomes of the underlying networking games.  Finally, interactions among agents with various amounts of knowledge will be  analyzed both in terms of dynamics and steady state equilibrium(s), and we  will present how new multi-user communication mechanisms can be synthesized,  which are efficient, fair, and incentive compatible (i.e. they are robust to  manipulation by strategic agents).

A feature that distinguishes the theories and algorithms discussed in this course from those common in economics is that we focus on the design and selection of equilibria of these games to achieve desired outcomes rather than on the use of games and equilibria to describe existing situations.

Intended audience

Communication, Networking, Signal Processing, Computer Engineering and Systems, and Computer Science Graduate Students

Topics included

1. Strategic interactions in communications, networks and computing systems – a    motivation

  • Existing multi-user and system optimizations, and solutions – limitations; network collapse
  • Why are game-theoretic and economics principles useful? – A brief motivation
  • Constructing engineering games - Some illustrative examples
    • Non-collaborative networking
    • Multi-user wireless communications: CSMA, TDMA
    • Multi-user networking: TCP
    • Peer-to-peer (P2P) networking: Bit-Torrent
    • Multi-tasking over multi-core processors
    • Collaborative networking: Sensor networks
    • User utility: Defining realistic utility-resource functions
    • System utility: Pareto efficiency (optimality) & fairness

2. Non-cooperative game theory in different networks and distributed systems

  • Networking games in normal form
  • Analyzing games: from optimality to equilibrium
    • Dominant strategies, Dominated strategies
    • Defining best response and Nash equilibrium
    • Existence of Nash equilibria
    • Finding Nash equilibria
    • Efficient vs. inefficient Nash equilibria (price of anarchy)
    • Correlated equilibrium
    • Conjectural equilibrium
    • Other equilibria and when are they useful
    • Comparing the performance of various equilibria
    • Adjustment processes
    • Policing and convergence to equilibrium in networking games
    • Knowledge, beliefs and communication among agents in networking games
    • Illustrative examples – Multi-user access communication (MAC) games

3. Dynamic games of complete information

  • Extensive-form games
    • Stackelberg equilibrium
    • Sub-game perfect equilibrium, one-step deviation principle
    • Repeated games
    • On the importance of memory in games
    • Bayesian Games
    • Illustrative examples – P2P networks and MAC Games
    • Comparisons of different solutions in terms of complexity, performance and informational requirements for dynamic networks and systems

4. Advanced game representations

  • Stochastic games
  • Potential games, Congestion games
  • S-modular games
  • Illustrative examples – MAC Games

Course format: 8 hours

Material used

Tutorial articles from various magazines and journals. Also, some materials from several books will also be provided. Note: this class will require the students to independently study a certain  amount of related literature.

Biography of Prof. William Zane

William Zame is Distinguished Professor of Economics and Mathematics at UCLA, where he has been on the faculty since 1990. He is a Fellow of the Econometric Society and a past Fellow of the John Simon Guggenheim Foundation. He has published in all aspects of economic theory (including cooperative and non-cooperative game theory and general equilibrium theory), in experimental economics, in finance, and in applications of economic theory to electrical engineering and networks. He has held visiting appointments at the Institute for Advanced Study, the Institute for Mathematics and its Applications, the Mathematical Sciences Research Institute, the Institut Mittag-Leffler, the University of Copenhagen, and the University of California at Berkeley.

Biography of Prof. Mihaela van der Schaar

Mihaela van der Schaar is Chancellor's Professor of Electrical Engineering at University of California, Los Angeles.She is an IEEE Fellow, a Distinguished Lecturer of the Communications Society for 2011-2012, the Editor in Chief of IEEE Transactions on Multimedia and a member of the Editorial Board of the IEEE Journal on Selected Topics in Signal Processing. She received an NSF CAREER Award (2004), the Okawa Foundation Award (2006), the IBM Faculty Award (2005, 2007, 2008), and several best-paper awards including recently the Gamenets Conference Best Paper Award (2011) and the 2011IEEE Circuits and Systems Society Darlington Award Best Paper Award. She received three ISO awards for her contributions to the MPEG video compression and streaming international standardization activities, and holds 33 granted US patents. For more information about her research visit: http://medianetlab.ee.ucla.edu/