Meccanismi
one-parameter: il problema
dell’albero dei cammini minimi a
sorgente singola
SPT non cooperativo
(ogni agente controlla un arco)


Input: un grafo G=(V,E) biconnesso
sugli archi, in cui ogni arco corrisponde
in modo biunivoco ad un insieme di
agenti egoisti, ed un nodo sorgente
sV; il tipo di un agente è il costo di
utilizzo dell’arco (quindi tipo>0);
SCF: un albero dei cammini minimi
radicato in s in G=(V,E,t).
SPT non utilitario

Per ogni albero ricoprente T di G radicato in s, la funzione
obiettivo minimizzata dalla SCF è:
f(t)= arg min
TF

{  dT(s,v) =  te ||e||}
vV
Con protocollo unicast : ve(te,T)=
eE(T)
te
se e  E(T)
0
altrimenti
e quindi f(t)  arg min  ve(te,T) (problema non utilitario)
TF

eE
Ma il problema è one-parameter, in quanto
se e  E(T)
1
ve(te,T)= te we(T), ove we(T)=
0
altrimenti
Meccanismo one-parameter
per l’SPT non utilitario

MSPT= <g(r), p(x=g(r))>


g(r): dato il grafo e le dichiarazioni, calcola un
SPT SG(s) di G=(V,E,r) utilizzando l’algoritmo
di Dijkstra.
p(x): per ogni arco e  E
pe=re we(r) +
∫r
∞
e
we(r-e,z) dz
così da garantire la partecipazione volontaria.
Truthfulness
Osservazione: MSPT è truthful. La truthfulness segue dal
fatto che MSPT è un meccanismo OP. Infatti, l’algoritmo di
Dijkstra per il calcolo dell’SPT è monotono, in quanto il carico
di lavoro per un agente ae ha sempre la forma:
L’algoritmo del
meccanismo
è monotono!
1
Өe : valore soglia
Өe è il valore tale che, fissato r-e:
se ae dichiara al più Өe, allora e è selezionato
se ae dichiara più di Өe, allora e non è selezionato
Sui pagamenti
1
Өe : valore soglia
re

re
pe=0, se e non è un arco selezionato
∞
pe = re we(r) + ∫ we(r-e,z) dz = 0+0 = 0
re

pe= Өe, se e è nella soluzione
∞
pe = re we(r) + ∫ we(r-e,z) dz = re + Өe - re = Өe
re
Sulle soglie
Sia e=(u,v) un arco in SG(s) (u più vicino a s che v)
 e resta in SG(s) finché uso e per raggiungere v
 Allora, Өe=dG-e(s,v)-dG(s,u)
Esempio
2
2
re=1
re= 2+ε
re= 3+ε
s
s
s
1
1
1
u
e 1
v
3
2
6
2
u
e 2+ε
v
3
2
6
2
u
e 3+ε
v
3
Өe = 3
6
Una soluzione banale
e=(u,v) SG(s) applichiamo l’algoritmo di
Dijkstra al grafo G-e e troviamo dG-e(s,v)
Complessità: k=n-1 archi per O(m + n logn):
O(mn + n2 logn) time
La soluzione che proponiamo costerà:
O(m + n logn) time
Definizione di Өe
s
u
x
e
f
v
y
dG-e(s,v)=
min
{dG(s,x)+w(f)+dG(y,v)}
f=(x,y)C(e)
ove w(f) denota il peso dichiarato per l’arco f
Definizione di Өe

Calcolare dG-e(r,v) (e quindi Өe) vuol dire individuare l’arco
f* tale che:
f*= arg min
f=(x,y)C(e)
= arg min
f=(x,y)C(e)
Perché dG(s,v) non
dipende da f
{dG(s,x)+w(f)+dG (y,v)}
{dG(s,x)+w(f)+dG (y,v)+dG(s,v)}
= arg min {dG(s,x)+w(f)+dG(s,y)}
f=(x,y)C(e)
lo chiamo k(f)
Osservazione: k(f) è un valore univocamente associato
all’arco f: vale per tutti gli archi di SG(s) che formano un
ciclo con f.
Calcolo delle soglie




Costruiamo il transmuter (rispetto a SG(s) )
Eseguiamo l’algoritmo (analisi di sensitività)
per il calcolo dei valori up(e) etichettando i
nodi pozzo t(f) con i valori k(f) (invece che
w(f))
Ogni arco e  SG(s) riceverà il suo valore
miglior valore k(f*)
Өe= (k(f*)-dG(s,v)) - dG(s,u)
dG-e(s,v)

Complessità temporale: O(m (m,n))
Complessità del meccanismo
Teorema
MSPT è calcolabile in tempo O(m + n log n).
Dim.:
Complessità di g(٠): O(m + n log n)
(Dijkstra con Heap di Fibonacci)
Calcolare tutti i pagamenti costa:
O(m (m,n))=O(m + n log n)
perché (m,n) costante
quando m=(n log log n)
Approfondimento
Progettare un meccanismo one-parameter per il
calcolo dell’SPT modello unicast radicato in s del
seguente grafo: