Ron Lavi – Chaitanya Swamy
Strumenti della Teoria dei Giochi per l’Informatica
A.A. 2009/2010
Annibale Panichella
1
Mechanism Design
 un insieme di giocatori [n ]
 un insieme di possibili outcomes A
 un insieme di valutazioni private Vi per ogni giocatore
 una funzione di valutazione vi : A 

con vi  Vi
 una funzione di scelta sociale f : V1 Vn  A
 un vettore di pagamenti p1 ,, pn con f : V1 
Vn 
 una funzione utilità i ui  vi  pi
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
Meccanismo
=
Funzione di
scelta sociale
+
Pagamenti
che spinga i giocatori a rivelare il proprio vero valore
3
Mechanism Design
DEFINIZIONE
Un meccanismo deterministico ( f , p ) è compatibile agli incentivi se
• per ogni giocatore i
•
vi Vi
•
 vi , vi ' Vi dove vi è la valutazione vera di i
qualunque siano le valutazioni degli altri giocatori
si ha che vi ( f (vi , vi ))  pi (vi , vi )  vi ( f (vi ' , vi ))  pi (vi ' , vi )
L’utilità ottenuta dal giocatore i
nel caso in cui dice il vero
L’utilità 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
• L’algoritmo 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
item
indivisibili
giocatori
• 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 vi (S ) per ogni
sottoinsieme degli item S, che gode delle seguenti proprietà:
• vi(Ø)=0
• vi (.) è non decrescente: vi (S )  vi (T ) per S  T
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
un’allocazione di item (S1 ,…, Sn) da distribuire tra i giocatori, tale che
• Si  S j  0
• massimizzi il social welfare
 v (S )
i
i
item
indivisibili
giocatori
PROBLEMI
• SWM è un problema NP-hard
• vi (S ) 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 M  ( f , pi i 1n )
• La funzione di scelta sociale ƒ è la funzione SWM e va calcolata sui veri
valori dei giocatori vi  (v1 vn ) che non sono pubblici
OUTPUT
INPUT
Valutazioni
dichiarate
v  (v1 vn )
Meccanismo
Allocazione
f (v)  (S1  Sn )
Pagamenti
p(v)  ( pi (v) pn (v))
• Ogni giocatore cerca di massimizzare la propria utilità
• Il meccanismo deve essere compatibile agli incentivi
8
Meccanismi VCG
DOMANDA: data la funzione di scelta sociale ƒ=SWM , esistono dei
pagamenti p tali che il meccanismo M  ( f , p ) è compatibile agli
incentivi?
RISPOSTA: Sì, i pagamenti VCG (Vickrey-Clarke-Groves) garantiscono la
compatibilità agli incentivi.
Meccanismi VCG generici
VCG per Asta Combinatoria
A = insieme di outcome
A = allocazione di item (S1,…,Sn)
Vi = insieme di valutazioni valide
Vi = funzione di valutazioni monotone
f : V1 Vn  A funz. di scelta soc.
f : V1 Vn  A funz. di scelta soc.


f (v)  arg max   vi (a) 
 i

aA
pagamenti
i,


f (v)  SWM  max   vi (a) 
aA  i

p (vi , vi )  hi (vi )   v j ( f (vi , vi ))
i j
Qualunque funzione che non dipende dal giocatore i
9
Meccanismi VCG
VCG richiede di calcolare
la funzione di scelta sociale
ƒ(v), ossia, di risolvere il
problema SWM che è NPhard
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
10
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.
Condizioni necessarie
1.
Modelliamo il problema
tramite la P. L. Intera
2. Costruiamo un algoritmo
c-approssimato
3. Dimostriamo
che
l’integrality gap è al più c
Operazioni
1.
Costruiamo un
meccanismo
frazionario
2. Costruiamo un
meccanismo di
supporto
deterministico
Output
Otteniamo un
meccanismo capprossimato,
truthful-inexpectation
Finora ci siamo occupati di Meccanismi Deterministici. L’obiettivo principale di
tale costruzione è quello di trasformare un meccanismo deterministico in un
Meccanismo Probabilistico avente particolari proprietà.
11
Meccanismi Probabilistici
Definizioni di Meccanismi Deterministici
confronto.
e di Meccanismi Probabilistici a
Meccanismi Deterministici
Meccanismi Probabilistici
Definizione M ( f , p )
Definizione
f : V1 V n outcome A è la
funzione di scelta sociale
M R ( f R , pR )
f R (v) è una variabile aleatoria con una
propria distribuzione di probabilità
p : V1 Vn   è la funzione di
piR (v ) è una variabile aleatoria con una
ui  vi  pi è la funzione di utilità del
uiR è la variabile aleatoria associata
pagamento
propria distribuzione di probabilità
giocatore i
all’utilità di ogni singolo giocatore i
Obiettivo: il meccanismo M ( f , p )
deve essere compatibile agli incentivi
(truthful)
Obiettivo: il meccanismo M R ( f R , p R )
deve essere truthful in expectation
(compatibile agli incentivi in
aspettativa)
12
Meccanismi Probabilistici
DEFINIZIONE
Un meccanismo probabilistico M R ( f R , p R ) è truthful in expectation
(compatibile agli incentivi in aspettativa) se
• per ogni giocatore i
qualunque siano le d.p. delle valutazioni degli altri giocatori
• vi  Vi
•  vi , vi ' Vi dove vi è la valutazione vera di i
si ha che
E[vi ( f (vi , vi ))  pi (vi , vi )]  E[vi ( f (vi ' , vi ))  pi (vi ' , vi )]
Il valore atteso dell’utilità
ottenuta dal giocatore i nel caso
in cui dice il vero
Il valore atteso dell’utilità
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
13
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 l’insieme delle possibili valutazioni dei singoli
giocatori sono note pubblicamente e la funzione obiettivo è lineare.
14
Costruzione per CA
Possiamo formulare il problema dell’asta combinatoria come un problema
di Programmazione Lineare Intera:
• dato l’insieme degli item da vendere T  T1 ,, Tn 
• definiamo una variabile aleatoria xi,S per ogni coppia
• giocatore i
• S  T con
S 0
xi ,S
1

0
se il giocatore i riceve l’insieme di item S
altrimenti
• la funzione obiettivo è
max
 v (S )  x
i,S 0
i
i,S
corrisponde alla funzione
di Social Welfare
15
Costruzione per CA
• definiamo i seguenti vincoli
x
S 0

i
i,s
1
per ogni giocatore i
 xi,S  1
per ogni item j
S : jS
xi , S  0, 1
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!
16
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):
 v (S )  x
max
i,S 0
i
i,S
soggetta a vincoli
 x  1 per ogni giocatore i
  x  1 per ogni item j
S 0
i,s
i ,S
xi , S  0, 1
i
S : jS
0  xi , S  1
per ogni coppia (i,S)
Rilassamento continuo
per ogni coppia (i,S)
17
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?
•
Soluzioni ammissibili
della P.L. Intera
Soluzioni ammissibili
della P.L. NON Intera
Gli ottimi dei due
problemi possono
essere diversi
18
Integrality Gap
Siano:
• P l’insieme dei punti della regione ammissibile;
• Z ( P )  P l’insieme delle soluzioni intere ;
l’integrality gap di P è definito come
IGP  sup
v  ( v1 , ,vn )
max xP  i , S vi ( s) xi ,S
max xZ ( P )  i , S vi ( s) xi ,S
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 IGP ≥ α , il che vuol dire che la soluzione
ottima del problema di P.L. Intera è al massimo 1/ α volte la soluzione
ottima del suo rilassamento.
19
Meccanismi VGC frazionario
Meccanismo VCG frazionario è M F ( f F , p F ) così definito:
• sia ƒ di scelta sociale del problema SWM
x* (v) la soluzione ottima del problema modellato
• sia
con
Programmazione Lineare Frazionaria (ossia del rilassamento di P.L.
Intera)
• sia v  (v1 , , vn ) il vettore delle valutazioni dei giocatori
1. poniamo la funzione di scelta sociale frazionaria f F (v)  x* (v)
2. definiamo i pagamenti dei singoli giocatori come


*
p (v)   hi (vi )   v j ( S ) x j ,S 
j i


F
i
Somma delle valutazioni degli
altri giocatori j≠i
È una qualsiasi funzione che non
dipende da vi tale che ui ≥ 0
20
Normalizzazione
Dato un meccanismo VCG frazionario con integrality gap pari ad α ≥ 1,
possiamo definire un meccanismo VCG frazionario α-scalato nel seguente
modo:
VCG frazionario
VCG frazionario α-scalato
1. funzione sociale
F
f (v )
p F (v )
2. pagamenti
1. funzione sociale
2. pagamenti
p F (v )
OSSERVAZIONE: dato che la funzione di valutazione dei giocatori
funzione lineare in x ,
 f (v ) 
vi 

  
F

vi f F (v)


f F (v )


vi ( x) è una
VCG frazionario α-scalato è
chiaramente compatibile agli
incentivi
21
Normalizzazione
Infatti, supponiamo che il meccanismo frazionario α–scalato è
compatibile agli incentivi, abbiamo che vi  Vi  vi , vi ' Vi
 f F (vi , vi )  piF (vi , vi )
 f F (vi ', vi )  piF (vi ', vi )
vi 
 vi 











vi f F (vi , v i )

 p
F
i
(vi , v i )



vi f F (vi ', vi )

 p
F
i
(vi ', vi )

Def. di
compatibilità
agli incentivi
per il
meccanismo
frazionario
non scalato
vi ( f F (vi , vi ))  piF (vi , vi )  vi ( f F (vi ', vi ))  piF (vi ', vi )
Ne deduciamo che il meccanismo frazionario α–scalato è compatibile agli
incentivi se e solo se il meccanismo frazionario MF(ƒF,pF) è compatibile
agli incentivi.
22
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  xi , S  come combinazione
lineare convessa delle soluzioni di P.L. Intera  x j  .
jI
Per definizione di combinazione lineare convessa, vogliamo calcolare una
sequenza di coefficienti λl per cui
xi*, S

  l x
l
i ,S

l
l
1
*
i ,S
per ogni (i, S ) tale che x
0
Per ogni coppia (i,S) che
costituiscono la soluzione
ottima del problema
frazionario
l
l , l  0
23
Main Decomposition Lemma
Riscrivendo il problema come problema di P. L. abbiamo
min  l
lI

l
xil, S 
l

l
1
xi*, S

, (i, S ) t.c. xi*, S  0
L’intersezione
tra
questi due vincoli ci
garantisce la ricerca
di una soluzione
ottima (se esiste) con
valore pari a 1
l
l , l  0
Considerazioni:
1. Le variabili xi,S sono associate alle coppie (i,S), quindi, il numero il loro
è esponenziale 2n•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)
24
Main Decomposition Lemma
Dato che tale problema non può essere risolto efficientemente, ci
concentriamo sul suo problema Duale:
Primale
Duale
min  l 1
max
lI

l
l
i ,S
x

l

l
*
i,S
x

( i , S )E
, (i, S ) t.c. xi*, S  0

( i , S )E
1

wi , S  1 z
xil, S wi , S  z  1 , l  I
z0
wi , S non vincolato (i, S )  E
l
l , l  0


xi*, S

con E  (i, S ) : xi*, S  0
25
Main Decomposition Lemma
Il problema duale presenta le seguenti caratteristiche
Duale
max

( i , S )E

( i , S )E
*
i,S
x

wi , S  z
xil, S wi , S  z  1 , l  I
z0
wi , S non vincolato (i, S )  E
1. Le variabili wi,S possono essere viste
come valutazioni
2. Il numero di variabili è polinomiale
(è pari al numero di coppie (i,S) a
cui è associata una variabile xi,S* del
primale che si trovano in base, cioè
xi,S* >0)
3. Il numero di vincoli è esponenziale
2n•m (dove n è il numero di Item
disponibili ed m è il numero di
giocatori)
Corrisponde alla funzione di scelta sociale del meccanismo frazionario αscalato.
26
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
min  l  max 
lI
lI
xi*, S

wi , S  z
 Dalla dualità debole è noto che per ogni soluzione finita x del primale e
y del duale, vale
min  l  max 
lI
lI
xi*, S

wi ,S  z
 Dalla proprietà dei problemi di packing, sappiamo che se
x  Z ( P) e y  x  y  Z ( P)
27
Main Decomposition Lemma
PROPOSIZIONE 1
Siano
*
E

(
i
,
S
)
:
x

i , S  0
•
• w  wi , S (i , S )E
Significato
intuitivo:
possiamo
trasformare il problema duale che ha le
variabili w non vincolate, in un
problema equivalente con variabili w+≥0

• w  max  wi , S , 0 
• xˆ  Z ( P) una soluzione del problema di P. L. Intera
Possiamo ottenere una nuova soluzione

( i , S )E
xil, S wi , S 

( i , S )E
xl  Z ( P) tale che
xˆi , S wi, S
DIMOSTRAZIONE
l
l
Poniamo xi , S  max  xˆi , S , 0  , che implica che xi ,S  xˆi ,S ; dato che xˆi , S  Z ( P )
per la proprietà di packing anche xl  Z ( P)
28
Main Decomposition Lemma
PROPOSIZIONE 2
*
E

(
i
,
S
)
:
x

i
, S  0
Siano
w  wi , S (i , S )E
possiamo calcolare in tempo polinomiale xl ∈Z(P) tale che

( i , S )E
xil, S wi , S 
1

 max
xP

( i , S )E
xi*,S wi ,S
DIMOSTRAZIONE
Dato che il problema utilizza delle valutazioni non negative w+, abbiamo
che
1

*

( i , S )E
xˆi , S wi , S 

 max
xP

( i , S )E
xi ,S wi ,S
Tuttavia, le valutazioni w+ non sono monotone. Tramite le Proposizione 1,
possiamo definire delle nuove valutazioni monotone wl tale che
1
l
l

ˆ
x
w

x
w

 max  xi*,S wi ,S


i ,S i ,S
i ,S i ,S
 xP ( i , S )E
( i , S )E
( i , S )E
29
Main Decomposition Lemma
Main Decomposition Lemma
Possiamo calcolare in tempo polinomiale i coefficienti λl che consentono
di esprimere l’insieme delle soluzioni ottime del problema di P.L.
*
frazionaria  xi , S  come combinazione lineare convessa delle soluzioni di
P.L. Intera  x j 
jI
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

( i , S )E
xi*, S

wi , S  z  1


( i , S )E
xi*, S

wi , S  1  z
30
Main Decomposition Lemma
Attraverso la Proposizione 2 possiamo definire un insieme di valutazioni
monotone wi,S per le xi,Sl tale che
*

( i , S )E
Che contraddice il vincolo
x wi , s 
l
i ,S

( i , S )E

( i , S )E
xi , S

xil, S wi , S  z  1
wi ,S  1  z
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
dell’ellissoide (che risolve qualunque istanza il problema di P.L. in
tempo polinomiale).
31
Meccanismo di supporto
deterministico
Tramite il lemma precedente, possiamo esprimere la soluzione del problema
di P.L. Frazionaria α-scalato , ossia x* (v)  , come combinazione lineare
I
convessa della soluzione ottima del problema di P.L. Intera x .
  j  0
 j (v) x con 

jI
 j  j  1
j
DEFINIZIONE
Un meccanismo di supporto deterministico MD sarà così costituito
• la funzione di scelta sociale f D (v)   j (v)
F
jI
p
(v )
• i prezzi sono gli stessi del mecc. fraz. α-approssimato piD (v)  i



32
Proprietà dei meccanismi MD
LEMMA: il meccanismo C è compatibile agli incentivi e calcola una αapprossimazione del social welfare.
DIMOSTRAZIONE: dimostriamo che MD
è equivalente ad un
Meccanismo VCG frazionario α-scalato e ne conserva tutte le proprietà.
Per qualche v   v1 , , vn  il valore del giocatore i risulta essere

*
*
v
x
(v)




x (v )
i
D
j
vi f (v)  vi    j (v) x   vi 





 jI




Dato che anche i pagamenti sono α-scalati , il meccanismo MD è compatibile agli
incentivi. Tale compatibilità garantisce anche una α-approssimazione
Ottimo
*
*
vi x (vi )
v x (vi )
frazionario
i i
OPTSWM   vi '  x(vi )  
i
i


  


33
Teorema
Dato un meccanismo deterministico MD di supporto, compatibile agli
incentivi e che calcola una α-approssimazione del social welfare
f (v)   j (v)
D
piD (v) 
piF (v)

jI
Coefficienti di combinazione lineare
convessa della soluzione ottima di
P.L. Intera
Prezzi α-scalati
con un numero polinomiale di coefficienti λj ≥ 0, possiamo ottenere in
tempo polinomiale un meccanismo probabilistico MR che è veritiero
(compatibile agli incentivi) in aspettativa e che calcola una αapprossimazione del social welfare
34
Meccanismi Probabilistici
A partire dal meccanismo di supporto deterministico MD è possibile
costruire un Meccanismo Probabilistico MR nel seguente modo
Meccanismo MR
Meccanismo MD
La funzione sociale è
f D (v)   j (v)
jI
Sono i coefficienti di
combinazione convessa
La funzione sociale è La funzione di scelta
sociale ƒR è una variabile aleatoria con
distribuzione di probabilità pari a ƒD
Prob  f R (v)   f D (v)   j (v)
  j  0

 j  j  1
jI
Sono anche le proprietà di
una funzione di probabilità
secondo Kolmogorov
35
Meccanismi Probabilistici
Meccanismo MR
Il giocatore i paga
Meccanismo MD
Il giocatore i paga
p (v ) 
D
i
F
i
p (v )

per ogni giocatore i
se vi ( f D (v))  0
piD (v)
p (v)  vi ( f (v))
vi ( f D (v))
R
i
R
se vi ( f D (v))  0
piR (v)  0
per ogni giocatore i
I pagamenti vengono definiti
in questo modo per garantire
che l’utilità dei giocatori siano
non negativi ui=vi-pi
Variabile Aleatoria
Scalare
36
Meccanismi Probabilistici
Per il meccanismo probabilistico definito, valgono le seguenti proprietà




R
l
l
l
D
1. E vi f (v)    Pr[ x ]  x  l  x  vi f (v)
i
i
D
D
D


p
(
v
)
p
(
v
)
p
(v) D
R
l
l
l
l
i
i
i
2. E  pi (v)     Pr[ x ]  x 


Pr[
x
]

x

 f (v)  piD (v)




D
D
D


f (v)  f (v) i
f (v )
i 
3. l’utilità
uiD  vi  f D (v)   piD  E vi  f R (v)   E  piR   E vi  f R (v)   piR 
Un meccanismo probabilistico MR è compatibile agli incentivi in aspettativa se
e solo se il meccanismo di supporto deterministico corrispondente è
compatibile agli incentivi.
37
Risultato Finale
Il meccanismo probabilistico MR 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.
2.
3.
4.
5.
6.
7.
8.
modelliamo il problema tramite P.L. Intera
risolviamo il suo rilassamento (P.L. Frazionaria)
verifichiamo l’Integrality Gap IG ≥ α
definiamo il meccanismo frazionario MF(ƒF,pF)
definiamo il meccanismo frazionario MF(ƒF,pF) α-scalato
calcoliamo i coefficienti di combinazione lineare convessa
(Decomposition Lemma) tramite il metodo dell’ellissoide
definiamo il meccanismo deterministico di supporto MD(ƒD,pD) αapprossimato
definiamo il meccanismo probabilistico MR(ƒR,pR)
39
Esempio
Vediamo come costruire un meccanismo probabilistico approssimato e
“veritiero” in aspettativa per le Multi-Unit Combinatorial Auctions.
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 vi (S ) per ogni
sottoinsieme degli item S, che gode delle seguenti proprietà:
• vi(Ø)=0
• vi (.) è non decrescente: vi (S )  vi (T ) per S  T
40
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
un’allocazione di item (S1 ,…, Sn) da distribuire tra i giocatori, tale da
massimizzi il social welfare
 v (S )
i
i
41
Costruzione di MR per MUCA
A questo punto, vediamo le operazioni da effettuare per costruire un MR
1.
modelliamo il problema di MUCA tramite P.L. Intera
max
 v (S )  x
i,S 0
i
i,S
 x 1
  x B
S 0
per ogni giocatore i
i,s
i ,S
xi , S  0, 1
i
S : jS
soggetta a vincoli
Ogni item ha
B copie
per ogni item j
per ogni coppia (i,S)
42
Costruzione di MR per MUCA
2.
risolviamo il suo rilassamento (P.L. Frazionaria)
max
 v (S )  x
i,S 0
i
i,S
soggetta a vincoli
 x  1 per ogni giocatore i
  x  B per ogni item j
S 0
i,s
i ,S
xi , S  0, 1
i
S : jS
0  xi , S  1
per ogni coppia (i,S)
Rilassamento continuo
per ogni coppia (i,S)
43
Costruzione di MR per MUCA
3.
verifichiamo l’Integrality Gap
Dagli studi di Algoritmi deterministici, sappiamo che la
versione del problema di P.L. rilassata ha I’Integrality Gap
 B11 
IGP  O  m 


4.
M = # di item
B = # istanze dello stesso item
definiamo il meccanismo frazionario MF(ƒF,pF) la cui funzione di
scelta sociale ƒF = ottimo frazionario e i pagamenti sono


piF (v)   hi (vi )   v j ( S ) x*j ,S 
j i


44
Costruzione di MR per MUCA
5.
definiamo il meccanismo frazionario
MF(ƒF,pF)
la cui funzione di scelta socialeƒ F 
1
B 1
pF
m
6.
 scalato
ottimo frazionario
m
e i pagamenti sono
m
1
B 1
1
B 1
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
calcoliamo i coefficienti di combinazione lineare
convessa {λl} tramite il metodo dell’ellissoide in
tempo polinomiale.
45
Costruzione di MR per MUCA
 B11 
7. Definiamo il meccanismo deterministico di supporto O  m   app.



M D = f D ,p D
8.

funzione di scelta socialeƒ D  l lI
=
pagamenti sono f D  f F

A partire dal meccanismo deterministico di supporto, definiamo
il corrispondente meccanismo probabilistico MR(ƒR,pR) che sarà
• Compatibile agli incentivi in aspettativa
• Con complessità polinomiale
•
 B11 
O  m   approssimato


46