Introduction Teor´ıa de juegos Market Mechanisms

Algorithmic Game Theory Gonzalo D´ıaz Universidad Cat´ olica de Chile

27 March 2012

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Introducci´on

La teor´ıa algor´ıtmica de juegos es un ´area de investigaci´on que combina el dise˜ no de algoritmos y la teor´ıa de juegos.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Juegos

Un juego consiste en un conjunto de n jugadores, J = {1, 2, . . . , n}. Cada jugador i tiene su propio conjunto de estrategias posibles Si . Para jugar el juego, cada jugador i elige una estrategia si ∈ Si . s = (s1 , . . . , sn ) es el vector de estrategias elegidas por los jugadores. s ∈ S = S1 × · · · × Sn . Este u ´ltimo conjunto contiene las combinaciones posibles de elecci´ on de estrategias de todos los jugadores.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Cada jugador tendr´a un orden de preferencias sobre los vectores s ∈ S. La forma usual de lograr esto es que cada jugador tenga una funci´ on de utilidad ui : S → R que asigna a cada vector s un n´ umero que representa su utilidad despu´es de jugada la ronda. Para algunos juegos es m´as conveniente definir la funci´on de costo ci : S → R, donde un costo menor es m´as deseable. Es crucial que la funci´ on de utilidad (costo) ui (ci ) dependa de la elecci´on de estrategia de todos los jugadores (S), y no s´olo del jugador i.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Ejemplo: Dilema del Prisionero Dilema del Prisionero es un juego donde existen dos estrategias posibles: Confesar y No Confesar. Las funciones de costo de ambos jugadores se pueden resumir en la siguiente tabla: j1 Confiesa j1 Calla

j2 Confiesa 4, 4 1, 5

j2 Calla 5, 1 2, 2

Aqu´ı, cada entrada muestra los costos incurridos por los jugadores: (c1 , c2 ).

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Soluci´on de la Estrategia Dominante Notaci´ on: Para un vector de estrategias s ∈ S, donde si es la estrategia jugada por el jugador i, denotamos con s−i al vector de dimensi´on (n − 1) que contiene las estrategias elegidas por los dem´as jugadores. As´ı, como alternativa a la notaci´ on ui (s), usaremos ui (si , s−i ), cuando sea conveniente. Definici´on Un vector de estrategias s ∈ S es una soluci´ on de estrategia dominante ssi ∀i, s 0 ∈ S: 0 0 ui (si , s−i ) ≥ ui (si0 , s−i )

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Teorema El juego Dilema del Prisionero tiene una soluci´on de estrategia dominante: s = (Confesar, Confesar). Demostraci´ on: Para ji : c1 (Co, Co) = 4 < c1 (Ca, Co) = 5, c1 (Co, Ca) = 1 < c1 (Ca, Ca) = 2. Para j2 : c2 (Co, Co) = 4 < c2 (Ca, Co) = 5, c2 (Co, Ca) = 1 < c2 (Ca, Ca) = 2.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Ejemplo: Juego de Contaminaci´ on ´ n es una generalizaci´ Juego de Contaminacio on de Dilema del Prisionero, con m´ ultiples jugadores. Asumimos n pa´ıses. Cada pa´ıs ji puede elegir si ∈ {Legislar, No legislar}. El costo de legislar es 3, pero cada pa´ıs que no legisla agrega un costo 1 a cada pa´ıs. Si en una ronda k pa´ıses no legislan: Habr´a k puntos de costo asociados a la contaminaci´on. Un pa´ıs que no legisl´ o: c = k. Un pa´ıs que s´ı legisl´ o: c = k + 3.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Teorema ´ n tiene la siguiente soluci´on de Juego de Contaminacio estrategia dominante: si = No legislar ∀i. Si en una ronda k pa´ıses no legislan: Los k pa´ıses que no legislan tienen costo ci = k. Los n − k pa´ıses que s´ı legislan tienen costo ci = k + 3. En este escenario, un pa´ıs que s´ı legisla puede mejorar su costo cambiando de estrategia. En la soluci´ on propuesta, ning´ un pa´ıs puede cambiar su estrategia para mejorar su costo.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Nota: En la pr´actica, muy pocos juegos tienen una soluci´on de estrategia dominante. El ´area de market design busca dise˜ nar juegos con soluciones de estrategias dominantes.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Ejemplo Para modelar una subasta: vi : Precio que el jugador i le asigna (privadamente) al objeto subastado. ui = vi − p si lo logra comprar a un precio p, si no, ui = 0. si : Precio que ofrece el jugador i. Cada jugador coloca su oferta en un sobre sellado y lo entrega. A continuaci´on, se necesita un mecanismo para elegir el ganador de la subasta.

Gonzalo D´ıaz

Algorithmic Game Theory

Introduction Teor´ıa de juegos Market Mechanisms

Mecanismo Definici´on Un mecanismo M es un algortimo que, dadas las estrategias de los jugadores, calcula el resultado (utilidades). Ejemplo En una subasta simple, el mecanismo es el siguiente: j