Il problema del cammino minimo tra 2 nodi in un grafo

con archi privati

Scenario

Archi di un grafo controllati da agenti egoistici Solo l’agente conosce il peso associato al

proprio arco Obiettivo: calcolare una “buona” soluzione di

un certo problema di ottimizzazione rispetto a pesi reali

Strumento: progettazione di un meccanismo truthful (pagamento opportuno degli agenti per convincerli a dire la verità!)

Il problema dello shortest path egoistico

Input: un grafo G=(V,E), ogni arco è un agente egoistico, un nodo sorgente s e un nodo destinazione t; il tipo di un agente è il costo di utilizzo dell’arco (quindi tipo > 0); la sua valutazione è uguale al suo tipo;

SCF: un vero cammino minimo in G=(V,E,tipi) tra s e t.

Più Formalmente Soluzioni ammissibili:

F: insieme dei cammini in G da s a t Tipo dell’agente e:

e: peso dell’arco intuitivamente: e è il costo che l’agente

sostiene per utilizzare e Valutazione agente e di un cammino

PF : ve(e,P)= e se eP, 0 altrimenti

SCF: shortest path in G=(V,E,) fra s e t.

Come progettare un meccanismo truthful per il

problema?Osservazione cruciale:

la (vera) lunghezza di un cammino P è:

eE ve(e,P)

problema utilitario!

…usiamo i meccanismi VCG

Meccanismo VCG

M= <g(r), p(x)>: g(r): arg minxF j vj(rj,x)

pe(x): Per ogni arco eE:

pe =j≠e vj(rj,g(r-e)) -j≠e vj(rj,x) cioè

Meccanismo VCG

M= <g(r), p(x)>: g(r): calcola PG(s,t) in G=(V,E,r) pe: Per ogni arco eE:

pe =j≠e vj(rj,g(r-e)) -j≠e vj(rj,x) cioè

dG-e(s,t)-(dG(s,t)-re) se ePG(s,t) 0 altrimenti

Per ogni e PG(s,t), dobbiamo calcolare PG-e(s,t), ovvero il cammino minimo di rimpiazzo in G-e =(V,E\{e},r-e) tra s e t

