Ron Lavi – Chaitanya Swamy 1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010...

Ron Lavi Chaitanya Swamy 1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010 Annibale Panichella

Mechanism Design un insieme di giocatori un insieme di possibili outcomes un insieme di valutazioni private per ogni giocatore una funzione di valutazione con una funzione di scelta sociale un vettore di pagamenti con una funzione utilit 2

Mechanism Design ASSUNZIONI I giocatori sono egoisti ogni giocatore cerca di massimizzare la propria utilit un giocatore mente se e solo se mentendo aumenta la sua utilit Principio di rivelazione diretta ogni giocatore rivela un proprio valore OBIETTIVO che spinga i giocatori a rivelare il proprio vero valore Meccanismo Funzione di scelta sociale Pagamenti =+ 3

Mechanism Design DEFINIZIONE Un meccanismo deterministico compatibile agli incentivi se per ogni giocatore i dove la valutazione vera di i si ha che qualunque siano le valutazioni degli altri giocatori Lutilit ottenuta dal giocatore i nel caso in cui dice il vero Lutilit ottenuta dal giocatore i nel caso in cui dice il falso 4

Mechanism Design PROBLEMATICHE Il problema su cui si intende definire una funzione di scelta sociale un problema NP-hard Lalgoritmo che implementa la funzione di scelta sociale un algoritmo non polinomiale Non tutti gli algoritmi portano a meccanismi compatibili agli incentivi 5

Es.: Asta Combinatoria m un insieme di item indivisibili da vendere n un insieme di giocatori che competono per appropriarsi di un sottoinsieme degli item il giocatore i ha una funzione di valutazione per ogni sottoinsieme degli item S, che gode delle seguenti propriet: v i ()=0 non decrescente: per item indivisibili giocatori Maggiore il numero di item aggiudicati da i e maggiore la sua valutazione 6

Es.: Asta Combinatoria OBIETTIVO Problema di Social-Welfare Maximization (SWM): vogliamo calcolare unallocazione di item (S 1,, S n ) da distribuire tra i giocatori, tale che massimizzi il social welfare item indivisibili giocatori PROBLEMI SWM un problema NP-hard hanno lunghezza esponenziale: risolvere esattamente SWM pu richiedere un numero esponenziale di comunicazioni 7

Es.: Asta Combinatoria Mechanism Design e Asta Combinatoria Definire un meccanismo La funzione di scelta sociale la funzione SWM e va calcolata sui veri valori dei giocatori che non sono pubblici Ogni giocatore cerca di massimizzare la propria utilit Il meccanismo deve essere compatibile agli incentivi Meccanismo Valutazioni dichiarate INPUT Allocazione Pagamenti OUTPUT 8

Meccanismi VCG DOMANDA: data la funzione di scelta sociale =SWM, esistono dei pagamenti p tali che il meccanismo compatibile agli incentivi? 9 Meccanismi VCG genericiVCG per Asta Combinatoria A = insieme di outcomeA = allocazione di item (S 1,,S n ) V i = insieme di valutazioni valideV i = funzione di valutazioni monotone funz. di scelta soc. pagamenti RISPOSTA: S, i pagamenti VCG (Vickrey-Clarke-Groves) garantiscono la compatibilit agli incentivi. Qualunque funzione che non dipende dal giocatore i

Meccanismi VCG 10 VCG richiede di calcolare la funzione di scelta sociale (v), ossia, di risolvere il problema SWM che NP- hard Il meccanismo VCG corrispondente NON computazionalmente efficiente E necessario usare algoritmi di approssimazione per calcolare la funzione di scelta sociale VCG non funziona con tutti gli algoritmi di approssimazione

OBIETTIVO Mostreremo una tecnica generale per trasformare un algoritmo di approssimazione per problemi SWM di packing in un meccanismo probabilistico, approssimato e compatibile agli incentivi. 11 1.Modelliamo il problema tramite la P. L. Intera 2.Costruiamo un algoritmo c-approssimato 3.Dimostriamo che lintegrality gap al pi c Condizioni necessarie 1.Costruiamo un meccanismo frazionario 2.Costruiamo un meccanismo di supporto deterministico Operazioni Otteniamo un meccanismo c- approssimato, truthful-in- expectation Output Finora ci siamo occupati di Meccanismi Deterministici. Lobiettivo principale di tale costruzione quello di trasformare un meccanismo deterministico in un Meccanismo Probabilistico avente particolari propriet.

Meccanismi Probabilistici Meccanismi DeterministiciMeccanismi Probabilistici Definizione la funzione di scelta sociale una variabile aleatoria con una propria distribuzione di probabilit la funzione di pagamento una variabile aleatoria con una propria distribuzione di probabilit la funzione di utilit del giocatore i la variabile aleatoria associata allutilit di ogni singolo giocatore i Obiettivo: il meccanismo deve essere compatibile agli incentivi (truthful) Obiettivo: il meccanismo deve essere truthful in expectation (compatibile agli incentivi in aspettativa) 12 Definizioni di Meccanismi Deterministici e di Meccanismi Probabilistici a confronto.

Meccanismi Probabilistici 13 DEFINIZIONE Un meccanismo probabilistico truthful in expectation (compatibile agli incentivi in aspettativa) se per ogni giocatore i dove la valutazione vera di i si ha che qualunque siano le d.p. delle valutazioni degli altri giocatori Il valore atteso dellutilit ottenuta dal giocatore i nel caso in cui dice il vero Il valore atteso dellutilit ottenuta dal giocatore i nel caso in cui dice il falso Significato intuitivo: se tutti gli altri giocatori dichiarano il valore vero, la best response del giocatore i di dichiarare il vero

Costruzione Generale Di seguito descriviamo una tecnica generale per ottenere i meccanismi probabilistici che siano veritieri (compatibili agli incentivi) in aspettativa, e che garantiscono di raggiungere una buona approssimazione di benessere sociale. Per studiare concretamente tale tecnica, vedremo come applicarla alle aste combinatorie (CA); tuttavia i risultati ottenibili non perdono di generalit, dato che la tecnica resta sempre valida per gli altri problemi di packing per i quali linsieme delle possibili valutazioni dei singoli giocatori sono note pubblicamente e la funzione obiettivo lineare. 14

Costruzione per CA Possiamo formulare il problema dellasta combinatoria come un problema di Programmazione Lineare Intera: dato linsieme degli item da vendere definiamo una variabile aleatoria x i,S per ogni coppia giocatore i la funzione obiettivo 15 se il giocatore i riceve linsieme di item S altrimenti corrisponde alla funzione di Social Welfare

definiamo i seguenti vincoli Costruzione per CA 16 per ogni giocatore i per ogni item j per ogni coppia (i,S) Ad ogni giocatore assegnato al pi un solo insieme di item S Ogni item j assegnato al pi ad un solo giocatore Vincoli di interezza PROBLEMA Sfortunatamente non conosciamo un metodo matematico per risolvere il problema di programmazione lineare intera in tempo polinomiale: la P.L. Intera un problema NP-hard!

Costruzione per CA Invece di risolvere il problema di programmazione lineare intera, risolviamo una versione rilassata del problema, per i quali conosciamo algoritmi polinomiali (ad es. il simplesso): 17 per ogni giocatore i per ogni item j per ogni coppia (i,S) soggetta a vincoli Rilassamento continuo

P.L. Intera e P.L. Non Intera DOMANDA: che relazione c tra le soluzioni di un problema di Programmazione Lineare Intera e le soluzioni della sua versione rilassata? 18 Soluzioni ammissibili della P.L. Intera Soluzioni ammissibili della P.L. NON Intera Gli ottimi dei due problemi possono essere diversi

