Flow Auctions

Prendiamo in considerazione un mercato all’interno del quale un cliente (o buyer ) vuole reclutare un team di agents (o sellers) per compiere un particolare incarico. Ogni agent offre un servizio richiedendo in cambio una certa quantit`a di denaro. Obiettivo del cliente `e quello di selezionare un team, o feasible set, di agents, che gli permetta di realizzare l’incarico. A tale scopo il cliente pianifica una Procurement Auction o asta di approvigionamento, tramite la quale, raccoglier`a le offerte degli agents, ne selezioner`a un sottoinsieme e pagher`a ad ogniuno di loro la quantit`a di denaro richiesta. Le Path e leFlow Auctions sono casi particolari di Procurement Auctions. Nelle Path Auctions un cliente cerca di acquistare, al prezzo pi`u basso, un cammino all’interno di una rete tra un nodo sorgente ed uno destinatario. I sellers vengono rappresentati tramite degli archi che congiungono i nodi della rete, ogni seller ha un costo privato per la trasmissione di una data quantit`a di traffico attra- verso il suo arco. Le Path Auctions nascono in contesti di routing all’interno delle reti di calcolatori: ad esempio un Internet Service Provider (ISP) pu`o utilizzare una Procurement Auction per selezionare gli autonomus systems (ASs) attraverso i quali inoltrare la sua domanda di traffico. Le Flow Auctions sono una generalizzazione delle Path Auctions nelle quali la domanda di un cliente pu`o eccedere la capacit`a di un singolo cammino tra sorgente e destinazione. In questo caso il cliente dovr`a acquistare un insieme di cammini per soddisfare la sua domanda. Noi prenderemo in considerazione un particolare tipo di flow auction nella quale ogni cammino che va dal nodo sorgente s a quello destinatario d `e composto da un solo arco rappresen- tante un particolare seller. Ogni arco viene etichettato con due valori: la quantit`a di osservazioni e il prezzo a cui tali osservazioni vengono vendute. Scopo del clien- te `e quindi quello di selezionare un insieme di archi (agents) che soddisfano le sue esigenze, in modo tale da poter effettuare una campagna di sensing. Tramite una serie di equivalenze adatteremo un problema ampiamente trattato in letteratura e chiamato Il Problema dello Zaino alla nostra particolare flow auction. Possiamo

4 – Teoria dei giochi e algoritmi utilizzati

infatti assumere che:

• la capacit`a dello zaino rappresenti il budget a disposizione del cliente

• gli oggetti da inserire nello zaino rappresentino i sellers

• il peso degli oggetti identifichi il prezzo di vendita per il pacchetto di osser- vazioni

• il valore di un oggetto rappresenti la quantit`a di osservazioni vendute dal seller.

4.3

Il modello matematico

4.3.1 Terminologia

Richiamando le equivalenze precedentemente definite chiameremo sellers gli oggetti da inserire nello zaino ed il loro numero verr`a indicato con n. Il prezzo e la quantit`a di osservazioni associate al seller j verranno rispettivamente indicate con pj e oj (j

= 1,...,n). La quantit`a di denaro a disposizone del cliente verr`a indicata con C.

4.3.2 Il problema

Il problema che tratteremo `e conosciuto come Problema dello zaino 0-1 dove un oggetto pu`o essere (o non essere) selezionato una ed una sola volta senza ripetizioni, ed `e esprimibile come: max n X j=1 oj· xj (4.7) n X j=1 pj· xj ≤ C (4.8) xj = {0,1},j = (1,...,n) (4.9)

La risoluzione del problema appena definito ci permetter`a di individuare un vettore a valori binari x indicante l’insieme di sellers che massimizza il numero di osserva- zioni acquistate, dato un determinato budget C a disposizione. Tuttavia, il cliente potrebbe voler perseguire un obiettivo differente, ad esempio, potrebbe voler mini- mizzare la spesa per l’acquisto di una quantit`a di osservazioni pari almeno a Q. In questo caso il problema di minimizzazione pu`o essere espresso come:

min n X j=1 pj· yj (4.10) n X j=1 oj· yj ≥ Q (4.11)

4 – Teoria dei giochi e algoritmi utilizzati

yj = {0,1},j ∈ N (4.12)

La soluzione si ottiene ponendo yj = 1 − xj e risolvendo il problema di massimizza-

zione: max n X j=1 pj · xj (4.13) n X j=1 oj· xj ≤ n X j=1 oj− Q (4.14) xj = {0,1},j = (1,...,n) (4.15)

Detta z max la soluzione di tale problema: il problema di minimizzazione ha per soluzione il valore fornito da:

zmin =

n

X

j=1

pj − zmax (4.16)

Intuitivamente `e come se stessimo massimizziamo la spesa per l’acquisto delle osser- vazioni fornite dai sellers che non vengono selezionati dal cliente. Un ultimo caso particolare `e quello in cui si vuole soltanto massimizzare il numero di sellers reclu- tati, avendo il solito vincolo di spesa C. Tale problema si modella imponendo oj =

1 per ogni seller j appartenete ad N (con N insieme dei sellers).

max n X j=1 xj (4.17) n X j=1 pj· xj ≤ C (4.18) xj = {0,1},j = (1,...,n) (4.19)

4.4

Complessit`a computazionale