pe={

Cammino di rimpiazzo per e

s

t

e

2

2

34

5 6

510

5

12

PG-e(s,t)PG(s,t)

quanto viene pagato e?

pe=12-(11-2)=3

Quel è la complessità temporale del meccanismo?

…dobbiamo calcolare con uno SP tra s e t

…e il pagamento per gli archi selezionati

…è solo una questione algoritmica!

Ipotesi di lavoro n=|V|, m=|E| w(e): denota il peso dell’arco e dG(s,t): distanza in G da s a t (somma dei

pesi degli archi di PG(s,t)) I nodi s,t sono 2-edge connessi: cioè,

esistono in G almeno 2 cammini tra s e t che sono disgiunti sugli archi per ogni arco e del cammino PG(s,t) che viene rimosso esiste almeno un cammino alternativo in G-e

…infatti, in caso contrario…

Se s,t non sono 2-edge connessi, c’è almeno un arco in PG(s,t) che è un ponte (arco che rimosso spezza G in due componenti C1 e C2, r C1 e s C2)

Se e è un ponte dG-e(s,t) = ∞ Il possessore di quell’arco “tiene in

pugno” il sistema: può chiedere qualsiasi cifra!

Una soluzione banale

e PG(s,t) applichiamo l’algoritmo di Dijkstra al grafo G-e

Complessità: k=O(n) archi per O(m + n logn): O(mn + n2 logn) time

La soluzione che proponiamo costerà: O(m + n logn) time

Notazioni

SG(s), SG(t): alberi dei cammini minimi radicati in s e t

Ms(e): insieme dei nodi raggiungibili da s in SG(s) senza passare per l’arco e

Ns(e)=V/Ms(e): nodi del sottoalbero di SG(s) radicato in v, dove e=(u,v)

Mt(e), Nt(e) definiti in modo analogo

s

u

v

t

e

Ms(e)

Ns(e)

SG(s)

Crossing edges

Ms(e) e Ns(e) individuano un taglio in G Cs(e)={(x,y) E\{e}: x Ms(e),

yNs(e)} archi del taglio: crossing edges

Crossing edges

s

u

v

t

e

Ms(e)

Ns(e)

SG(s)

Cs(e)

Come è fatto PG-e(s,t)?

Ovvio: non usa e PG-e(s,t) deve attraversare il taglio È il cammino più corto fra quelli che

non usano e La sua lunghezza è:

ove w(f) denota il peso dichiarato per f.

dG-e(s,t)= min {dG-e(s,x)+w(f)+dG-e(y,t)}f=(x,y) Cs(e)

Cammino di rimpiazzos

u

v

t

ex

y

dG-e(s,t)= min {dG-e(s,x)+w(f)+dG-e(y,t)}f=(x,y) Cs(e)

Come calcolare dG-e(s,t)

Sia f=(x,y) Cs(e); dimostreremo che: dG-e(s,x)+w(f)+dG-e(y,t)=dG(s,x)+w(f)+dG(y,t)

Osservazione: dG-e(s,x)=dG(s,x), perché x Ms(e)

Lemma:Sia f=(x,y) Cs(e) un arco del taglio (x

Ms(e)). Allora y Mt(e).(da cui segue che: dG-e(y,t)=dG(y,t))

Un semplice lemmaDim(per assurdo)y Mt(e),

allora y Nt(e).

Quindi y discendente di u in SG(t) e PG(t,y) usa e.

PG(v,y) è sottocammino di PG(t,y). Quindi:

dG (v,y)=w(e) + dG (u,y) > dG (u,y).

y Ns(e),

allora PG(s,y) usa e.

PG(u,y) è sottocammino di PG(s,y). Quindi:

dG (u,y)=w(e) + dG (v,y) > dG (v,y).

s

u

v

t

e

Ms(e)

Ns(e)

SG(s)

x

y

s

t

Ns(e) Mt(e)

Ms(e)

Costo per calcolare cammini di rimpiazzo

Dati SG(s) e SG(t), in tempo O(1) si può calcolare

k(f):= dG-e(s,x) + w(f) + dG-e(y,t)

dG(s,x) guardo in SG(s)

Osservazione: k(f) è la lunghezza del cammino minimofra s e t che usa f

dG(y,t) guardo in SG(t)

Un altro semplice algoritmo

Passo 1: Calcoliamo SG(s) e SG(t)

Passo 2: e PG(s,t) guardiamo gli archi del taglio Cs(e) e prendiamo il minimo (rispetto al valore k(٠)).

ComplessitàPasso 1: O(m + n logn)Passo 2: k=O(n) archi, O(m) archi in ogni taglio:

O(mn)Migliore di O(mn + n2 logn) se m=o(n logn)

L’algoritmo di Malik, Mittal e Gupta (1989)

Alla fine degli anni ‘80, Malik et al. hanno risolto in tempo O(m+n log n) il seguente problema di vitalità su grafi: dato un cammino minimo PG(s,t), qual è il suo arco più vitale, ovvero l’arco la cui rimozione induce il più lungo cammino minimo di rimpiazzo tra s e t?

Il loro approccio costruisce efficientemente tutti i cammini di rimpiazzo tra s e t……ma questo è esattamente quello che stiamo cercando nel nostro meccanismo VCG!

L’algoritmo di Malik, Mittal e Gupta

Siano e1, e2,…,ek gli archi di PG(s,t) da s verso t Al passo i manteniamo in un heap H l’insieme

dei nodi Ns(ei) (convenzione: Ns(e0)=V) Chiamiamo i nodi in H nodi attivi Ad ogni nodo yH è associata una chiave k(y)

e un particolare crossing edge. k(y)= min {dG(s,x)+w(x,y)+dG(y,t)}

k(y): lunghezza del cammino minimo da s a t che usa un qualche arco (x, y) non dell’albero

x Ms(ei)

L’algoritmo di Malik , Mittal e Gupta

Inizializzazione: H =V, k(y)= per ogni y Passo i : consideriamo l’arco ei e

processiamo H nel seguente modo: Elimino da H tutti i nodi in Ws(ei)=Ns(ei-1)\Ns(ei) Considero ogni x Ws(ei), quando trovo che un

vicino y a x è attivo, calcolo k’(y)=dG(s,x)+w(x,y)+dG(y,t)

Se k’(y)<k(y) decremento k(y) a k’(y) Processati tutti gli x Ws(ei), estraggo il

minimo da H, che fornisce la lunghezza del cammino minimo di rimpiazzo per ei (dG-ei(s,t))

Un esempio

Ns(e1)

e1

e2

e3

e5

e4

s

t

Ws(e1

)

10

2

5

9

9

8

8

8

1

15

10

1113

Un esempio

Ns(e2)

e1

e2

e3

e5

e4

s

t

Ws(e2

)

10

2

5

9

9

8

8

8

1

1113

14

14

Complessità computazionale di MMG

TeoremaDati due nodi s,t in un grafo G con n

vertici e m archi, tutti i cammini di rimpiazzo possono essere calcolati in tempo O(m + n log n).

Complessità computazionale di MMG

Dim: Calcoliamo SG(s) e SG(t) in tempo O(m + n logn). Usiamo l’heap di Fibonacci. Complessità ammortizzata delle operazioni di delete e delete_min è O(logn), e O(1) per le operazioni di insert, find_min, decrease_key,make_heap.

Singola operazione make_heapO(n) insertO(n) find_minO(n) deleteO(m) decrease_key

O(m + n logn)

Complessità computazionale del VCG

CorollarioIl meccanismo VCG per il problema del

cammino minimo può essere calcolato in tempo O(m + n logn)

DimComplessità di g(٠): O(m + n logn)Complessità di p(٠): calcolo tutte le distanze dG-e(s,t), in tempo O(m + n logn)