Integrality Gap Siano: P linsieme dei punti della regione ammissibile; linsieme delle soluzioni intere ; lintegrality gap di P definito come 19 Soluzione ottima del problema di P.L. frazionario Soluzione ottima del problema di P.L. intero Per i nostri scopi, ci occuperemo dei soli algoritmi di approssimazione che dimostrano un integrality gap IG P , il che vuol dire che la soluzione ottima del problema di P.L. Intera al massimo 1 / volte la soluzione ottima del suo rilassamento.

Meccanismi VGC frazionario Meccanismo VCG frazionario cos definito: sia di scelta sociale del problema SWM sia la soluzione ottima del problema modellato con Programmazione Lineare Frazionaria (ossia del rilassamento di P.L. Intera) sia il vettore delle valutazioni dei giocatori 1. poniamo la funzione di scelta sociale frazionaria 2. definiamo i pagamenti dei singoli giocatori come 20 Somma delle valutazioni degli altri giocatori ji una qualsiasi funzione che non dipende da v i tale che u i 0

Normalizzazione Dato un meccanismo VCG frazionario con integrality gap pari ad 1, possiamo definire un meccanismo VCG frazionario -scalato nel seguente modo: 21 1.funzione sociale 2.pagamenti VCG frazionario 1.funzione sociale 2.pagamenti VCG frazionario -scalato OSSERVAZIONE: dato che la funzione di valutazione dei giocatori una funzione lineare in x, VCG frazionario -scalato chiaramente compatibile agli incentivi

Ne deduciamo che il meccanismo frazionario scalato compatibile agli incentivi se e solo se il meccanismo frazionario M F ( F,p F ) compatibile agli incentivi. 22 Normalizzazione Infatti, supponiamo che il meccanismo frazionario scalato compatibile agli incentivi, abbiamo che Def. di compatibilit agli incentivi per il meccanismo frazionario non scalato

Main Decomposition Lemma Dimostreremo che dato un algoritmo A -approssimato che dimostra avere un integrality gap pari ad , possiamo esprimere qualunque soluzione del problema di P.L. frazionaria come combinazione lineare convessa delle soluzioni di P.L. Intera. 23 Per ogni coppia (i,S) che costituiscono la soluzione ottima del problema frazionario Per definizione di combinazione lineare convessa, vogliamo calcolare una sequenza di coefficienti l per cui

Main Decomposition Lemma 24 Riscrivendo il problema come problema di P. L. abbiamo Lintersezione tra questi due vincoli ci garantisce la ricerca di una soluzione ottima (se esiste) con valore pari a 1 Considerazioni: 1.Le variabili x i,S sono associate alle coppie (i,S), quindi, il numero il loro esponenziale 2 n m (dove n il numero di Item disponibili ed m il numero di giocatori) 2.Il numero di vincoli polinomiale ( pari al numero di variabili in base)

DualePrimale Main Decomposition Lemma Dato che tale problema non pu essere risolto efficientemente, ci concentriamo sul suo problema Duale: 25

Main Decomposition Lemma Il problema duale presenta le seguenti caratteristiche 26 1.Le variabili w i,S possono essere viste come valutazioni 2.Il numero di variabili polinomiale ( pari al numero di coppie (i,S) a cui associata una variabile x i,S * del primale che si trovano in base, cio x i,S * > 0 ) 3.Il numero di vincoli esponenziale 2 n m (dove n il numero di Item disponibili ed m il numero di giocatori) Duale Corrisponde alla funzione di scelta sociale del meccanismo frazionario - scalato.

Main Decomposition Lemma Dalla dualit forte, si sa che il Primale ha una soluzione ottima finita se e solo se anche il suo Duale ha una soluzione ottima finita, e in questo caso i rispettivi valori delle funzioni obiettivo coincidono Dalla dualit debole noto che per ogni soluzione finita x del primale e y del duale, vale Dalla propriet dei problemi di packing, sappiamo che se 27

Main Decomposition Lemma PROPOSIZIONE 1 Siano Possiamo ottenere una nuova soluzione tale che 28 DIMOSTRAZIONE Poniamo, che implica che ; dato che per la propriet di packing anche Significato intuitivo: possiamo trasformare il problema duale che ha le variabili w non vincolate, in un problema equivalente con variabili w + 0

DIMOSTRAZIONE Dato che il problema utilizza delle valutazioni non negative w +, abbiamo che Tuttavia, le valutazioni w + non sono monotone. Tramite le Proposizione 1, possiamo definire delle nuove valutazioni monotone w l tale che Main Decomposition Lemma PROPOSIZIONE 2 Siano possiamo calcolare in tempo polinomiale x l Z(P) tale che 29

30 Main Decomposition Lemma Possiamo calcolare in tempo polinomiale i coefficienti l che consentono di esprimere linsieme delle soluzioni ottime del problema di P.L. frazionaria come combinazione lineare convessa delle soluzioni di P.L. Intera DIMOSTRAZIONE Dimostriamo che il valore ottimo del problema duale, e quindi del suo primale (dualit forte), esattamente 1. Supponiamo per assurdo che il valore ottimo del duale maggiore di

Attraverso la Proposizione 2 possiamo definire un insieme di valutazioni monotone w i,S per le x i,S l tale che 31 Main Decomposition Lemma Che contraddice il vincolo del problema duale. In questo modo, abbiamo dimostrato che il valore ottimo esattamente 1 : la soluzione del problema duale restituisce i coefficienti l di combinazione lineare convessa. Per calcolare in tempo polinomiale tali coefficienti, possiamo risolvere il problema duale mediante il metodo dellellissoide (che risolve qualunque istanza il problema di P.L. in tempo polinomiale).

Meccanismo di supporto deterministico Tramite il lemma precedente, possiamo esprimere la soluzione del problema di P.L. Frazionaria -scalato, ossia, come combinazione lineare convessa della soluzione ottima del problema di P.L. Intera. 32 DEFINIZIONE Un meccanismo di supporto deterministico M D sar cos costituito la funzione di scelta sociale i prezzi sono gli stessi del mecc. fraz. -approssimato

Propriet dei meccanismi M D LEMMA: il meccanismo C compatibile agli incentivi e calcola una - approssimazione del social welfare. DIMOSTRAZIONE: dimostriamo che M D equivalente ad un Meccanismo VCG frazionario -scalato e ne conserva tutte le propriet. Per qualche il valore del giocatore i risulta essere 33 Dato che anche i pagamenti sono -scalati, il meccanismo M D compatibile agli incentivi. Tale compatibilit garantisce anche una -approssimazione Ottimo frazionario

Teorema Dato un meccanismo deterministico M D di supporto, compatibile agli incentivi e che calcola una -approssimazione del social welfare con un numero polinomiale di coefficienti j 0, possiamo ottenere in tempo polinomiale un meccanismo probabilistico M R che veritiero (compatibile agli incentivi) in aspettativa e che calcola una - approssimazione del social welfare 34 Coefficienti di combinazione lineare convessa della soluzione ottima di P.L. Intera Prezzi -scalati

La funzione sociale Meccanismi Probabilistici A partire dal meccanismo di supporto deterministico M D possibile costruire un Meccanismo Probabilistico M R nel seguente modo 35 Meccanismo M D La funzione sociale La funzione di scelta sociale R una variabile aleatoria con distribuzione di probabilit pari a D Meccanismo M R Sono anche le propriet di una funzione di probabilit secondo Kolmogorov Sono i coefficienti di combinazione convessa

Il giocatore i paga per ogni giocatore i Meccanismi Probabilistici 36 Meccanismo M D Il giocatore i paga per ogni giocatore i Meccanismo M R Variabile Aleatoria Scalare I pagamenti vengono definiti in questo modo per garantire che lutilit dei giocatori siano non negativi u i =v i -p i