Il Problema dello zaino 0-1 precedentemente introdotto `e un problema di ottimiz- zazione combinatoria risolvibile mediante l’utilizzo della programmazione dinamica ed appartenente alla classe di problemi NP-Difficili. Dimostriamo che il problema dello zaino `e la generalizzazzione di un problema per il quale `e gi`a stato dimostrato essere NP-Difficile.

Dato il seguente problema decisionale:

PROBLEMA DI PARTIZIONAMENTO (PP): dati n interi positivi w1,...,wn

esiste un sottoinsieme S ⊆ N = {1,...,n} tale che P

j∈Swj =

P

4 – Teoria dei giochi e algoritmi utilizzati

Karp (1972) ha dimostrato che questo problema `e NP-Completo.

PROBLEMA SOMMA DI SOTTOINSIEMI (SS) `e NP-Difficile.

Dimostrazione. Consideriamo il rispettivo problema decisionale, ad esempio: dati n + 2 interi positivi w1, ..., wn, c e a, esiste un sottoinsieme S ⊆ N = {1,...,n} tale

che P

j∈Swj ≤ c ePj∈Swj ≥ a ?

Ogni istanza I del PP pu`o essere trasformata polinomialmente in una istanza equi- valente I0 del problema decisionale SS ponendo c = a =P

j∈Nwj/2.

(La risposta per I `e positiva se lo `e anche per I0).

IL PROBLEMA DELLO ZAINO 0-1 `e NP-Difficile.

Dimostrazione. Il problema della somma di sottoinsiemi `e un caso particolare del problema dello zaino 0-1 quando pj = wj per ogni j ∈ N .

4.5

L’Algoritmo

L’algoritmo pi`u semplice che possiamo utilizzare `e quello che utilizza un approccio brute-force, essendo presenti n agents esistono 2n possibili combinazioni di agents. Esplorando tutte le combinizioni possibili troviamo quella che ci permette di ottenere il massimo numero di osservazioni spendendo al massimo C crediti. Il tempo di esecuzione con tale approccio sarebbe O(2n_{). Possiamo fare di meglio utilizzando un}

algoritmo basato sulla programmazione dinamica. Due sono gli ingredienti chiave dei problemi di ottimizzazione che conducono ad una soluzione con la programmazione dinamica:

• sottostruttura ottima: una soluzione ottima del problema contiene al suo in- terno soluzioni ottime per i sottoproblemi,

• ripetizione dei sottoproblemi : alcuni sottoproblemi verranno visitati pi`u volte (ad esempio, sottoproblemi che condividono stessi sottoproblemi).

Denotiamo con KN AP (1,n,C) il problema dello zaino, se (x1,x2,...,xn) `e una solu-

zione ottima per il problema KN AP (1,n,C) allora:

• Se xn= 0 l’agent n-esimo non `e selezionato, allora (x1,x2, . . . ,xn−1) deve essere

una soluzione ottima per il problema KN AP (1,n − 1,C).

• Se xn = 1 l’agent n-esimo `e selezionato, allora (x1,x2, . . . ,xn−1) deve essere

4 – Teoria dei giochi e algoritmi utilizzati

Basandoci sulla sottostruttura ottima possiamo descrivere la soluzione del problema come: M [n,C] = max( n.osserv.caso1, n.osserv.caso2 ) = max(M [n − 1,C], M [n − 1,C − pn] + on). Similmente:

• M [n − 1,C] = max(M [n − 2,C],M [n − 2,C − p_n−1]) + on−1

• M [n − 1,C − p_n] = max(M [n − 2,C − pn],M [n − 2,C − pn− pn−1] + on−1)

Presa M [i,C0] come la cella della matrice M [·,·] che rappresenta il valore della solu- zione ottima per il problema KN AP (1,i,C0), che `e il sottoproblema della selezione degli agents in [1 . . . i] soggetta al vincolo di crediti pari a C0 allora:

M [i,C0] = max(M [i − 1,C0],M [i − 1,C0 − p_i] + oi). Considerando le condizioni al

contorno:

• Se i = 0; nessun agent da scegliere, allora M [i,C0] = 0;

• Se C0= 0; non ci sono crediti spendibili a disposizione, M [i,C0] = 0;

• Se p_i > C0; l’agent i eccede la quantit`a di crediti disponibili per cui non possiamo selezionarlo, allora M [i,C0] = M [i − 1,C0].

In conclusione la soluzione ricorsiva completa `e:

M [i,C0] =          0 se i = 0 o C0 = 0 M [i − 1,C0] se pi > C0 max(M [i − 1,C0],M [i − 1,C0− p_i] + oi) se i > 0 e C0 ≥ pi

La soluzione ottima si trova in M[n,C].

4.5.1 Pseudocodice

L’algoritmo che genera il contenuto della matrice M [·,·] `e mostrato nella scheda Algorithm 1: KNAPSACK01. La complessit`a dell’algoritmo in termini di tem- po `e O(nC), l’occupazione di memoria `e O(nC). La dimensione dei dati di ingres- so `e O(n · log C) quindi il tempo di esecuzione non sar`a polinomiale ma pseudo- polinomiale. L’algoritmo per la ricerca degli agent selezionati `e mostrato nella scheda Algorithm 2: SEARCHAGENTS

4.5.2 Un esempio

Consideriamo una istanza del problema con 9 agents ed una quanti`a di crediti a disposizione pari a 15. Il prezzo e la quantit`a di osservazioni vendute da un agent sono specificati nella tabella 4.1.

4 – Teoria dei giochi e algoritmi utilizzati

Algorithm 1 KNAPSACK01(C, n, o[], p[]) for c := 0 → C do M [0,c] := 0; end for for i := 0 → n do M [i,0] := 0; end for for i := 1 → n do for c := 1 → C do if p[1] > c then M [i,c] = M [i − 1,c]; else

if (o[i] + M[i-1, c - p[i]) > M[i-1,c] then M [i,c] := o[i] + M [i − 1,c − p[i]]; else M [i,c] := M [i − 1,c]; end if end if end for end for return M [n,C]; Algorithm 2 SEARCHAGENTS(C, n, M[,]) c = C; for i = n → 1 do if M [i,c] 6= M [i − 1,c] then l’agent i-esimo `e nello zaino i = i − 1; c = c − pi;

else

i = i − 1 end if end for

4 – Teoria dei giochi e algoritmi utilizzati

Agent 1 2 3 4 5 6 7 8 9 Osservazioni 2 3 3 4 4 5 7 8 8 Prezzo 3 5 7 4 3 9 2 11 5

Tabella 4.1: Prezzi e quantit`a di osservazioni

La matrice M `e: C’ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 i = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 i = 1 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 i = 2 0 0 0 2 2 3 3 3 5 5 5 5 5 5 5 5 i = 3 0 0 0 2 2 3 3 3 5 5 5 5 6 6 6 8 i = 4 0 0 0 2 4 4 4 6 6 7 7 7 9 9 9 9 i = 5 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13 i = 6 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13 i = 7 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18 i = 8 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18 i = 9 0 0 7 7 7 11 11 15 15 15 19 19 19 21 23 23 Tabella 4.2: Matrice M La soluzione ottima `e : Agent Selezionati 9, 7, 5, 4 Osservazioni acquistate 23 Spesa 14

Tabella 4.3: Soluzione ottima

4.6

Il gioco

Terminata la trattazione dei fondamenti teorici su cui il nostro gioco `e basato passia- mo ora alla descrizione della sua specifica implementazione. Il gioco consiste in una sorta di asta inversa dal momento che esiste un solo compratore, avente a disposizio- ne un budget spendibile per l’acquisto di una determinata quantit`a di osservazioni di sensing, ed un insieme di venditori ognuno dei quali offre un particolare servizio, e quindi una specifica quantit`a di osservazioni a cui `e collegato un costo. Scopo del gioco `e: per il compratore, tentare di massimizzare il numero di osservazioni acquistate avendo a disposizione un budget fissato, mentre per i venditori, tentare di massimizzare il guadagno per la vendita del proprio pacchetto di osservazioni. `E anche possibile, per il compratore, perseguire un obiettivo differente dal precedente,

4 – Teoria dei giochi e algoritmi utilizzati

piuttosto che massimizzare il numero di osservazioni avendo un budget prefissato, questi pu`o voler minimizzare la spesa complessiva per l’acquisto di una quantit`a prefissata di osservazioni.

4.6.1 Le entit`a coinvolte Le entit`a coinvolte nel gioco sono:

• N sellers che vendono pacchetti di osservazioni

• 1 buyer che vuole acquistare osservazioni di sensing