Meccanismi Probabilistici Per il meccanismo probabilistico definito, valgono le seguenti propriet 1. 2. 3. lutilit 37 Un meccanismo probabilistico M R compatibile agli incentivi in aspettativa se e solo se il meccanismo di supporto deterministico corrispondente compatibile agli incentivi.

Risultato Finale Il meccanismo probabilistico M R definito in precedenza compatibile agli incentivi in aspettativa e calcola una - approssimazione della soluzione ottima di Social Welfare Maximization in tempo polinomiale. 38

Ricapitolando Operazioni per costruire il Meccanismo Probabilistico 1. modelliamo il problema tramite P.L. Intera 2. risolviamo il suo rilassamento (P.L. Frazionaria) 3. verifichiamo lIntegrality Gap IG 4. definiamo il meccanismo frazionario M F ( F,p F ) 5. definiamo il meccanismo frazionario M F ( F,p F ) -scalato 6. calcoliamo i coefficienti di combinazione lineare convessa (Decomposition Lemma) tramite il metodo dellellissoide 7. definiamo il meccanismo deterministico di supporto M D ( D,p D ) - approssimato 8. definiamo il meccanismo probabilistico M R ( R,p R ) 39

Esempio Vediamo come costruire un meccanismo probabilistico approssimato e veritiero in aspettativa per le Multi-Unit Combinatorial Auctions. 40 Formalmente una MUCA cos definita: m un insieme di item indivisibili da vendere B copie dello stesso item n un insieme di giocatori che competono per appropriarsi di un sottoinsieme degli item il giocatore i ha una funzione di valutazione per ogni sottoinsieme degli item S, che gode delle seguenti propriet: v i ()=0 non decrescente: per

MUCA Ogni giocatore pu aggiudicarsi pi copie dello stesso item Le valutazioni di un giocatore i per due copie dello stesso item sono uguali Se B= 1 parliamo di Asta Combinatoria OBIETTIVO Problema di Social-Welfare Maximization (SWM): vogliamo calcolare unallocazione di item (S 1,, S n ) da distribuire tra i giocatori, tale da massimizzi il social welfare 41

Costruzione di M R per MUCA A questo punto, vediamo le operazioni da effettuare per costruire un M R 1. modelliamo il problema di MUCA tramite P.L. Intera 42 per ogni giocatore i per ogni item j per ogni coppia (i,S) soggetta a vincoli Ogni item ha B copie

Costruzione di M R per MUCA 2. risolviamo il suo rilassamento (P.L. Frazionaria) 43 per ogni giocatore i per ogni item j per ogni coppia (i,S) soggetta a vincoli Rilassamento continuo

Costruzione di M R per MUCA 3. verifichiamo lIntegrality Gap 44 Dagli studi di Algoritmi deterministici, sappiamo che la versione del problema di P.L. rilassata ha IIntegrality Gap M = # di item B = # istanze dello stesso item 4.definiamo il meccanismo frazionario M F ( F,p F ) la cui funzione di scelta sociale F = ottimo frazionario e i pagamenti sono

Costruzione di M R per MUCA 6. Grazie al Main Decomposition Lemma sappiamo che le soluzioni frazionarie di P.L. possono essere scritte come combinazione lineare convessa delle soluzioni di P.L. intera 45 calcoliamo i coefficienti di combinazione lineare convessa { l } tramite il metodo dellellissoide in tempo polinomiale. 5.definiamo il meccanismo frazionario M F ( F,p F )

Costruzione di M R per MUCA 46 7.Definiamo il meccanismo deterministico di supporto 8.A partire dal meccanismo deterministico di supporto, definiamo il corrispondente meccanismo probabilistico M R ( R,p R ) che sar Compatibile agli incentivi in aspettativa Con complessit polinomiale

Ron Lavi – Chaitanya Swamy 1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010...

Documents

Transcript of Ron Lavi – Chaitanya Swamy 1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010...