Il problema del job scheduling in presenza di agenti egoistiferraioli/files/tesi.pdf · l'ambiente...

UNIVERSITÀ DEGLI STUDI DI SALERNOFACOLTÀ DI SCIENZE MATEMATICHE FISICHE E NATURALI

CORSO DI LAUREA IN INFORMATICA SPECIALISTICA

anno accademico 2007-2008

Il problema del job

scheduling in presenza di

agenti egoisti

Relatore Candidato

prof. Vincenzo Auletta Diodato Ferraioli

Per te, nonno

Indice

Introduzione 3

1 Selsh Scheduling 7

1.1 Modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Selsh Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3 Selsh Client Assignment . . . . . . . . . . . . . . . . . . . . . 101.4 Associazione in reti 802.11-based . . . . . . . . . . . . . . . . 11

2 Teoria dei giochi 13

2.1 Giochi e Equilibri . . . . . . . . . . . . . . . . . . . . . . . . . 132.2 Congestion e Potential Games . . . . . . . . . . . . . . . . . . 152.3 Price of Anarchy . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Stato dell'arte 20

3.1 Notazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2 Unrestricted Job Scheduling . . . . . . . . . . . . . . . . . . . 22

3.2.1 Maximum Latency . . . . . . . . . . . . . . . . . . . . 233.2.2 Total Latency . . . . . . . . . . . . . . . . . . . . . . . 25

3.3 Restricted Job Scheduling . . . . . . . . . . . . . . . . . . . . 283.4 Routing Games . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Unrelated Restricted Scheduling 32

4.1 Esistenza Equlibrio . . . . . . . . . . . . . . . . . . . . . . . . 324.1.1 Dimostrazione . . . . . . . . . . . . . . . . . . . . . . . 324.1.2 Potenziale . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2 Maximum Latency . . . . . . . . . . . . . . . . . . . . . . . . 344.3 Server Latency . . . . . . . . . . . . . . . . . . . . . . . . . . 354.4 Total Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.4.1 Machine load and PoA . . . . . . . . . . . . . . . . . . 374.4.2 Identical Setting . . . . . . . . . . . . . . . . . . . . . 42

4.5 Quadratic latency . . . . . . . . . . . . . . . . . . . . . . . . . 48

1

INDICE 2

Conclusioni 50

Indice analitico 56

Introduzione

Negli ultimi anni è emersa un interessante area di studio nella comunità al-goritmica che fonde i principi dell'informatica a quelli, più strettamente eco-nomici, di teoria dei giochi: tale fusione, chiamata algorithm game theoryè imputabile soprattutto all'avvento e alla diusione di Internet.

Internet ha trasformato e accelerato i normali mercati noti all'economiae ne ha creati nuovi e perciò inimmaginabili, oltre ad essere esso stesso, inmaniera importante, un mercato: in questo ambito, gli algoritmi diventanol'ambiente naturale e la piattaforma di default per prese di decisione strate-giche. D'altro canto, Internet è il primo artefatto computazionale che nonè stato creato da una singola entità (ingegnere, team di progettazione, ocompagnia), ma emerge dall'interazione strategica di molte di esse. Gli in-formatici si sono trovati così per la prima volta di fronte ad un oggetto a cuidovevano pensare con la stessa incertezza e perplessità con cui gli economistiavevano approcciato i mercati. E, in maniera abbastanza prevedibile, si sonorivolti alla teoria dei giochi per ottenere ispirazione in tale studio, o, perdirlo con le parole di Scott Shenker, un pionere di questo modo di pensare,Internet è un equilibrio, noi dobbiamo solo identicare il gioco.

Gli algoritmi per computare equilibri sono stati uno dei primi obiettividella ricerca dell'algorithm game theory. Questi lavori hanno dato un con-tributo notevole al dibattito in economia circa la validità delle predizioni delcomportamento: un'eciente computabilità è emersa come una caratteristicamolto desiderabile per tali predizioni, mentre l'intrattabilità computazionalegetta un ombra di implausibilità su un concetto di equilibrio proposto.

La natura algoritmica del mechanism design, un'altra delle aree dell'al-gorithm game theory, è ancora più immediata: essa si occupa della proget-tazione di giochi, con giocatori che hanno utilità sconosciute e private, taliche all'equilibrio il progettista ottenga i propri obiettivi indipendentementedalle utilità degli agenti. Questo è ovviamente un problema computazionale:un ingente lavoro esplicitamente algoritmico sul mechanism design è statofatto negli ultimi anni, specialmente in ambiti come aste e cost sharing dirapida applicazione pratica (per esempio, come recuperare il costo un servizio

3

4

Internet dai clienti che valutano il servizio con importi noti soltanto a loro).Inne, ci si è occupati di analizzare situazioni in cui gli utenti di un sistema

interagiscono e si condizionano l'uno con l'altro. Esistono molti giochi chemodellano problemi tipici dell'informatica: routing, network design e facilitylocation ne sono solo alcune.

Il routing game modella il traco dei pacchetti su Internet: ogni routerdecide verso quale link instradare i pacchetti che debbano raggiungere unadeterminata destinazione. Una assai ragionevole soluzione sarebbe quella diselezionare il link che sembri meno congestionato. Comunque, se molti routerselezionano lo stesso link questo diverrà sovraccarico e creerà danni al routerche vedrà riempirsi la proprio coda e rallentare la propria attività. Questoè un gioco: la scelta di ogni router condiziona l'attività e le performance dimolti altri router.

Chiaramente, il processo che costruisce e mantiene Internet, e localizzaalcune risorse (come i name servers DNS) è anch'esso un gioco. Internet ècostruito da un insieme di Independent Network Providers (ISP), ognuno deiquali costruisce la propria porzione di rete in maniera autonoma e secondoi propri interessi e utilizzando gli altri providers solo se necessario. Ma unabuso delle risorse di rete di un ISP produce un peggioramento del tracoe delle condizioni del servizio, creando quindi una situazione simile a quelladescritta in precedenza: guardando Internet da questa prospettiva, è magicoche esso lavora così bene come fa.

Koutsoupias e Papadimitriou [17] per primi hanno inquadrato questiproblemi e queste analisi, come un nuovo genere di problemi algoritmici,chiedendosi quanto la mancanza di coordinazione e il comportamento egois-tico inuenzassero il raggiungimento di un ottimo sociale, e introducendo ilconcetto di Price of Anarchy (PoA) come misura di questa inuenza. Essi sisono occupati di un semplice e particolare modello, denito KP-model , rapp-resentato da una rete formata da m link paralleli, tutti con la stessa capacità:questo è essenzialmente un problema di scheduling con m macchine e n jobsindipendenti di lunghezza wi.

In questo lavoro ci riferiamo ad un'estensione del KP-model, ossia ad unproblema di scheduling unrelated restricted: ognuno degli n jobs può essereschedulato solo su un sottoinsieme dellem macchine ed inoltre l'esecuzione diogni job impiega una quantità di tempo dierente per ognuna delle macchinesu cui può essere schedulato, ma compresa in un intervallo [wmin, wmax].Questo modello sarà analizzato ampiamente in virtù di dierenti funzioni diottimo sociale:

• Maximum Latency , che prevede di minimizzare la massima attesa peril completamento dell'esecuzione di un job;

5

• Server Latency , che equivale a minimizzare il lavoro totale eseguitodalle macchine;

• Total Latency , che si occupa di minimizzare l'attesa totale osservatadai jobs;

• Quadratic Latency , che anch'essa prova a essere una misura dell'attesatotale osservata dai jobs.

Per questo modello erano stati già ottenuti i seguenti risultati, riportatiin seguito in questo lavoro:

• Even-Dar et al. [14] hanno dimostrato l'esistenza di un equilibrio Nash;

• Awerbuch et al. [7] hanno dimostrato che per la Maximum Latency ilPrice of Anarchy è Θ(s+ logm

log(1+ log ms

)).

dove s = wmax

wmin.

Risultati ottenuti

In questo lavoro sono presentati interessanti risultati raggiunti per alcune diqueste funzioni:

• per la Server Latency abbiamo dimostrato che PoA = Θ(s);

• per la Total Latency abbiamo dimostrato che s ≤ PoA = O(max(s,logm

log(1+ log ms

)));

• per la Quadratic Latency abbiamo dimostrato che PoA = Θ(s2).

Oltre al problema di scheduling unrelated restricted ci occuperemo breve-mente anche del modello identical restricted, cioè tale che ognuno dei n jobspuò essere schedulato solo su un sottoinsieme delle m macchine, ma l'ese-cuzione di ogni job impiega la stessa quantità di tempo wi ∈ [0, 1] per og-nuna delle macchine su cui può essere schedulato. Hoefer e Souza [16] hannostudiato questo modello in funzione del traco totale w, ossia la somma deipesi wi di ciascun job, ed hanno individuato che il Price of Anarchy per laTotal Latency è Θ(n

√mw

). Tuttavia in questo lavoro evidenzieremo che laloro dimostrazione non è corretta e, attraverso le tecniche utilizzate nel casounrelated restricted, stabiliremo un nuovo bound di Θ( logm

log logm).

Riassumiamo nella tabella 1 tutti i risultati raggiunti.

6

Server La-

tency

Total Latency Quadratic

Latency

30.20

RestrictedUnrelated JobScheduling

30.20

PoA = Θ(s)

PoA = O(max(s,logm

log(1+ log ms

)))

30.20

PoA = Θ(s2)

PoA = Ω(s)

maxjcjc∗j

= Θ(max(s,logm

log(1+ log ms

)))

RestrictedIdentical JobScheduling

PoA = Θ( logmlog logm

)

Tabella 1: Nuovi risultati presentati in questo lavoro

Organizziazione

Nel resto del lavoro introdurremo prima il modello di Selsh Scheduling nelCapitolo 1, denendone le caratteristiche e descrivendo alcuni esempi in cuitale modello si adatta perfettamente. Nel Capitolo 2 introdurremo e spiegher-emo i concetti fondamentali dell'Algorithm Game Theory. Nel Capitolo 3saranno analizzati alcuni dei maggiori risultati ottenuti relativamente al Self-ish Scheduling. Inne, nel Capitolo 4 saranno riassunti tutti i risultati relativial modello unrelated restricted e presentati i nuovi risultati raggiunti.

Capitolo 1

Selsh Scheduling

1.1 Modello

Lo studio dello scheduling risale ai primi anni 50 e da allora una enormevarietà di problemi e di risultati ad esso relativi sono stati introdotti.

In generale un problema di scheduling si verica ogni qual volta ci sitrova di fronte ad n jobs che devono essere processati su m macchine. Inrealtà diversi problemi nascono in virtù di come tali jobs e tali macchinesono denite e dell'obiettivo che ci si pone di raggiungere. In particolare perquanto riguarda i jobs possiamo distinguere due macrocategorie:

• Unweighted Jobs, in cui i jobs sono tutti identici, quindi si può dire che∀ i : wi = 1;

• Weighted Jobs, ossia ogni job ha un arbitrario processing time.

In virtù delle caratteristiche delle macchine distinguiamo in:

• Identical Machines, tutte le macchine sono uguali e quindi per proces-sare lo stesso job impiegano tutte la stessa quantità di tempo;

• Related Machines, ad ogni macchina è associata una velocità qj e iltempo necessario per processare il job i di carico wi è

wi

qj;

• Unrelated Machines, dove ogni macchina è completamente diversa euno stesso job ha dei processing time diversi e non relati tra le diversemacchine.

Una ulteriore classicazione nasce da quali macchine possono essere utiliz-zate; si parla di:

7

CAPITOLO 1. SELFISH SCHEDULING 8

• Unrestricted Scheduling, quando ogni job può essere processato da qual-siasi macchina;

• Restricted Scheduling, se un job può essere processato solo su un sot-toinsieme delle macchine.

Ancora, relativamente ai jobs, possiamo distinguere:

• unsplittable job, cioè il job deve essere processato completamente dallastessa macchina;

• splittable job, per cui il job può essere diviso in task che possono essereeseguiti su macchine dierenti.

Inoltre, in relazione a come i job vengano processati, dierenziamo:

• sequential fashion, che fà sì che una volta cominciato il job deve es-sere processato completamente e un nuovo job dovrà attendere che lamacchina si liberi;

• round-robin fashion, che permette a tutti i jobs assegnati alla stessamacchina di attendere sostanzialmente la stessa quantità di tempo peril completamento del processing.

Inne, un'ulteriore distinzione viene fuori dall'obiettivo dello scheduling: ilmakespan è, senza dubbio, l'obiettivo su cui gli studiosi hanno concesso mag-giore attenzione, ma numerosi altri sono stati introdotti per far fronte allepiù svariate necessità.

L'informatica ha dedicato molta attenzione a questo problema, soprat-tutto come problema algoritmico, per cercare di calcolare il miglior assegna-mento di jobs alle macchine. Tuttavia, oggi ci sono numerosi esempi in cuinon c'è nessuna autorità globale capace di forzare l'applicazione di un taleassegnamento ottimo, ma gli agenti sono guidati nelle loro azioni solo dal pro-prio interesse. Questo naturalmente costringe ad adottare una impostazionedi Teoria dei Giochi, attraverso il quale analizzare cosa accade alla funzioneobiettivo.Al selsh scheduling , ovviamente si adattano tutte le categorie e le dis-tinzioni denite sopra, con tuttavia il diverso compito di dover confrontarela soluzione ottima, che può essere suggerita dà un'autorità centrale, con lasoluzione risultante dal comportamento egoistico degli agenti.In particolare i risultati raggiunti e presentati qui si riferiscono ad un modellodi restricted selsh scheduling con weighted e unsplittable jobs processati inround-robin fashion su unrelated machines e a diverse interessanti funzioni


obiettivo.Questo generale modello si adatta perfettamente a numerosi problemi re-ali che si vericano oggi giorno, come al selsh routing su link paralleli(sezione 1.2), all'associazione client-server in sistemi distribuiti (sezione 1.3)o all'associazione agli Access Point nelle reti wireless (sezione 1.4).

1.2 Selsh Routing

Oggi nella progettazione di molte reti di grandi dimensioni uno dei mag-giori sforzi è dedicato alla denizione di validi meccanismi di routing, ossiastabilire come debba essere scelto un path per il traco tra mittente e des-tinatario. La versione splittable di questo problema è quando il traco trai due agenti può essere soddisfatto da molti path contemporaneamente; laversione unsplittable, o discreta, in cui il traco è instradabile su un unicopath, risulta più complessa. Tuttavia, in molti casi, come in Internet, nellereti wireless o nelle rete overlay costruite su Internet il traco dal mittenteal destinatario è mandato su un singolo path e suddividere tale traco causaproblemi di riassemblamento al destinatario e per questo motivo è evitato.Considerando una rete in cui ogni link ha una legge per cui il traco determi-na la propria latenza, osserviamo come questo problema può essere facilmenteformalizzato come un problema di teoria dei giochi, vedendo gli utenti dellarete come agenti indipendenti che partecipano in un gioco non-cooperativo:ogni agente desidera usare il path di latenza minima dalla sua sorgente allasua destinazione, data la congestione causata dal resto degli agenti.Tuttavia il fatto che il routing sia soggetto al comportamento egoistico e non-cooperativo degli utenti, non toglie che il progettista si ponga un problemadi ottimizzazione ben preciso, in cui egli desidera ottimizzare un costo so-ciale, ovvero minimizzare il massimo ritardo (Maximum Latency) piuttostoche minimizzare la somma di tutti i ritardi tra gli agenti (Total Latency).

Sebbene quello del selsh routing è un problema vasto e di enorme appli-cabilità, nora ci si è concentrati soprattutto su un caso speciale di questoproblema, introdotto da Koutsoupias e Papadimitriou [17] in uno degli arti-coli basilari dell'Algorithm Game Theory, in cui la rete è composta semplice-mente da m link paralleli da un origine a una destinazione, tutti con la stessacapacità e il ritardo soerto da ogni agente è uguale alla quantità totale ditraco sul link selezionato. Sono inoltre presenti n agenti che hanno ognunouna quantità di traco wi, i = 1, . . . , n da mandare dall'origine alla desti-nazione. Si assume che il trasferimento del traco dell'agente i sul link jtermini quando terminano tutti i trasferimenti sul link j: questa assunzione


è realistica in quanto il traco può essere suddiviso in pacchetti, che sonomandati secondo modalità round-robin.

È facile vedere come il KP-model può essere ovviamente rappresentatocome un problema di selsh scheduling dove gli m link paralleli sono le mmacchine e gli n agenti gestiscono n jobs di durata wi ognuno. Si trattaquindi di scheduling unrestricted (ogni job ha accesso su tutti i link) su mac-chine identiche in round-robin fashion. Quindi studiare il problema di selshscheduling fornisce anche utili informazioni ad un semplice, ma signicativoproblema come quello del routing su link paralleli.

1.3 Selsh Client Assignment

Siccome gli utenti che accedono ai servizi di Internet crescono in numero edispersione, è diventato necessario, per migliorare le performance e la scal-abilità di tali servizi, distribuire i siti server per la fornitura del servizio.Tale distribuzione ha l'eetto beneco di ridurre la latenza di accesso e dimigliorare la scalabilità del servizio dividendo il carico tra i diversi siti. Ilproblema generato da tale scenario è come debba l'utente scegliere il serverappropriato.

Diversi sono i casi in cui tale problema si verica: molte reti aziendali sonoconnesse a molti service providers (ISPs) e la gestione di quale ISP usare inquale momento è soggetta solo alle politiche aziendali e alle scelte progettualidei sistemisti di rete. Ancora, Czumaj et al. [12] hanno investigato gli eettidel comportamento egoista in una Web server farm: i server distribuiti nelmondo memorizzano le di grosso carico come immagini grandi o embeddedles, e gli stream di richieste (spesso anche molto dierenti tra loro) chesarebbero stati normalmente diretti al web server del provider, ora devonoessere assegnati a tali nuovi web server. Un altro esempio, descritto da Suriet al. [26], riguarda i sistemi peer-to-peer (P2P), dove i dati sono spessoreplicati per ottenere un alto livello di disponibilità e di tolleranza ai guasti:in questo modo, gli utenti hanno spesso la scelta di molti host da cui scaricarei propri dati, scelta guidata dall'obiettivo di minimizzare il download time,mentre, d'altro canto, servendo dati a più utenti un host deve condividere lasua limitata banda tra questi utenti, incrementando così il download time diciascuno di essi.

In generale possiamo descrivere tutti questi problemi considerando uninsieme di n selsh client, ognuno dei quali deve scegliere uno tra m serverdisponibili. Ogni client i potrebbe essere connesso solo ad un sottoinsiemedegli m server, che possiamo indicare come l'insieme dei server permissibiliper i. I server possono avere velocità diverse, così come le richieste dei client


possono avere un carico dierente sul server. Ogni client vuole minimizzarela propria attesa e razionalmente preferisce un server veloce ad uno più lento.Infatti, la latenza di un server è inversamente proporzionale alla sua velocità,ma è direttamente proporzionale al carico: quindi il ritardo osservato daciascun client è soggetto al comportamento degli altri utenti.

Da tale descrizione si evince come anche in questo caso questi problemipossono essere visti semplicemente come problemi di selsh scheduling, incui i client rappresentino gli n jobs e i server le m macchine. Ancora unavolta, quindi, studiare questo generico problema fornisce informazioni utili anumerosi problemi che realmente si vericano in ambito informatico.

1.4 Associazione in reti 802.11-based

Con l'evolversi della tecnologia wireless si è diuso il concetto di WirelessMesh Network , una rete che consiste di nodi wireless che possono essereclient, router o entrambi: ciò permette di avere una backbone wireless chesupporta la trasmissione end-to-end e in cui ogni nodo è un router che inoltrapacchetti ad altri nodi, ma che può agire contemporaneamente come clienttrasmettendo i propri pacchetti.

Uno dei meccanismi fondamentali per garantire un'eciente comunicazioneè rappresentato dall'associazione dei client (STA) agli Access Point (AP) del-la Mesh Network. Nello standard IEEE 802.11 [2] tale procedura prevedeche una STA non associata collezioni informazioni relative agli AP attraver-so un'operazione di scanning attivo o passivo e quindi scelga sulla base ditali informazioni l'AP a cui ritiene sia più opportuno associarsi. Nello stan-dard, l'informazione che è usata è la forza del segnale ricevuto relativamenteai frame di management trasmessi dall'AP detto Received Signal StrengthReport Indicator (RSSRI).

Tuttavia è stato dimostrato che le policy di associazione basate sull'indi-catore RSSRI possono portare ad un ineciente uso delle risorse di rete[3], [8], [9]. Questo perché RSSRI fornisce informazioni solo per il canaledi downlink (dall'AP alla STA) e nulla per quanto riguarda la qualità delcanale, l'interferenza, la potenza di trasmissione dell'AP, le condizioni delcanale di uplink e le dimensioni della popolazione gestite da uno stesso AP.

Per questo motivo il Task Group IEEE 802.11s [1] raccomanda l'uso delprotocollo Radio Metric - Ad Hoc On Demand Distance Vector (RM-AODV)come protocollo di default: tale protocollo introduce una nuova metrica daassociare a ciascun router wireless detta airtime metric. Questa metricatenta di fornire alla STA una reale misura di quanto il canale sia occupato.


Athanasiou et al. [4] sono stati i primi a denire delle nuove proceduredi associazione e riassociazione che utilizzino tale metrica, che siano fullycompliant allo standard 802.11 e che siano compatibili con le implementazionicorrenti di questo standard. Nella loro procedura si fa sì che le STA, dopoaver acquisito le informazioni di cui necessitano, provvedano, diversamenteda quanto accade ora, ad eseguire i calcoli necessari a determinare il migliorAP: da notare è che le misure di due dierenti STA relative ad uno stessoAP possono essere completamente diverse tra loro, così come le misure dellastessa STA relative ad AP dierenti possono essere non correlate in alcunmodo. Inoltre è importante sottolineare che secondo lo standard 802.11 ognistazione può essere associata con solo un AP e così non è possibile unabiforcazione del traco prodotto da tale STA.

Tuttavia sia nel meccanismo di associazione standard, sia in quello in-trodotto da Athanasiou et al. le STA sono non-cooperative e si comportanoegoisticamente per ottimizzare le proprie performance: questo motiva quindilo studio di tali meccanismi attraverso l'attenta lente della Teoria dei Giochi.

Tuttavia anche in questo caso è facile ridurre il meccanismo di associ-azione indicato da Athanasiou et al. ad un problema di scheduling: le stazionirappresentano gli n jobs, gli access point le m macchine; ogni job porta uncarico su ogni macchina che dipende dal rate di trasmissione con cui la STAè interessato a trasmettere all'AP; il carico sull'access point è una funzionedel carico portato da ciascun job.

In particolare questo esempio giustica più degli altri la scelta del set-ting che verrà analizzato in questo lavoro: restricted, dato che le STA nonhanno la possibilità di accedere a qualsiasi AP nella rete; unrelated, datoche i rate di trasmissione selezionati, e quindi i carichi portati da ciascunodi esso, dipendono sia dalla stazione sia dall'access point a cui ci si vuoleassociare; unsplittable jobs, dato che non è permessa biforcazione del traf-co; round-robin fashion, perché eettivamente l'access point gestisce con-temporaneamente tutte le STA riducendo la banda dedicata a ciascuno diessa. Quindi, ancora una volta, è possibile vedere come i risultati analizzatiqui sono di enorme utilizzo pratico per sottolineare l'ecienza o meno diprotocolli, schemi e procedure che si presentano in molti sistemi.

Capitolo 2

Teoria dei giochi

2.1 Giochi e Equilibri

Un gioco è una rappresentazione formale di una situazione in cui un numerodi individui interagiscono in un setting di interdipendenza strategica: cioè ilbenessere di ogni individuo dipende non solo dalle proprie azioni, ma anchedalle azioni degli altri individui [20].

Più formalmente, un gioco consiste di un insieme di n giocatori 1, 2, . . . ,n. Ogni giocatore i ha un insieme di possibili strategie Si. Tale giocatorepartecipa al gioco selezionando una strategia si ∈ Si. Tuttavia il propriooutcome, l'esito del proprio gioco, non dipende solo dalla strategia selezionatama dall'intero vettore s = (s1, . . . , sn) ∈ S = ×iSi delle strategie scelteda tutti gli n giocatori. Ovviamente, ogni giocatore preferisce alcuni deipossibili outcome piuttosto che altri: per specicare tali preferenze spesso siusa assegnare, per ogni giocatore, un valore (un costo o un ricavo) vi : S → <a ciascuno di tali esiti.

Un gioco si conclude quando tutti i giocatori raggiungono una situazionedi stabilità, vale a dire una situazione in cui i giocatori sono contenti dell'out-come ricevuto e risulta dicile migliorare il proprio benessere. Formalmentequesta nozione di stabilità ha dato vita a diversi solution concepts.

Alcuni giochi, infatti, godono di una interessante proprietà: ognuno deigiocatori ha un unica best strategy, indipendente dalle strategie degli altrigiocatori. Diremo che i giochi con questa proprietà hanno una dominantstrategy solution. Più formalmente, indicando con si la strategia giocatada i e con s−i le strategie giocate da tutti gli altri giocatori e ridenendol'utilità vi(s) come vi(si, s−i), diremo che un vettore delle strategie s ∈ S èuna dominant strategy solution se

∀ i,∀ s−i,∀ s′

i, vi(si, s−i) ≥ vi(s′

i, s−i). (2.1)

13

CAPITOLO 2. TEORIA DEI GIOCHI 14

È importante sottolineare due importanti note: una dominant strategy so-lution potrebbe non dare la massima utilità a qualcuno dei giocatori, ossia,potrebbe non coincidere con quella che sarebbe stata la soluzione ottima perquei giocatori; il requisito che un gioco abbia una singola strategia dominanteper tutti i giocatori è estremamente rigido e molti pochi giochi lo soddis-fano, cosicché questo concetto di soluzione, nonostante la sua semplicità edimmediatezza, ha una ridotta applicabilità nello studio di molte situazionireali.

Dato ciò è necessario individuare una soluzione, un concetto di stabilitàche sia più ampiamente applicabile: ciò è senza dubbio rappresentato dallanozione di Nash Equilibrium [19], per cui nessun singolo giocatore può indi-vidualmente migliorare il proprio benessere modicando la propria strategia.Formalmente, un vettore delle strategie s ∈ S è un Nash Equilibrium se

∀ i, ∀ s′i, vi(si, s−i) ≥ vi(s′

i, s−i). (2.2)

Sostanzialmente, ogni giocatore gioca la sua migliore strategia assumendo chele strategie giocate da tutti gli altri giocatori siano ssate: questo porta afar sì che questa soluzione sia self-enforcing, nel senso che, una volta che unplayer devia da una congurazione iniziale, tutti gli altri adattano la propriastrategia a questi cambiamenti, no a che si raggiunga l'equilibrio, per cui anessuno conviene più deviare.Tuttavia anche per quanto riguarda gli equilibri Nash sono da sottolinearedue importanti note: in un gioco l'equilibrio Nash potrebbe non essere unicoe ciascuno dei dierenti equilibri potrebbe avere utilità ampiamente diverseper i giocatori; esistono giochi che non possiedono un equilibrio Nash. Ancorauna volta quindi, nonostante questo concetto di soluzione appaia convincenteed eciente, la sua non-unicità e la sua non-universalità la rendono in alcunicasi non adatta a descrivere applicazioni reali.

Per gli equilibri Nash appena descritti ci siamo riferiti a strategie pure, incui ogni giocatore deterministicamente sceglie una sola strategia. Tuttavia,possiamo considerare che i giocatori facciano le proprie scelte in manierarandom, assumendo tuttavia che essi siano risk-neutral, cioè tentino dimassimizzare il proprio payo atteso. Per denire tale concetto di soluzioneformalmente ammettiamo quindi che la scelta di un giocatore consista nel de-terminare una distribuzione di probabilità tra tutte le possibili strategie rifer-endoci quindi a strategie miste. Estendendo il concetto di soluzione denitoformalmente in (2.2) a tali strategie, introduciamo i Mixed Strategy NashEquilibria [19].In particolare Nash [19] ha dimostrato che ogni gioco con un insieme ni-to di giocatori e un insieme nito di strategie ha un Mixed Strategy Nash


Equilibrium: tuttavia tale dimostrazione è solo esistenziale e, anzi, è statoampiamente dimostrato che trovare tale equilibrio è un problema dicile.Quindi laddove l'universalità rende questo concetto abbastanza aascinanteper la sua pratica applicabilità, l'inecienza e la scarsa naturalezza delladenizione lo rendono invece spesso inadatto a tali studi.

Un ulteriore rilassamento del concetto di equilibrio Nash è quello di Cor-related Equilibrium introdotto da Aumann [5]: laddove in un equilibrio Nash igiocatori scelgono le loro strategie indipendentemente, in un equilibrio corre-lato un device di correlazione esterno, un coordinatore trusted, può scegliereuna distribuzione di probabilità per gli outcome e da questa derivarne unastrategia da suggerire ad ogni giocatore; se nessuno dei giocatori può incre-mentare la propria utilità attesa cambiando la strategia suggerita allora lasoluzione è un Correlated Equilibria.Sebbene questo concetto mantenga l'universalità dei Mixed Strategy NashEquilibrium essendone una generalizzazione, e sebbene la ricerca di tali equi-libri sia eciente, essi appaiano ancora più astrusi, innaturali e poco con-vincenti, tale da portarli ad una scarsa applicazione nell'analisi di situazionireali.

Ulteriori varianti del concetto di equilibrio Nash sono state introdotteper far fronte a problemi leggermente dierenti, come quelli in cui il giocoabbia molti turni di mosse, in cui quindi ogni giocatore può modicare lapropria strategia in base a quanto è accaduto nel turno precedente, o ancoracome quelli in cui gruppi di utenti possono cooperare modicando le pro-prie strategie ed ottenendo un outcome migliore per tutti: tuttavia questeestensioni, sebbene molto interessanti, sono per ora estranee all'obiettivo diquesto lavoro.

Infatti, in questo lavoro sostanzialmente utilizzeremo come concetto disoluzione quello dei Pure Strategy Nash Equilibria, anche perché il suo princi-pale difetto, la non-universalità, non sembra essere un problema per il nostromodello come evidenziato nella prossima sezione.

2.2 Congestion e Potential Games

I Congestion Games sono stati introdotti da Rosenthal [22], mostrando chetale classe di giochi ammette sempre un equilibrio Nash.Formalmente in un (general) congestion game ci sono un insieme nito dirisorse E (con |E| = m). La strategia si per un giocatore i è rappresentatadalla selezione di un particolare sottoinsieme di risorse in una famiglia disottoinsiemi permessi (Si). Il costo per il player i nel giocare la strategiasi è dato dalla somma dei costi di ciascuna risorsa selezionata. Tali costi


ck(·), chiamati congestion cost, sono solo funzioni di nk(s), cioè il numero digiocatori che selezionano la k-esima risorsa ek nello stato s = (s1, . . . , sn).Nello stato s l'utilità per il player i, vi(s) è:

vi(s) = −∑k∈si

ck(nk(s)) (2.3)

In un network congestion game la famiglia di insiemi Si è implicitamentepresentata come path in una rete. L'input è rappresentato da una rete (V,E),due nodi ai, bi ∈ V per ogni giocatore i e una funzione di ritardo per og-ni arco: l'insieme di tutti i path da ai a bi identica l'insieme di strategieper il player i. Ci sono sostanzialmente due varianti di network congestiongames : la variante asimmetrica, in cui è consentito che i player abbianodiverse strategie, e quella simmetrica, dove tutti i giocatori condividono lastessa strategia, ossia hanno gli stessi endpoint a e b.

Particolarmente interessanti in questa classe di problemi sono i routinggames , che fanno luce su un importante problema pratico: come instradareil traco in un grande rete di comunicazione, senza autorità centrale, spe-cialmente per quanto riguarda reti con source routing, in cui ogni utentesceglie una rotta completa per il proprio traco, e per quanto riguarda retiin cui il traco è instradato in maniera distribuita, sensibile alla congestione.Sono noti due dierenti modelli di routing games : il non-atomic selsh rout-ing , introdotto da Pigou [21] e formalmente denito da Wardrop [27], in cuisono presenti un gran numero di giocatori, ognuno dei quali controlla unafrazione negligibile del traco totale; l'atomic selsh routing , consideratoper primo da Rosenthal [23], dove ogni giocatore controlla una quantità nontrascurabile di traco.

Una variante leggermente diversa, denita single-choice congestion gameè quella in cui ogni player può scegliere soltanto una risorsa: in questo casopossiamo dire che n giocatori condividono un insieme di m risorse. È facilenotare come un single-choice congestion game può essere facilmente vistocome un symmetric network congestion game su una rete con solo due nodi eun insieme di archi paralleli o equivalentemente ad un problema di schedulingcome quelli analizzati in questo lavoro.

Come già detto, Rosenthal in [22] ha mostrato che

Theorem 2.2.1. Ogni (general) congestion game possiede almeno un equi-librio Nash puro.

La dimostrazione si basa sull'introduzione della seguente funzione:

P (s) =m∑k=1

nk(s)∑y=1

ck(y) (2.4)


ed evidenziando che qualsiasi variazione a questa funzione corrisponde anchead una variazione (dello stesso segno) nell'utilità di qualche player. Per cuiil minimo di questa funzione, dovrà per forza corrispondere ad uno stato incui nessun giocatore può migliorare la propria utilità, ossia ad un equilibrioNash.

La funzione (2.4) è stata denita potential function da Monderer e Shap-ley [18]: tale concetto è direttamente collegato con i congestion games, inquanto traccia il global payo del sistema. Tuttavia tale funzione poten-ziale può assumere diverse forme: la più generale, quella di generalized ordinalpotential , prevede che la funzione P : S → < per un gioco Γ , sia tale che ∀i, ∀ s−i ∈ S−i e ∀ si, s

′i ∈ Si

vi(si, s−i)− vi(s′

i, s−i) > 0 implica P (si, s−i)− P (s′

i, s−i) > 0 (2.5)

Deniamo, inoltre, ordinal potential function la funzione P : S → < per ungioco Γ , se ∀ i, ∀ s−i ∈ S−i e ∀ si, s

′i ∈ Si


i, s−i) > 0 i P (si, s−i)− P (s′

i, s−i) > 0 (2.6)

o equivalentemente

sgn(vi(si, s−i)− vi(s′

i, s−i)) = sgn(P (si, s−i)− P (s′

i, s−i)) (2.7)

Indichiamo, invece, con w-potential , dove w = (wi)i∈1,...,n, o weighted po-tential la funzione P : S → < per un gioco Γ tale che ∀ i, ∀ s−i ∈ S−i e ∀si, s

′i ∈ Si


i, s−i) = wi(P (si, s−i)− P (s′

i, s−i)) (2.8)

Inne, introduciamo l'exact potential function P : S → < per un gioco Γtale che ∀ i, ∀ s−i ∈ S−i e ∀ si, s

′i ∈ Si


i, s−i) = P (si, s−i)− P (s′

i, s−i) (2.9)

La classe di giochi che ammettono un potenziale sono detti potential games .Monderer e Shapley [18], hanno individuato alcuni importanti risultati rela-tivi a tali giochi.

Theorem 2.2.2. Ogni ordinal potential game nito possiede un equilibrioNash puro.

Theorem 2.2.3. Ogni congestion game è un potential game.

Theorem 2.2.4. Ogni (exact) potential game nito è isomorfo a un conges-tion game.


I teoremi 2.2.3 e 2.2.4 sostanzialmente dimostrano quindi che congestiongame e potential game sono praticamente equivalenti.

Tuttavia, nonostante tale equivalenza e nonostante abbiamo già vistocome il nostro modello è riconducibile ad un congestion game, nel capitolo 4,mostreremo che esiste anche un ordinal potential function.

2.3 Price of Anarchy

Come già sottolineato in precedenza nella sezione 2.1, un equilibrio, ovverol'outcome raggiunto spontaneamente da agenti razionali ed egoisti, è inferiorealla soluzione che potrebbe essere centralmente indicata da una autorità cheregola e monitora la rete al ne di ottimizzare una certa funzione obiettivo.

Il Price of Anarchy , denito da Koutsoupias e Papadimitriou [17] è la piùpopolare misura dell'inecienza di tali equilibri: sostanzialmente, nell'averea che fare con questo nuovo genere di problemi algoritmici, è necessario inves-tigare il costo della mancanza di coordinazione, come per gli algoritmi on-lineè necessario investigare il costo della mancanza di informazione e per gli al-goritmi di approssimazione il costo della mancanza di risorse computazionaliillimitate. Così come avviene in queste aree, per valutare la perdita al sis-tema si utilizza il worst-case approach, ossia l'ottimo viene confrontato conil peggiore equilibrio Nash.

Formalmente, quindi, il Price of Anarchy di un gioco è denito come ilrapporto tra il peggior valore della funzione obiettivo in corrispondenza diun equilibrio del gioco e il valore della funzione obiettivo in corrispondenzadella soluzione ottima.

Il Price of Anarchy ha un enorme interesse pratico: identicare giochiin cui tale misura è prossima ad 1, signica dire che tutti gli equilibri sonouna buona approssimazione della soluzione ottima, per cui il comportamen-to egoista degli agenti è da preferirsi alla costosa o dicilmente praticabileinstallazione di un controllo centrale.

Tuttavia, l'esistenza di un solo equilibrio ineciente tra tanti quasi ottimi,porterebbe ad un prezzo dell'anarchia molto alto. Per questo Schulz e StierMoses [24] hanno introdotto il concetto di Price of Stability di un gioco, comeil rapporto tra il miglior valore della funzione obiettivo in corrispondenza diun equilibrio del gioco e il valore della funzione obiettivo in corrispondenzadella soluzione ottima: oltre a dierenziare tra giochi in cui tutti gli equilibrisono inecienti e giochi in cui solo qualche equilibrio è ineciente, il Priceof Stability è signicativo in quanto può essere visto come indicativo dellasoluzione che una autorità centrale può proporre agli utenti egoisti.


Possiamo quindi concludere che laddove il Price of Anarchy misura ilrischio massimo che l'assenza di coordinamento comporta, il Price of Stabilityrappresenta la degradazione necessaria a cui si va incontro facendo a menodi una autorità centrale.

In questo lavoro ci occuperemo di calcolare il Price of Anarchy per ilnostro modello, relativamente a dierenti funzioni obiettivo.

Capitolo 3

Stato dell'arte

In questo capitolo presenteremo alcuni dei maggiori risultati relativi al mod-ello del selsh scheduling presentato nel Capitolo 1. Prima, tuttavia, sarànecessario chiarire la notazione che sarà usata sia in questo che nel capitolosuccessivo.

3.1 Notazione

Il modello di riferimento in questo lavoro è rappresentato dal problema diselsh scheduling presentato nel Capitolo 1, in cui sono presenti n jobs e mmacchine.

∀ i ∈ 1, . . . , n deniamo con Ai ⊆ 1, . . . ,m l'insieme delle macchineammissibili per i.

Qualora ci riferiamo al caso di unrestricted selsh scheduling (sezione 1.1)allora ∀ i ∈ 1, . . . , n Ai = 1, . . . ,m, cioè tutte le macchine sono ammis-sibili.

∀ i ∈ 1, . . . , n ∀ j ∈ Ai deniamo con wij ∈ [wmin, wmax] con wmin > 0, ilcarico del job i sulla macchina j.

Nel caso identical (sezione 1.1) ∀ i ∈ 1, . . . , n ∀ j ∈ Ai deniamo conwij = wi ∈ [wmin, wmax] con wmin > 0, il carico del job i sulla macchina j:ossia un job ha lo stesso carico su qualsiasi macchina j ∈ Ai.

Nel caso related (sezione 1.1) ∀ j ∈ 1, . . . ,m deniamo con qj ≥ 1 lavelocità della macchina j e ∀ i ∈ 1, . . . ,m deniamo con wi ∈ [wmin, wmax]con wmin > 0, la lunghezza del job i: in questo caso il carico del job i sullamacchina j è wij = wi

qj.

20

CAPITOLO 3. STATO DELL'ARTE 21

Nel caso di unweighted jobs (sezione 1.1) ∀ i ∈ 1, . . . , n wi = 1 sia inpresenza di macchine identiche sia in presenza di macchine relate (il caso dimacchine non relate non ha più senso di esistere con jobs non pesati).

Deniamo s = wmax

wmin.

Deniamo un assegnamento di jobs alle macchine attraverso una matricen×m: in particolare ci riferiremo ad x come all'assegnamento in equilibrioNash e a x∗ come all'assegnamento ottimo. Quindi diremo

xij = 1, se i è stato assegnato a j nella soluzione in equilibrio;

xij = 0, altrimenti.

e allo stesso modox∗ij = 1, se i è stato assegnato a j nella soluzione ottima;

x∗ij = 0, altrimenti.

Considereremo sempre un processing in round-robin fashion (sezione 1.1),per cui, dato l'assegnamento x:

• ∀ j ∈ 1, . . . ,m deniamo con cj =∑

i:xij=1wij il carico presente sullamacchina j nella soluzione in equilibrio Nash;

• ∀ j ∈ 1, . . . ,m deniamo con nj = |i : xij = 1| il numero di jobspresenti sulla macchina j nella soluzione in equilibrio Nash (osserviamoche cj = nj in presenza di unweighted jobs (sezione 1.1));

• ∀ i ∈ 1, . . . , n deniamo con ji = j : xij = 1 la macchina su cui iljob i è assegnato nella soluzione in equilibrio Nash.

Le stesse denizioni possiamo possiamo darle anche in funzione dell'assegna-mento ottimo x∗:

• ∀ j ∈ 1, . . . ,m deniamo con c∗j =∑

i:x∗ij=1wij il carico presente sullamacchina j nella soluzione ottima;

• ∀ j ∈ 1, . . . ,m deniamo con n∗j = |i : x∗ij = 1| il numero dijobs presenti sulla macchina j nella soluzione ottima (osserviamo chec∗j = n∗j in presenza di unweighted jobs (sezione 1.1));

• ∀ i ∈ 1, . . . , n deniamo con j∗i = j : x∗ij = 1 la macchina su cui iljob i è assegnato nella soluzione ottima.


Dato che la soluzione x è in equilibrio Nash per essa dovrà valere la condizioneNash:

∀ i ∈ 1, . . . , n ∀ j ∈ Ai cji ≤ cj + wij (3.1)

Inne faremo riferimento alle seguenti funzioni di costo sociale:

• Maximum Latency , che prevede di minimizzare la massima attesa peril completamento dell'esecuzione di un job; per tale funzione obiettivo

il costo della soluzione in equilibrio Nash è C(NASH) = maxj cj;

il costo della soluzione ottima è C(OPT ) = maxj c∗j .

• Server Latency , che equivale a minimizzare il lavoro totale eseguitodalle macchine (osserviamo che tale obiettivo ha senso solo nel casounrelated (sezione 1.1)); per tale funzione obiettivo

il costo della soluzione in equilibrio Nash è C(NASH) =∑

j cj;

il costo della soluzione ottima è C(OPT ) =∑

j c∗j .

• Total Latency , che si occupa di minimizzare l'attesa totale osservatadai jobs; per tale funzione obiettivo


i cji =∑j njcj;


i c∗j∗i

=∑

j n∗jc∗j .

• Quadratic Latency , che anch'essa prova a essere una misura dell'attesatotale osservata dai jobs (osserviamo che nel caso di unweighted jobs(sezione 1.1) questa coincide con la Total Latency); per tale funzioneobiettivo


iwijicji=

∑j(cj)

2 (per il caso related C(NASH) =∑

iwicji 6=∑

j(cj)2);


iwij∗i c∗j∗i

=∑

j(c∗j)

2

(per il caso related C(OPT ) =∑

iwic∗j∗i6=

∑j(cj)

2).

3.2 Unrestricted Job Scheduling

I primi due risultati che analizziamo si riferiscono ad un problema di unre-stricted selsh scheduling su macchine relate e weighted jobs (sezione 1.1).Il primo risultato, dovuto a Czumaj and Vöcking [13], si riferisce alla Maxi-mum Latency ed è particolarmente interessante perché le tecniche introdotte


sono state molto utilizzate in numerosi lavori successivi per individuare ungran numero di bound relativi al Price of Anarchy per il selsh scheduling.Il secondo risultato presentato invece è opera di Hoefer e Souza [15] e uti-lizza come funzione obiettivo quella della Total Latency : questo è uno deipochi risultati, insieme a quelli presentati da Berembrink et al. [10], relativia questa funzione obiettivo in un setting con weighted jobs.

Entrambi i risultati presentati sono essenzialmente tight e provvederemoa presentare sia l'upper che il lower bound.

3.2.1 Maximum Latency

Dimostriamo ora che il Price of Anarchy è Θ( logmlog logm

), assumendo che lemacchine siano in ordine decrescente di velocità, ossia q1 ≥ · · · ≥ qm.

Upper Bound

Fissiamo un equilibrio Nash e normalizziamo i pesi wi di ogni job tali cheC(OPT ) = 1; dimostriamo ora che C(NASH) = O( logm

log logm).

Lemma 3.2.1.1. C(NASH) ≤ Γ (−1)(m) + 1 = O( logmlog logm

).

Dimostrazione: Per k ≥ 1 deniamo jk l'indice più piccolo in 0, 1, . . . ,mtale che cjk+1 < k o, se non esiste tale indice, jk = m. Osserviamo che:

• per ogni k ≥ 1 con 0 < jk ≤ m, tutte le macchine j ≤ jk hanno caricoalmeno k;

• per ogni k ≥ 1 con 0 ≤ jk < m, la macchina jk + 1 ha carico minore dik;

Deniamo C∗ = bC(NASH)−1c. Mostreremo che j1 ≥ C∗!, che, combinan-dolo con l'ovvio bound j1 ≤ m fornisce il risultato desiderato.

Per stimare j1, prima stimiamo jC∗ .

Claim 3.2.1.2. jC∗ ≥ 1, da cui c1 ≥ C∗.

Dimostrazione: Per assurdo, assumiamo jC∗ = 0. Questo implica chec1 < C∗ ≤ C(NASH) − 1. Sia j∗ la macchina più carica, allora c1 + 1 <C(NASH) = cj∗ .

Osserviamo che tutti i jobs i assegnati a j∗ sono tali che

wi > q1. (3.2)

Infatti, se un job i avesse peso wi ≤ q1, allora c1 + wi

q1≤ c1 + 1 ≤ cj∗ , che

viola la condizione Nash (3.1).


Osserviamo inoltre che

C(OPT ) ≥ maxiwimaxj qj

. (3.3)

Ora, combinando le disuguaglianze (3.2) e (3.3), otteniamo che la nostraassunzione iniziale (C(OPT ) = 1) è violata, dimostrando così l'assurdo.

Ora diamo un lower bound per jk in funzione di jk+1.

Claim 3.2.1.3. Per k ≥ 1, jk ≥ (k + 1)jk+1.

Dimostrazione: Sia T l'insieme di jobs assegnati alle macchine 1, . . . ,jk+1 e indichiamo con OPT l'allocazione ottima.

Osserviamo che OPT non può assegnare i jobs di T a una macchinaj, j > jk. Sia wT , il peso minimo tra i jobs in T . Il carico delle macchinein 1, . . . , jk+1 è, per denizione, almeno k + 1, mentre, per denizione, ilcarico sulla macchina jk+1 è minore di k. Perciò la condizione Nash comportache wT > qjk+1, altrimenti al job corrispondente converrebbe spostarsi sullamacchina jk+1. Supponiamo per assurdo che OPT assegna i jobs di T a unamacchina j, j > jk per cui wT

qj≥ wT

qjk+1> 1, che insieme alla diseguaglianza

(3.3), come prima, porta a violare la condizione che C(OPT ) = 1.Quindi, in OPT , tutti i jobs di T sono allocati su macchine in 1, . . . , jk.

Sia WT la somma dei pesi dei jobs in T , osserviamo che

WT =∑i∈T

wi =

jk+1∑j=1

cjqj.

Perciò, dato che ∀ j ≤ jk+1, cj ≥ k + 1, abbiamo che

WT =

jk+1∑j=1

cjqj ≥ (k + 1)

jk+1∑j=1

qj (3.4)

D'altro lato, dato che C(OPT ) = 1 e che OPT alloca tutti i jobs in T amacchine in 1, . . . , jk, otteniamo

WT ≤jk∑j=1

qj (3.5)

Combinando le disuguaglianze (3.4) e (3.5) abbiamo∑jk

j=1 qj ≥ (k + 1) ·∑jk+1

j=1 qj. Ora, dato che le velocità delle macchine sono non-decrescenti,risulta che jk ≥ (k + 1)jk+1.

Iterando questa proprietà osserviamo che j1 ≥ C∗!jC∗ ≥ C∗!, e da quirisaliamo al risultato desiderato.


Lower Bound

Senza perdita di generalità, lasciamo che√m sia un intero. Consideriamo

K + 1 gruppi di macchine 0, 1, . . . , K. I gruppi sono deniti come segue:

• per 1 ≤ k ≤ K, il numero di macchine nel gruppo k è uguale a√m ·

K!k!

(nota che per 1 ≤ k < K il numero di macchine nel gruppo k èesattamente (k + 1) volte il numero di macchine nel gruppo k + 1);

• il numero di macchine nel gruppo 0 è almeno√m ·K!;

• per 0 ≤ k ≤ K, la velocità delle macchine nel gruppo k è 2k;

• per 0 ≤ k ≤ K, per ogni macchina nel gruppo k, ci sono esattamentek jobs di peso 2k assegnati ad essa nella soluzione S.

Da tale suddivisione risulta che√m ·

∑Kk=0

K!k!≤ m, il che è vero per K ≤

Γ (−1)(√me

)− 1 = Ω( logmlog logm

).Innanzitutto osserviamo che C(S) = K. Se una macchina j è nel gruppo

k allora

cj =k · 2k

2k= k. (3.6)

Quindi le macchine nel gruppo K avranno proprio carico K.Osserviamo inoltre che S è in equilibrio Nash. Consideriamo un job i

che è allocato a una macchina nel gruppo k ≥ 1 e sia j 6= r una qualsiasimacchina nel gruppo t, 0 ≤ t ≤ K. Per provare che il sistema è in equilibrioNash, ci basterà provare che cj + wi

qj≥ cji : ma, essendo cji = k, cj = t (per

la (3.6)) e wi

qj= 2k−t, dovremo dimostrare che t+ 2k−t ≥ k, il che è vero per

qualsiasi t e k non negativi.Inne, osserviamo che C(OPT ) ≤ 2. Infatti, allocando tutti i jobs asseg-

nati a macchine nel gruppo k, k ≥ 1, nella soluzione S a macchine nel gruppok − 1, avremmo esattamente k ·

√m · K!

k!=√m · K!

(k−1)!jobs di peso 2k su

√m · K!

(k−1)!macchine, ognuna delle quali ha velocità 2k−1. Quindi assegnando

ogni job ad una macchina diversa, il costo di ogni macchina è al più 2.Da qui, il Price of Anarchy è ≥ K

2= Ω( logm

log logm).

3.2.2 Total Latency

Dimostriamo ora, assumendo che le macchine siano in ordine decrescentedi velocità, ossia q1 ≥ · · · ≥ qm, che tali velocità siano normalizzate, ossiaqm ≥ 1 e che i jobs siano tali che wi ∈ [0, 1], che n

2w≤ PoA ≤ n

w+ m2+m

w2 ,indicando con w =

∑iwi > 0, il peso totale dei jobs.


Upper bound

Lemma 3.2.2.1. C(OPT ) ≥ w2Pj qj

Dimostrazione: Osserviamo che wi ≤ 1, il che implica che C(OPT ) =∑j n∗jc∗j ≥

∑j(c∗j)

2. Provando a minimizzare la funzione∑

j

t2jqj

soggetta alvincolo che

∑j tj = w, dove quindi tj rappresenta la somma dei pesi dei

jobs assegnati alla macchina j, osserviamo che tale minimo è ottenuto incorrispondenza della scelta tj =

w·qjPmk=1 qk

. Quindi, C(OPT ) ≥∑

j(c∗j)

2 ≥∑j

t2jqj≥

∑j

(w·qj)2qj(·

Pmk=1 qk)2

= w2Pj qj

, c.v.d..

Lemma 3.2.2.2. C(NASH) ≤ n(w+m2+m)Pj qj

Dimostrazione: Distinguiamo tra macchine veloci e macchine lente: unamacchina j è veloce se qj ≥ 1

m·∑m

k=1 qk (tale denizione implica che esistasempre almeno una macchina veloce ed in particolare, dato l'ordinamentodelle macchine, che la macchina 1 è veloce), altrimenti è lenta. Indichiamo,come sopra, con tj la somma dei pesi dei jobs assegnati a j, ossia tj =∑

i:xij=1wi. Indichiamo con tj, il carico assegnato alla macchina j, in unaideale allocazione perfettamente bilanciata, cioè tj =

qj ·wPmk=1 qk

e osserviamo

che possiamo riscrivere tj come tj +δj: utilizzando tale notazione osserviamo

che cj =tj+δjsj

= wPmk=1 qk

+δjqj.

Deniamo yj =δjqj. Assumiamo che |yj| ≤ m

qj. Inoltre, notiamo che la

condizione Nash (3.1) implica che, per un job i assegnato alla macchina jnella soluzione in equilibrio, cj ≤ c1 + wi

q1≤ c1 + 1

q1. Ricordandoci che la

macchina 1 è veloce, ossia 1q1≤ mPm

k=1 qk, avremo

C(NASH) =∑j

njcj ≤∑j

nj(c1 +1

q1) = n(c1 +

1

q1) ≤ n(

w∑mk=1 qk

+

+ |y1|+m∑mk=1 qk

) ≤ n(w∑mk=1 qk

+m

q1+

m∑mk=1 qk

) ≤ n(w +m2 +m)∑mk=1 qk

.

Ci rimane da provare nel claim seguente che l'assunzione fatta è corretta.

Claim 3.2.2.3. |yj| ≤ mqj

Dimostrazione. Diciamo che una macchina j è overloaded se δj > 0⇒ yj > 0,underloaded se δj < 0⇒ yj < 0 e balanced, altrimenti. Notiamo che∑

j

tj =∑i

wi = w (3.7)


e ∑j

tj =∑j

(tj + δj) =∑j

qj · w∑mk=1 qk

+∑j

δj = w +∑j

δj (3.8)

Da (3.7) e (3.8) risulta quindi che∑

j δj = 0, il che signica che se c'è unamacchina overloaded dovrà per forza esserci anche una macchina underloaded.

Se tutte le macchine fossero balanced avremmo che |yj| = 0 e il claimsarebbe banalmente dimostrato. Quindi consideriamo che esiste una macchi-na k underloaded e una macchina j overloaded. Supponiamo che k riceva unjob arbitrario i dalla macchina j, il suo carico sarà ck + wi

qk. La condizione

Nash (3.1) stabilisce che ck + wi

qk≥ cj: questo signica che spostando un

solo job da una macchina overloaded ad una macchina underloaded, trasfor-ma quest'ultima in overloaded. Inoltre essendo wi

qk≤ 1

qk, questo implica che

|yj| ≤ 1qk.

Cerchiamo ora di valutare il numero di jobs che è necessario rimuovereda una macchina overloaded j, per renderla underloaded o balanced. Sup-poniamo ci siano u macchine underloaded e che migriamo u jobs da j aognuna delle dierenti macchine underloaded. Supponiamo che j sia ancorasovraccarica: questo è assurdo, perché, da quanto notato in precedenza, nonesistono più macchine underloaded, il che contraddice il fatto che

∑j δj = 0.

Siccome ogni job migrato contribuisce al più di 1qj, avremo che |yj| ≤ u

qj≤ m

qj,

c.v.d..

Mettendo insieme i risultati del Lemma 3.2.2.1 e del Lemma 3.2.2.2,otteniamo l'upper bound per il Price of Anarchy di n

w+ m2+m

w2 .

Lower Bound

Consideriamo l'esistenza di due macchine entrambi di velocità unitaria e unnumero pari di jobs. Sia w un intero positivo pari e deniamo i pesi dei jobsnel modo seguente: w1 = w2 = · · · = ww = 1 e ww+1 = · · · = wn = 0.

L'allocazione ottima assegna i w jobs di peso 1 alla macchina 1, i restantialla macchina 2: il costo di questa soluzione è C(OPT ) = w2.

Invece, la soluzione che assegna w2jobs di peso 1 e n−w

2jobs di peso 0 a

ciascuna macchina è in equilibrio, poiché nessun job migliorerebbe la proprialatenza, migrando da una macchina all'altra: il costo di questa soluzione èC(NASH) = nw

2, da cui otteniamo il lower bound per Price of Anarchy di

n2w.


3.3 Restricted Job Scheduling

In questo paragrafo consideriamo un problema di restricted selsh schedulingsu macchine relate e unweighted jobs (sezione 1.1) (in questo caso ricordiamoche cj = nj). Il risultato mostrato qui si riferisce ad una funzione di costosociale di total latency : il modello restricted rende particolarmente interes-sante questa dimostrazione, poiché le tecniche utilizzate nel caso unrestrict-ed, basate sopratutto sulla possibilità di spostare un job da una macchinaa qualsiasi altra, falliscono in questa occasione. Invece, nella dimostrazioneseguente, sarà utilizzata un'altra tecnica abbastanza diusa, che introduce ilconcetto di Nash Inequality .

Per questo modello il risultato è tight e stabilisce che 2.5−ε ≤ PoA ≤ 2.5:l'upper bound è dovuto a Suri et al. [25], mentre il lower bound è statoindividuato da Caragiannis et al. [11].

Upper Bound

Dalla condizione Nash (3.1) abbiamo che per ogni i:

njiqji≤nj∗i + 1

qj∗i(3.9)

Deniamo ∀ j ∈ 1, . . . ,m Nj = i : xij = 1 e N∗j = i : x∗ij = 1(osserviamo che nj = |Nj| =

∑mk=1 |Nj ∩N∗k | e n∗k = |N∗k | =

∑mj=1 |Nj ∩N∗k |).

Osserviamo che, sommando la diseguaglianza (3.9) per ogni i, otteniamo laseguente Nash Inequality :

C(NASH) =n∑i=1

njiqji

=m∑j=1

(nj)2

qj=

m∑j=1

njqj

m∑k=1

|Nj ∩N∗k | =

=m∑k=1

m∑j=1

njqj|Nj ∩N∗k | ≤

m∑k=1

m∑j=1

nk + 1

qk|Nj ∩N∗k | =

=m∑k=1

nk + 1

qk

m∑j=1

|Nj ∩N∗k | =m∑j=1

(nj + 1)n∗jqj

(3.10)

È facile vericare che

njn∗j =

1

3(nj)

2 +3

4(n∗j)

2 − 1

3(nj −

3

2n∗j)

2. (3.11)


Dalla Nash Inequality (3.10) dall'uguaglianza (3.11) otteniamo:

C(NASH) ≤m∑j=1

njn∗j + n∗jqj

=m∑j=1

1

qj(1

3(nj)

2 +3

4(n∗j)

2 + n∗j−

− 1

3(nj −

3

2n∗j)

2) ≤m∑j=1

1

qj(9

8(n∗j)

2 +3

2n∗j −

1

2(nj −

3

2n∗j)

2).

(3.12)

È facile dimostrare che 98(n∗j)

2 + 32n∗j − 1

2(nj− 3

2n∗j)

2 ≤ 52(n∗j)

2, riscrivendo talediseguaglianza come

n∗j(3−11

4n∗j)

2 ≤ (nj −3

2n∗j)

2 (3.13)

e osservando che (3.13) è trivialmente vericata per n∗j = 0 o per n∗j ≥ 2,mentre per n∗j = 1 è sempre vericato in quanto nj può assumere solo valoriinteri.

Mettendo insieme tale dimostrazione con la diseguaglianza (3.12) otte-

niamo che C(NASH) ≤ 52

∑mj=1

(n∗j )2

qj= 5

2C(OPT ), ovvero che PoA ≤

2.5.

Lower Bound

Per trovare tale bound, rappresentiamo un gioco come un grafo diretto (gamegraph), che ha un nodo per ogni macchina, e un arco diretto per ogni job: ladirezione dell'arco è dalla macchina a cui il job è associato nell'assegnamentoottimo alla macchina a cui è invece associato nell'assegnamento in equilibrioNash.

Noi costruiamo un game graph G consistente di un albero binario com-pleto con k + 1 livelli e 2k+1 − 1 nodi; inoltre ad ogni foglia è collegata unalinea di k + 1 archi e k + 1 nodi addizionali. Il grafo G ha quindi 2k + 2livelli 0, . . . , 2k + 1, con 2i nodi a livello i per i = 0, . . . , k e 2k nodi ai livellik + 1, . . . , 2k + 1.

• Le macchine corrispondenti ai nodi a livello i = 0, . . . , k− 1 hanno unavelocità qi = (3

2)i;

• le macchine corrispondenti ai nodi a livello i = k, . . . , 2k hanno unavelocità qi = (3

2)k−12i−k;

• le macchine corrispondenti ai nodi a livello 2k + 1 hanno una velocitàq2k+1 = (3

2)k−12k.


L'assegnamento dove tutti i jobs sono allocati alle macchine corrisponden-ti al vertice più vicino alla radice del game graph, può essere facilmentevericato che è un equilibrio Nash: quindi C(NASH) =

∑k−1i=0 4 · 2i(2

3)i +∑2k

i=k(23)k−1(1

2)i−k = 15(4

3)k − (2

3)k−1 − 12.

Se consideriamo l'assegnamento dove tutti i jobs selezionano la macchinacorrispondente al vertice più lontano dalla radice, il suo costo certamentenon sarà migliore del costo dell'assegnamento ottimo, quindi C(OPT ) ≤∑k−1

i=1 2i(23)i +

∑2ki=k 2k(2

3)k−1(1

2)i−k + 2k(2

3)k−1(1

2)k = 6(4

3)k − 4.

Quindi, per ogni ε > 0 e per k sucientemente largo, PoA = C(NASH)C(OPT )

≥52− ε.

3.4 Routing Games

Come abbiamo evidenziato nella sezione 1.2 c'è una strettissima relazionetra i problemi di selsh scheduling e quelli di selsh routing : in particolare,il primo può essere visto come un caso speciale del secondo, quindi upperbound per quest'ultimo, saranno, ovviamente, validi anche per lo scheduling.

In questa sezione analizziamo un risultato che, presentato da Awerbuchet al. [6] relativamente ad un generico routing game, possiamo facilmenteestendere ad un problema di restricted selsh scheduling su macchine relatee weighted jobs (sezione 1.1). Il risultato mostrato qui si riferisce ad unafunzione di costo sociale di quadratic latency : ancora una volta la tecnicautilizzata si basa sull'utilizzo della Nash Inequality . La diversa tecnica diapprossimazione utilizzata qui è risultata utile per dimostrare uno dei nostririsultati (sezione 4.5).

Sebbene il risultato in [6] fosse tight, il lower bound si riferisce ad unagenerica rete, il che lascia aperto il problema di stabilire se esso sia valido omeno per un problema di scheduling.

Di seguito forniamo, invece, la dimostrazione per l'upper bound al Priceof Anarchy di 3+

√5

2≈ 2.618, adattata per il problema di scheduling. Innanz-

itutto scriviamo la Nash Inequality :

C(NASH) =∑i

wicji ≤∑i

wi(cj∗i +wiqj∗i

) ≤∑i

wi(cj∗i + c∗j∗i ) =

=∑j

c∗j(cj + c∗j) = C(OPT ) +∑j

c∗jcj.(3.14)

In (3.14) rimane quindi da trovare un bound per∑

j c∗jcj, che possiamo


ottenere mediante la diseguaglianza di Cauchy-Schwartz :∑j

c∗jcj ≤√∑

j

(c∗j)2

√∑j

(cj)2 =√C(NASH)

√C(OPT ). (3.15)

Mettendo insieme (3.14) e (3.15) e dividendo tutto per C(OPT ) otteni-amo che

PoA =C(NASH)

C(OPT )≤ 1 +

√C(NASH)√C(OPT )

= 1 +√PoA. (3.16)

Ponendo x = PoA in (3.16), elevando al quadrato entrambi i lati delladisequazione e risolvendola otteniamo il bound desiderato.

Capitolo 4

Unrelated Restricted Scheduling

In questo capitolo presenteremo i risultati relativi al modello di restrictedselsh scheduling su macchine unrelated (sezione 1.1). Presenteremo sia ladimostrazione di esistenza introdotta da Even-dar et al. in [14], sia il boundtight al Price of Anarchy per la funzione Maximum Latency presentato daAwerbuch et al. in [7].

Presenteremo inne i nuovi risultati raggiunti relativamente ai bound alPrice of Anarchy per le altre funzioni obiettivo, quasi tutti rigorosamentetight.

4.1 Esistenza Equlibrio

Forniremo in questa sezione, prima la dimostrazione di esistenza introdottada Even-dar et al. in [14], poi il potenziale ordinale (sezione 2.2) introdottodagli stessi.

4.1.1 Dimostrazione

Consideriamo un vettore ci di m elementi, dove ogni elemento cij rappresentail carico assegnato alla macchina j all'istante i. Deniamo inoltre una fun-zione sort(ci) = li, che ordina il vettore ci in ordine non crescente di carico.Deniamo quindi la relazione d'ordine lessicograco , aermando che:

ci1 ci2 ⇔ ∃k : ∀j < k, li1j = li2j e li1k > li2k .

Consideriamo che dall'istante t all'istante t + 1 un job i si sposti da unamacchina j1 ad una macchina j2: siccome i è gestito da un agente egoista erazionale, tale spostamento ha potuto avere luogo solo se

ctj1 > ct+1j2

> ctj2 . (4.1)

32

CAPITOLO 4. UNRELATED RESTRICTED SCHEDULING 33

D'altro canto, dato che la macchina j1 ha perso del carico

ctj1 > ct+1j1. (4.2)

Dalla diseguaglianza (4.1) risulta evidente che in lt l'elemento ctj1 compaiaprima dell'elemento ctj2 ed inoltre tutti gli elementi che compaiono prima dictj1 in lt sono rimasti invariati in lt+1: in tale vettore, tuttavia, la posizioneche era precedentemente occupata da ctj1 , sarà occupata dal maggiore tra ct+1

j2

e ct+1j1

. Ma, (4.1) e (4.2) dimostrano che, indipendentemente da quale sia ilmaggiore,

lt lt+1.

Quindi ogni migrazione provoca un miglioramento nell'ordine lessicograco.Da qui, essendo il numero di possibili assegnamenti nito (mn), esisterà unvettore l∗, che rappresenterà un minimo globale secondo la relazione d'ordinedenita, tale quindi che non saranno più possibili spostamenti: ossia taleminimo rappresenta un equilibrio Nash.

4.1.2 Potenziale

Sotto il vincolo che wij ∈ ℵ, possiamo associare al problema di scheduling sumacchine non relate (sezione 1.1) la seguente funzione:

P (t) =m∑j=1

4ctj . (4.3)

Consideriamo che dall'istante t all'istante t + 1 un job i si sposti da unamacchina j1 ad una macchina j2. Per la condizione Nash (3.1) cj2+wij2−cj1 <0, da cui

cj2 ≥ 0

cj2 + wij2 ≤ cj1 − 1

cj1 − wij1 ≤ cj1 − 1

(4.4)

Osserviamo la variazione della funzione (4.3): essendo gli unici elementi dellasommatoria a cambiare quelli relativi a j1 e a j2, ci concentriamo solo suquesti due.

Prima dello spostamento la loro somma equivale a 4cj1 +4cj2 ; dopo equiv-arrà a 4cj1−wij1 + 4cj2+wij2 : quindi, utilizzando le disuguaglianze evidenziatein (4.4) la dierenza è

∆P (t) = 4cj1−wij1 + 4cj2+wij2 − 4cj1 − 4cj2 ≤ 4cj1−1 + 4cj1−1 − 4cj1 =

= 2 · 4cj1−1 − 4 · 4cj1−1 = −2 · 4cj1−1 < 0.


Quindi, la migrazione di un job causa il decremento del valore di tale funzione:possiamo quindi concludere che il minimo di tale funzione corrisponde ad unequilibrio Nash, ovvero che (4.3) è un potenziale ordinale per il problemadello scheduling su macchine non relate.

4.2 Maximum Latency

In questa sezione presentiamo il risultato di Awerbuch et al. relativo allafunzione di costo sociale Maximum Latency. In [7] essi hanno dimostrato chein questo modello il Price of Anarchy è Θ(s+ logm

log(1+ log ms

)). La dimostrazione

dell'upper bound riadatta la tecnica introdotta da Czumaj and Vöcking in[13] (sezione 3.2.1).

Upper bound

Consideriamo i link in ordine non crescente di carico. Per ogni k ≥ 1, deni-amo mk essere il minimo intero tale che cmk+1 < k · C(OPT ) (mk = m senon esiste tale intero). Poniamo h = bC(NASH)

C(OPT )c. Il seguente claim mostra

una relazione tra mk e mk+1.

Claim 4.2.1. Per ogni k ≥ 1, mk ≥ k+1smk+1.

Dimostrazione: Indichiamo con Ik+1 l'insieme dei jobs assegnati dalla soluzionein equilibrio ad una macchina dell'insieme 1, . . . ,mk+1 e conW (Ik+1) il pe-so totale dei jobs in Ik+1 nella soluzione in equilibrio. Supponiamo che c'è unjob i ∈ Ik+1 che è assegnato nella soluzione ottima a una macchina t > mk,e indichiamo con q ≤ mk+1 la macchina a cui i era assegnato nella soluzionein equilibrio. Allora,

cq ≥ (k + 1) · C(OPT ) ≥ k · C(OPT ) + wit > ct + wit,

che contraddice la condizione Nash (3.1). Perciò tutti i jobs in Ik+1 sonoassegnati nella soluzione ottima a macchine dell'insieme 1, · · · ,mk. Daqui,

mk ·OPT ≥mk∑i=1

c∗i ≥W (Ik+1)

s≥ (k + 1) ·OPT

s·mk+1,

da cui il claim segue.


Ora, se h ≤ s allora è fatto. Altrimenti, usando il Claim 4.2.1 otteniamoche

m ≥ ms ≥h(h− 1) · · · (s+ 1)

sh−s=

h!

s! · sh−s≥ (

h

e1−s/hs)h.

Da qui segue che h = O( logm

log(1+ log ms

)) e quindi PoA = O(s+ logm

log(1+ log ms

)).

Lower bound

Assumiamo che s ≤ m logm. Partizioniamo le macchine in Ks + 1 gruppi,dove K ≤ Γ−1(m

13s ). Per k = 0, . . . , K − 1 e i = 1, . . . , s, il gruppo numero

ks + i contiene nks+i =√m · (K!)s

(k!)s(k+1)i macchine, e il gruppo 0 contiene

n0 = m−∑ks+1

l=1 nl macchine. Nota che

√m · (K!)s +

ks+1∑l=1

nl ≤√m · (K!)s +

√m ·

K−1∑k=0

s(K!)s

(k!)s≤

≤√m · (K!)s(1 + es) ≤ m,

cosicché n0 ≥√m · (K!)s.

I jobs sono partizionati in Ks gruppi. Per k = 0, . . . , K−1 e i = 1, . . . , s,il (ks+ i)-esimo gruppo contiene (k+ 1) ·nks+i jobs. Ogni job in quel gruppoha peso 1 su una macchina del gruppo ks + i − 1 e peso s − s−i

k+1su una

macchina dal gruppo ks+ i.L'assegnamento ottimo assegna ogni job dall'l-esimo gruppo di jobs a una

distinta macchina nel (l − 1)-esimo gruppo di macchine. Così C(OPT ) = 1.Ora, consideriamo la seguente soluzione S: ogni job dall'l-esimo gruppo dijobs è assegnato ad una diversa macchina nell'l-esimo gruppo di macchine.Chiaramente, il carico su una macchina dell'l-esimo gruppo è esattamente lper l ≥ 1, e in particolare, il massimo carico è Ks.

Inoltre, la soluzione S è in equilibrio Nash: per un job i dall'l-esimogruppo che era assegnato a una macchina j, abbiamo che cj = l, e per ognimacchina k 6= j, ck + wik ≥ (l − 1) + 1 = l. Perciò, il prezzo dell'anarchiaè Ω(Ks). Da qui, possiamo prendere K = Ω(1 + logm

s·log(1+ log ms

)), da cui segue

che PoA = Ω(s+ logm

log(1+ log ms

)).

4.3 Server Latency

In questa sezione mostriamo il primo risultato che abbiamo raggiunto, ovveroche per questa funzione obiettivo PoA = Θ(s).


Upper bound

Dato che wiji ≤ swij∗i

C(NASH) =∑j

cj =∑i

wiji ≤ s ·∑i

wij∗i = s ·∑j

c∗j = s · C(OPT ).

Quindi PoA = C(NASH)C(OPT )

≤ s.

Lower bound

Sia m = n = 2.Il job i1 può essere assegnato:

• Alla macchina j1 con un peso wi1j1 = 1;

• Alla macchina j2 con un peso wi1j2 = s;

Il job i2 può essere assegnato:

• Alla macchina j1 con un peso wi2j1 = s;

• Alla macchina j2 con un peso wi2j2 = 1;

La soluzione ottima assegna:

• Il job i1 alla macchina j1;

• Il job i2 alla macchina j2.

Il costo della soluzione ottima è quindi

C(OPT ) =∑j

c∗j = 2 (4.5)

Consideriamo la seguente soluzione:

• Il job i1 è assegnato alla macchina j2;

• Il job i2 è assegnato alla macchina j1.

Osserviamo che entrambi i jobs subiscono un carico s e spostandosi uni-lateralmente sulla macchina a cui sono associati nell'assegnamento ottimosubirebbero un carico s + 1, quindi non trarrebbero alcun giovamento dall'-eettuare questo spostamento. Quindi questa soluzione è in equilibrio Nash.Il costo di questa soluzione é

C(NASH) =∑j

cj = 2s (4.6)


Da (4.5) e (4.6) risulta che il prezzo dell'anarchia è quindi

PoA =C(NASH)

C(OPT )=

2s

2= s.

4.4 Total Latency

In questa sezione ci concentriamo sulla funzione di costo sociale Total La-tency. Presenteremo due risultati: il primo è un bound tight al Price ofAnarchy nel setting unrelated restricted ; il secondo invece si riferisce al mod-ello di restricted selsh scheduling con macchine identiche e weighted jobs(sezione 1.1). In questo modello un risultato è stato presentato da Hoefere Souza in [16]: tuttavia, noi dimostreremo la presenza di un errore nellaloro dimostrazione e individueremo un nuovo bound tight attraverso le stessetecniche della dimostrazione per il caso unrelated restricted.

4.4.1 Machine load and PoA

Dimostriamo ora che s ≤ PoA = O((max(s, logm

log(1+ log ms

)))). Per la dimostrazione

dell'upper bound fonderemo una variante della tecnica presentata da Czumajand Vöcking in [13] (sezione 3.2.1) e già utilizzata da Awerbuch et al. in [7](sezione 4.2), con la tecnica della Nash Inequality , gia introdotta in questolavoro nella sezione 3.3 e nella sezione 3.4.

Machine load ratio

Deniamo h = bmaxjcjc∗jc.

Se h ≤ s, alloramaxj

cjc∗j

= O(s). (4.7)

Consideriamo, quindi, il caso in cui h > s.Ordiniamo le m macchine in ordine non crescente di carico, ossia

c1 ≥ c2 ≥ · · · ≥ cm.

Indichiamo inoltre con j∗ la macchina più carica nell'assegnamento ottimo.Deniamo ∀ k ≥ 1

Mk = j : cj ≥ kc∗j∗ ⊆ [1, . . . ,m].


Deniamo inoltre

mk =

maxj∈Mk

j = |Mk|, se Mk 6= ∅;1, se Mk = ∅ e k > 1;

m, altrimenti.

È facile vedere che m1 ≥ m2 ≥ . . . .Osserviamo inoltre che

(h+ 1)c∗j∗ > maxj

(cjc∗j

) · c∗j∗ ≥c1c∗1· c∗j∗ ≥

c1c∗1· c∗1.

Quindi non esiste alcun job j tale che cj ≥ (h + 1)c∗j∗ , ovvero Mh+1 = ∅ equindi, essendo h+ 1 > 1, mh+1 = 1. Da qui mh è ≥ 1.Deniamo Ik = i : ji ∈Mk.Supponiamo ∃ i ∈ Ik+1, ossia assegnato nella soluzione in equilibrio Nash aduna macchina q ∈Mk+1 e quindi tale che cq ≥ (k+ 1)c∗j∗ , che nella soluzioneottima sia assegnato ad una macchina t /∈ Mk, cioè tale che ct < kc∗j∗ ,avremmo:

cq ≥ (k + 1)c∗j∗ = kc∗j∗ + c∗j∗ ≥ kc∗j∗ + c∗t ≥ kc∗j∗ + wit > ct + wit

che è assurdo perché viola la condizione Nash (3.1). Quindi possiamo con-cludere che tutti i jobs i ∈ Ik+1 sono assegnati nella soluzione ottima amacchine j ∈Mk o equivalentemente possiamo dire che l'insieme di jobs as-segnati nella soluzione ottima a macchine j ∈ Mk (i : j∗i ∈ Mk) contieneIk+1. Da qui:

mkc∗j∗ ≥

∑j∈Mk

c∗j =∑

i:j∗i ∈Mk

wij∗i ≥∑i∈Ik+1

wij∗i ≥1

s

∑i∈Ik+1

wiji =

=1

s

∑j∈Mk+1

cj ≥1

s· (k + 1)c∗j∗mk+1.

(4.8)

Indi

mk ≥k + 1

s·mk+1. (4.9)

Utilizzando la diseguaglianza (4.9) otteniamo:

m ≥ ms ≥s+ 1

s·ms+1 ≥

(s+ 1)(s+ 2)

s2·ms+2 ≥ · · · ≥

≥ h!

s!sh−s·mh ≥

h!

s!sh−s.

(4.10)


Ricordando che x! ≤ (xe)x, dalla (4.10) concludiamo che

(h

e1−s/hs)h ≤ m

da cui

h = O(logm

log(1 + logms

)). (4.11)

Quindi dalla (4.7) e dalla (4.11) possiamo concludere che

maxj

cjc∗j

= O(max(s,logm

log(1 + logms

))). (4.12)

Upper bound PoA

Sommando la condizione Nash (3.1) per ogni i:∑i

cji ≤∑i

(cj∗i + wij∗i ). (4.13)

Dato che i è assegnato a j∗i nella soluzione ottima, wij∗i ≤ c∗j∗i , quindi ladiseguaglianza (4.13) diventa:∑

i

cji ≤∑i

(cj∗i + c∗j∗i ). (4.14)

Nella prima sommatoria di (4.14) ogni elemento cj compare tante volte quantisono i jobs i tali che ji = j, cioè quanti sono i jobs assegnati a j nellasoluzione in equilibrio, quindi nj volte. Nella seconda sommatoria, invece,ogni elemento (cj+c

∗j) compare tante volte quanti sono i jobs i tali che j∗i = j,

cioè quanti sono i jobs assegnati a j nella soluzione ottima, quindi n∗j volte.Riscriviamo quindi la disequazione (4.14) come:∑

j

njcj ≤∑j

n∗jc∗j +

∑j

n∗jcj ⇒ C(NASH) ≤ C(OPT ) +∑j

n∗jcj. (4.15)

Ponendo cj ≤ O(max(s, logm

log(1+ log ms

))) · c∗j (sezione 4.4.1) in (4.15), otteniamo

che

PoA =C(NASH)

C(OPT )= O(max(s,

logm

log(1 + logms

))).


Lower bound

CASO 1. Se max(s, logm

log(1+ log ms

)) = logm

log(1+ log ms

), allora il machine load ratio é

Ω( logm

log(1+ log ms

)).

Dimostrazione. Sia m = n ≥ 8.Sia s ≥ m logm > 1 il rapporto tra il massimo e il minimo peso dei jobs taleche

logm

log(1 + logms

)= s+ 1⇒ (1 +

logm

s)s+1 = m. (4.16)

Un valore per s tale che (4.16) è vericata esisterà certamente dato che

• D[(1 + logms

)s+1] = (1 + logms

)s+1[log(1 + logms

) + (s+ 1) s3(s−m logm)m(s+logm)

] > 0per s ≥ m logm;

• lims→∞(1 + logms

)s+1 =∞;

• (1 + logmm logm

)(m logm)+1 = (m+1m

)(m logm)+1 ≤ m per m ≥ 8.

Cioè la funzione è crescente e tende verso innito e, per come è stato sceltom, la condizione è vericata per un valore di s ≥ 1, quindi ammissibile.Sia K = s+ 1 = logm

log(1+ log ms

).

Riscriviamo m = n come 2x − x 1K

(supponiamo m sia tale che x e xK

sianoentrambi interi).Dividiamo le macchine in 3 gruppi J1, J2, J3 tali che:

• |J1| = x 1K;

• |J2| = x− x 1K;

• |J3| = x− x 1K.

Dividiamo inoltre i jobs in 2 gruppi I1, I2 tali che:

• |I1| = x;

• |I2| = x− x 1K.

Ogni job i ∈ I1 può essere assegnato:

• Ad una distinta macchina ji ∈ J1

⋃J2 con un peso wiji = 1;

• Ad una macchina ji ∈ J1, per un totale di K jobs assegnabili alla stessamacchina, con un peso wiji = 1.


Ogni job i ∈ I2 può essere assegnato:

• Ad una distinta macchina ji ∈ J2 con un peso wiji = s;

• Ad una distinta macchina ji ∈ J3 con un peso wiji = s.


• Ogni job i ∈ I1 ad una distinta macchina ji ∈ J1

⋃J2, ognuna delle

quali avrà quindi un solo job di peso 1;

• Ogni job i ∈ I2 ad una distinta macchina ji ∈ J3, ognuna delle qualiavrà quindi un solo job di peso s.


• Ogni job i ∈ I1 è assegnato ad una macchina ji ∈ J1, ognuna delle qualiavrà quindi K job di peso 1 ognuno;

• Ogni job i ∈ I2 è assegnato ad una distinta macchina ji ∈ J2, ognunadelle quali avrà quindi un solo job di peso s.

Osserviamo che

• Ogni job i ∈ I1 subisce un carico K = s+ 1 e spostandosi sulla macchi-na in cui è associato nell'assegnamento ottimo subirebbe o un caricoK + 1 o un carico s + 1 = K, quindi non trarrebbe alcun giovamentodall'eettuare questo spostamento;

• Ogni job i ∈ I2 subisce un carico s e spostandosi sulla macchina a cui èassociato nell'assegnamento ottimo subirebbe ancora un carico s, quindinon trarrebbe alcun giovamento dall'eettuare questo spostamento.

Quindi questa soluzione è in equilibrio Nash. Osserviamo che ogni macchinaj ∈ J1 ha carico K nella soluzione in equilibrio Nash e carico 1 nella soluzioneottima quindi:

maxj

cjc∗j

= K =logm

log(1 + logms

),

quindi il bound per il machine load è tight.

CASO 2. Se max(s, logm

log(1+ log ms

)) = s, allora machine load ratio è Ω(s) e

PoA = Ω(s)


Dimostrazione. Consideriamo lo stesso esempio descritto nella sezione 4.3.Entrambi le macchine hanno carico s nella soluzione in equilibrio Nash e

carico 1 nella soluzione ottima, quindi:

maxj

cjc∗j

= s,

che implica che il bound per il machine load è tight.Inoltre, secondo la funzione di costo sociale che stiamo considerando, il costodella soluzione ottima è

C(OPT ) =∑i

c∗j∗i = 2. (4.17)

Invece, il costo della soluzione in equilibrio é

C(NASH) =∑i

cji = 2s. (4.18)

Quindi, dalla (4.17) e dalla (4.18), emerge che il prezzo dell'anarchia è

PoA =C(NASH)

C(OPT )=

2s

2= s.

4.4.2 Identical Setting

Hoefer e Souza in [16] si sono occupati di restricted selsh scheduling sumacchine identiche (sezione 1.1), ossia tale che un job i ha lo stesso caricowi ∈ [0, 1] su qualunque macchina j ∈ Ai.

PoA

In questo setting loro hanno dimostrato che

PoA ≤ n√m

w+

2nm2

w2(4.19)

dove w =∑

iwi. Ma, essendo wi ∈ [0, 1], 0 ≤ w ≤ n. Possiamo osservareinoltre che la funzione in (4.19) è minimizzata scegliendo w = n. Quindi ilbound migliore che potrebbe essere ottenuto è

PoA ≤√m+

2m2

n

e siccome n m

PoA = O(√m).


Dimostrazione

Per dimostrare tale bound Hoefer e Souza pongono le macchine in ordine noncrescente di carico ottenuto nella soluzione in equilibrio Nash, cioè

c1 ≥ c2 ≥ · · · ≥ cm.

Deniscono una partizione dell'insieme delle macchine in gruppi M1, . . . ,Mk

con la proprietà che per ogni gruppo Mt = rt−1 + 1, . . . , rt, il carico dellemacchine crt−crt+1 > wmax (cioè il carico dell'ultima macchina di un grupposi dierenzia rispetto al carico della prima macchina del gruppo successivodi più di wmax) e cl− cl+1 ≤ wmax ∀ l ∈ rt−1 + 1, . . . , rt−1 (cioè all'internodello stesso gruppo il carico di 2 macchine successive si dierenzia di al piùwmax).Indichiamo con It l'insieme di job assegnati a macchine in Mt. Data questasuddivisione è ovvio che ogni job i ∈ It trarrebbe vantaggio nello spostarsiad una macchina di un gruppo con indice maggiore: quindi se la soluzione èin equilibrio è perché questo spostamento non può avvenire, quindi ogni jobpuò essere assegnato solo a macchine presenti nello stesso gruppo o in gruppicon indice minore.Posti mt = |Mt|, Wt =

∑l∈Mt

cl e W ∗t =

∑l∈Mt

c∗l , Hoefer e Souza perraggiungere il bound dimostrano che∑

t

(Wt)2

mt

≤∑t

(W ∗t )2

mt

Per farlo utilizzano il seguente algoritmo per trasformare il prolo dell'equi-librio Nash W1, . . . ,Wk nel prolo ottimo W ∗

1 , . . . ,W∗k :

1. Indichiamo con y1, . . . , yk il prolo corrente dell'algoritmo e inizializzi-amolo al prolo in equilibrio: y1 = W1, . . . , yk = Wk.

2. Deniamo un gruppo t

• sovraccarico, se yt > W ∗t ;

• sottocarico, se yt < W ∗t ;

• saturo, se yt = W ∗t ;

Osserviamo che se esiste un gruppo sovraccarico t, dovrà esistere ancheun gruppo sottocarico con indice l < t.

3. Selezioniamo il gruppo sovraccarico con indice più grande (sia essot) e il gruppo sottocarico con indice più grande (sia esso l < t) edecrementiamo yt e incrementiamo yl di una quantità δ tale che unodei due gruppi si saturi.


4. Ripetiamo dal passo 2 nché tutti i gruppi sono saturi.

Dimostrazione errore

L'algoritmo descritto sopra non sembra corretto: infatti, trovandoci in unsetting restricted, potrebbe non essere sempre possibile fare gli spostamentidesiderati da un gruppo all'altro. Infatti, qui descriviamo un esempio dovetale algoritmo fallisce.Sono presenti 3 macchine che chiameremo A,B e C.Sono inoltre presenti 5 tipi di jobs:

• i jobs di tipo a hanno peso wmin e ne sono s− 2, di cui s− 3 possonoessere assegnati solo alla macchina A e l'altro sia alla macchina A, siaalla macchina B;

• l'unico job di tipo b ha peso 2wmin− 2ε e può essere assegnato solo allamacchina A;

• l'unico job di tipo c ha peso 2wmin − ε e può essere assegnato solo allamacchina B;

• i jobs di tipo d hanno peso 2wmin e ne sono s2− 1, tutti assegnabili solo

alla macchina B;

• i jobs di tipo e hanno peso wmax = swmin e ne sono 4, di cui 3 possonoessere assegnati solo alla macchina C e l'altro sia alla macchina B siaalla macchina C.

Consideriamo quindi la seguente soluzione S1:

• Sulla macchina A sono presenti tutti e s− 2 i jobs di tipo a e il job ditipo b, per un numero totale di s−1 jobs e un carico totale di swmin−2ε;

• Sulla macchina B sono presenti tutti e s2− 1 i jobs di tipo d, il job di

tipo c e un job di tipo e, per un numero totale di s2

+ 1 jobs e un caricototale di 2swmin − ε;

• Sulla macchina C sono presenti i rimanenti 3 jobs di tipo e, per unnumero totale di 3 jobs e un carico totale di 3swmin;

È facile rendersi conto che questa soluzione è in equilibrio Nash, dato che anessuno dei 2 jobs che hanno possibilità di spostarsi conviene farlo. Inoltreosserviamo che il costo di questa soluzione è:

C(S1) ' (2s2 + 10s)wmin.

Consideriamo ora una nuova soluzione S2:


• Sulla macchina A sono presenti s−3 jobs di tipo a e il job di tipo b, perun numero totale di s− 2 jobs e un carico totale di (s− 1)wmin − 2ε;

• Sulla macchina B sono presenti tutti e s2− 1 i jobs di tipo d, il job di

tipo c e un job di tipo a, per un numero totale di s2

+ 1 jobs e un caricototale di (s+ 1)wmin − ε;

• Sulla macchina C sono presenti tutti e 4 i jobs di tipo e, per un numerototale di 4 jobs e un carico totale di 4swmin;

Il costo di questa soluzione è:

C(S2) ' (3

2s2 +

29

2s+ 3)wmin.

È facile vericare inoltre che per s = 10 questa è la soluzione ottima.Provando a raggruppare le macchine come in [16], osserviamo che nellasoluzione in equilibrio Nash il carico di ciascuna macchina dierisce dal cari-co della successiva di più di wmax, quindi ciascuna macchina appartiene adun gruppo dierente:

M1 = C,M2 = B,M3 = A.

Dato questo raggruppamento risulta che

• M1 è sottocarica;

• M2 è sovraccarica;

• M3 è sovraccarica.

Quindi l'algoritmo alla prima iterazione selezionerebbe t = 3 ed l = 1, manon è possibile spostare carico dall'uno all'altro gruppo, dato che non esistonojobs che possono essere spostati dalla macchina A alla macchina C.

Miglioriamo il PoA

Possiamo tuttavia trovare un nuovo bound per il Price of Anarchy nel mod-ello utilizzato da Hoefer e Souza, mediante le tecniche utilizzate nella sezione4.4.1.Una importante dierenza è tuttavia rappresentata dal fatto che s → ∞,quindi attentamente cercheremo di evitare qualsiasi riferimento ad s.In particolare osserviamo che la diseguaglianza (4.8) diverrà

mkc∗j∗ ≥

∑j∈Mk

c∗j =∑

i:j∗i ∈Mk

wi ≥∑i∈Ik+1

wi =∑

j∈Mk+1

cj ≥ (k + 1)c∗j∗mk+1.


Indimk ≥ (k + 1)mk+1 (4.20)

Utilizzando (4.20) otteniamo:

m ≥ m1 ≥ 2 ·m2 ≥ 2 · 3 ·ms+2 ≥ · · · ≥ h! ·mh ≥ h!.

Dalla denizione di Gamma function, h! ≤ m implica

h ≤ Γ−1(m+ 1). (4.21)

Dalla (4.21), utilizzando una nota approssimazione della inverse Gammafunction, otteniamo che

h = O(log(m+ 1)

log log(m+ 1)). (4.22)

Quindi dall'uguaglianza (4.22) concludiamo che

maxj

cjc∗j

= O(logm

log logm). (4.23)

Ora utilizzando il risultato (4.23) in (4.15), otteniamo che

PoA =C(NASH)

C(OPT )= O(

logm

log logm),

asintoticamente migliore rispetto al miglior bound che dai risultati in [16]poteva essere ottenuto, come evidenziato nella sezione 4.4.2.

Lower Bound

Sia k = logmlog logm

e n = m(k + 2km

) (supponiamo, senza perdità di generalità,

che k + 2km

sia un intero).I job sono di 2 tipi:

• i job di tipo a hanno peso 0, ne sono m(k + 2km− 1);

• i job di tipo b hanno peso 1, ne sono m.

Deniamo le seguenti restrizioni:

• i job di tipo a possono essere assegnati ad una qualsiasi delle m mac-chine;


• ogni job b1, . . . , bm−1 è assegnabile ad una sola e distinta macchina in1, . . . ,m− 1;

• il job bm è assegnabile sia alla macchina 1 che alla macchina m.


• i job b1, . . . , bm−1 all'unica macchina a cui sono associabili;

• il job bm alla macchina 1;

• i job di tipo a alla macchina m.

Quindi:

• la macchina 1 ha 2 job per un carico totale di 2;

• le macchine in 2, . . . ,m− 1 hanno un unico job per un carico totaledi 1;

• la macchina m ha m(k + 2km− 1) job per un carico totale di 0.

Il costo della soluzione ottima è quindi

C(OPT ) =∑j

n∗jc∗j = 2 · 2 + (m− 2) · 1 · 1 + 0 = m+ 2 (4.24)


• i job b1, . . . , bm−1 all'unica macchina a cui sono associabili;

• il job bm alla macchina m;

• k + 2km− 1 job di tipo a a ciascuna macchina.

Quindi tutte le macchine hanno k+ 2km

job per un carico totale di 1. Osservi-amo inoltre che ogni job subisce un carico 1 e spostandosi unilateralmentesu una qualsiasi altra macchina subirebbero un carico 2, quindi non trar-rebbe alcun giovamento dall'eettuare questo spostamento. Quindi questasoluzione è in equilibrio Nash. Il costo di questa soluzione é

C(NASH) =∑j

cj = m · (k +2k

m) · 1 = mk + 2k = k(m+ 2) (4.25)

Da (4.24) e (4.25) risulta che il prezzo dell'anarchia è quindi

PoA =C(NASH)

C(OPT )=k(m+ 2)

m+ 2= k.

Quindi PoA = Ω( logmlog logm

).


4.5 Quadratic latency

In questa sezione analizziamo un altro nostro risultato relativo alla funzioneobiettivo della Total Latency : infatti mostreremo che PoA = Θ(s2).

L'upper bound è una estensione del bound presentato nella sezione 3.4 alcaso in cui le macchine siano non relate e adotta le stesse tecniche di quelladimostrazione: Nash Inequality e approssimazione mediante diseguaglianzadi Cauchy-Schwartz.

Per il lower bound ancora una volta il semplice esempio descritto nellasezione 4.3 ci porta al risultato desiderato.

Upper bound

Sommando la condizione Nash (3.1) per ogni i e moltiplicando ogni elementoper wiji abbiamo: ∑

i

wijicji ≤∑i

wiji(cj∗i + wij∗i ). (4.26)

Dato che in (4.26) i è assegnato a j∗i nella soluzione ottima, wij∗i ≤ c∗j∗i , quindi:∑i

wijicji ≤∑i

wiji(cj∗i + c∗j∗i ). (4.27)

Siccome wiji ≤ swij∗i , la diseguaglianza (4.27) diventa:∑i

wijicji ≤ s ·∑i

wij∗i (cj∗i + c∗j∗i ). (4.28)

Nella prima sommatoria di (4.28) ogni elemento cj risulta moltiplicato per∑i:ji=j

wiji = cj. Nella seconda sommatoria, invece, ogni elemento (cj + c∗j)è moltiplicato per

∑i:j∗i =j wij∗i = c∗j . Da cui:

C(NASH) =∑j

(cj)2 ≤ s ·

∑j

(c∗j)2 + s ·

∑j

c∗jcj =

= s · C(OPT ) + s ·∑j

c∗jcj.(4.29)

Per la diseguaglianza di Cauchy-Schwartz :∑j

cjc∗j ≤

√∑j

(cj)2 ·√∑

j

(c∗j)2 =

√C(NASH) ·

√C(OPT ). (4.30)


Da (4.29) e (4.30), dividendo tutto per C(OPT ) e semplicando, avremo:

PoA =C(NASH)

C(OPT )≤ s+ s

√PoA. (4.31)

Risolvendo la disequazione (4.31) otteniamo l'upper bound:

PoA ≤ 1

2(s2 + 2s+

√s4 + 4s3) = O(s2).

Lower bound

Consideriamo lo stesso esempio descritto nella sezione 4.3.Secondo la funzione di costo sociale che stiamo considerando, il costo della

soluzione ottima èC(OPT ) =

∑j

(c∗j)2 = 2. (4.32)

Invece, il costo della soluzione in equilibrio é

C(NASH) =∑j

(cj)2 = 2s2. (4.33)

Quindi, dalla (4.32) e dalla (4.33), emerge che il prezzo dell'anarchia è

PoA =C(NASH)

C(OPT )=

2s2

2= s2.

Conclusioni

I risultati raggiunti in questo lavoro sono quasi tutti tight, tranne nel ca-so della Total Latency : per questa funzione obiettivo è impossibile trovareuna istanza del problema per cui PoA ≥ logm

log(1+ log ms

)> s. Infatti, una tale

istanza comporterebbe che per ogni macchina j, cjc∗j> s, e quindi, anché

tale rapporto possa vericarsi, nj > n∗j , ovvero∑

j nj >∑

j n∗j = n, che è

assurdo.A questo punto, la nostra assunzione è che per la Total Latency PoA =

Θ(s), ma rimane un problema aperto riuscire a trovare un upper bound cherigorosamente conferma tale assunzione.

In ogni caso, i risultati raggiunti in questo lavoro mostrano per quasi tuttele funzioni di costo sociale che il Price of Anarchy ha una stretta dipenden-za da s: tale risultato è abbastanza signicativo, perché pone il progettistadi sistemi distribuiti, gestiti da agenti selsh, davanti all'importante com-pito di limitare la varietà di scelte che tali agenti possono fare. A tal ne,potrebbe essere interessante lo studio e la progettazione di meccanismi capacidi garantire tali obiettivi, qualora possa essere dicile al progettista porretali limiti sicamente.

Come abbiamo indicato nella sezione 2.3, il Price of Anarchy è una misuraimportante dell'ecienza dei giochi, ma può portare ad una cattiva valu-tazione data la non unicità degli equilibri Nash di un gioco: sarebbe interes-sante analizzare quindi anche il Price of Stability sia nel nostro che in altrisetting.

Inoltre il solution concept considerato non prevede la presenza di collab-orazione tra agenti: di enorme utilità sarebbe investigare quanto tali collabo-razioni potrebbero inuire negativamente sul raggiungimento della soluzioneottima.

Ancora, nel nostro modello abbiamo implicitamente supposto che un jobpotesse semplicemente migrare da una macchina ad un'altra: tuttavia inmolti esempi reali eettuare tali migrazioni potrebbe incorrere in costi perl'agente. Interessante ed utile quindi sarebbe valutare la perdita di ecienzain tale setting.

50

51

Inne, i risultati raggiunti prevedono un insieme di agenti statici. Inpratica, molto spesso, accade che alcuni agenti lasciano il sistema e nuovise ne aggiungono, costringendo comunque a raggiungere una soluzione inequilibrio Nash. Studiare come il sistema si comporta in presenza di taledinamicità avrebbe un enorme interesse pratico.

Ringraziamenti

Questa è forse la parte più dicile di tutta la tesi. Comunque ci proverò.Prima di tutto grazie alla mia famiglia, alla mia mamma e al mio papà.

Vorrei ringraziarli per il loro aetto, per l'immensa ducia che hanno sempreriposto in me, per il supporto che mi hanno fornito sempre in questi 23 anni.Vorrei ringraziarli per i loro insegnamenti, per le lezioni di vita, per la guidache hanno rappresentato sempre nel mio cammino. Più proseguo in questalista, però, più mi rendo conto che i motivi per cui voglio ringraziarli sonotanti, troppi e quasi sempre troppo dicili da esprimere con delle parole...Grazie mamma, grazie papà.

Un sincero ringraziamento va ai ragazzi che hanno frequentato e frequen-tano l'SCNLab, dove questa tesi è nata e cresciuta, per i consigli, per isuggerimenti, per le correzioni, per avermi ascoltato quando avevo bisognodi qualcuno con cui condividere le mie idee o anche per la complicità quandoc'era bisogno di svagarsi, di rilassarsi, di divertirsi: a proposito di svaghiun ringraziamento particolare va a Luca e alle avvincenti partite a BlobbyVolley.

Oltre a ringraziare quelli che mi sono stati a anco durante la tesi, voglioringraziare tutti coloro con cui ho condiviso questi anni di università. Eprima di tutto devo cominciare dal CrazyUnisa... Cosa è il CrazyUnisa?CrazyUnisa è una confraternita, congrega, crew, gruppo, banda di scalmanatie chi più ne ha più ne metta, i cui membri frequentano o hanno frequentato(almeno per un qualche periodo) la facoltà di Informatica. Ma per spiegaremeglio quanto è importante questo gruppo, userò un commento ad un vecchiopost apparso sul sito di uno dei membri:

La forza di questo gruppo sta nel fatto che ognuno dei mem-bri lo sente come il suo gruppo, e questo dà la forza ad ognunodi continuare a vivere intensamente questa cosa sua, anche sequalcuno è alla specialistica e qualcun'altro al primo anno, anchese c'è qualche innato leader che si condivide più o meno, an-che quando ci si diverte perché siamo dei cabarettisti più o menobravi, anche se vogliamo pensare a questo gruppo come ad un ato-

52

53

mo attorno a cui giriamo come particelle piuttosto che come unarete dentro il quale ci troviamo a raccogliere una parte di noi, an-che se qualcuno frequenta poco l'università e gli altri membri delgruppo, anche se si frequenta molto l'università e gli altri mem-bri del gruppo, anche se qualcuno ha una idea geniale che glialtri seguono, anche se le cose possono sembrare troppo facili otroppo dicili, anche se qualcuno insegna cose nuove agli altrie qualcun'altro apprende, anche quando si litiga, si discute, ci siincazza, anche quando si hanno idee diverse e si passano nottateintere a parlarne e a sbattersi le proprie teste dure le une con-tro le altre, anche quando si manda a quel paese lo studio e sibighellona, anche quando si manda a quel paese il bighellonare esi studia, anche quando si parla, anche quando si ascolta, anchequando ti senti bene, realizzato, senti di star facendo qualcosa dibuono, di star facendo parte di qualcosa di buono, oppure ti sentimale, ti senti come se ti manca qualcosa, ti senti in un periodo incui sembra che non ti va bene nulla, anche se si è vecchi membri,oppure si è nuovi nel gruppo.

Ma se il CrazyUnisa è stato importante in questi anni, altrettanto lo sonostati Rino, Tiziano e Angelo: sono tra coloro che conosco da più tempo el'amicizia che è nata e cresciuta tra le mura universitarie, continua indissol-ubile, se non raorzata, nonostante le strade dierenti che abbiamo scelto dipercorrere.

Un grazie particolare è dovuto alla grande famiglia della Magnica Gentedo' Sud: ai vecchi, guide indissolubili e maestri di questo grande gruppo,e ai giovani, prima di tutto amici, e spesso anche di più.

Per ultima, ma assolutamente non meno importante, ringrazio la miasorellina, il sorriso che è capace di donarmi, l'aetto enorme che solo lei saorire, per come conosce come sono fatto meglio di chiunque altro.

Bibliograa

[1] Ieee 802.11s: Wireless lan medium access control (mac) and physicallayer (phy) specications: Simple ecient extensible mesh (see-mesh)proposal.

[2] Ieee 802.11: Wireless lan medium access control (mac) and physicallayer (phy) specications, 1999.

[3] William A. Arbaugh, Arunesh Mishra, and Minho Shin. An empiri-cal analysis of the ieee 802.11 mac layer hando process. In in ACMSIGCOMM Computer Communication Review 33, pages 93102, 2003.

[4] George Athanasiou, Thanasis Korakis, Ozgur Ercetin, and Ros Tassiu-las. Dynamic cross-layer association in 802.11-based mesh networks. Inin IEEE INFOCOM, pages 20902098, 2007.

[5] Robert John Aumann. Acceptable points in general cooperative n-person games. in Contributions to the Theory of Games IV, Annalsof Mathematics Study 40, pages 287324, 1959.

[6] Baruch Awerbuch, Yossi Azar, and Amir Epstein. The price of routingunsplittable ow. In STOC '05: Proceedings of the thirty-seventh annualACM symposium on Theory of computing, pages 5766, 2005.

[7] Baruch Awerbuch, Yossi Azar, Yossi Richter, and Dekel Tsur. Tradeosin worst-case equilibria. In In WAOA, pages 4152, 2003.

[8] Yigal Bejerano and Randeep Bhatia. Mi: A framework for fairnessand qos assurance in current ieee 802.11 networks with multiple accesspoints. In in IEEE INFOCOM, pages 93102, 2004.

[9] Yigal Bejerano, Seung-Jae Han, and Erran L. Li. Fairness and loadbalancing in wireless lans using association control. In in MOBICOM,pages 315329, 2004.

54

BIBLIOGRAFIA 55

[10] Petra Berenbrink, Leslie Ann Goldberg, Paul W. Goldberg, and RussellMartin. Utilitarian resource assignment. Journal of Discrete Algorithms,4, pages 567587, 2006.

[11] Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Panagi-otis Kanellopoulos, and Luca Moscardelli. Tight bounds for selsh andgreedy load balancing. In in ICALP (1), pages 311322, 2006.

[12] Artur Czumaj, Piotr Krysta, and Berthold Vocking. Selsh trac allo-cation for server farms. In in Proc. 34th Annual Symposium on Theoryof Computing (STOC), pages 287296, 2002.

[13] Artur Czumaj and Berthold Vöcking. Tight bounds for worst-caseequilibria. ACM Trans. Algorithms, 3, page 4, 2007.

[14] Eyal Even-dar, Alex Kesselman, and Yishay Mansour. Convergence timeto nash equilibria. In In ICALP, pages 502513, 2003.

[15] Martin Hoefer and Alexander Souza. Tradeos and average-caseequilibria in selsh routing. In in ESA, pages 6374, 2007.

[16] Martin Hoefer and Alexander Souza. The inuence of link restrictionson (random) selsh routing. In in Proceedings of the First Symposiumon Algorithmic Game Theory (SAGT 2008), pages 2232, 2008.

[17] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria.In in Proceedings of the 16th Annual Symposium on Theoretical Aspectsof Computer Science, pages 404413, 1999.

[18] Don Monderer and Lloyd Stowell Shapley. Potential games. Games andEconomic Behavior, 14, pages 124143, 1996.

[19] John Nash. Non-cooperative games. The Annals of Mathematics 54(2),pages 286295, 1951.

[20] John Von Neumann and Oscar Morgenstern. Theory of Games andEconomic Behaviour. Princeton University Press, 1944.

[21] Arthur Cecil Pigou. The Economics of Welfare. Macmillan, 1920.

[22] Robert W. Rosenthal. A class of games possessing pure-strategy nashequilibria. International Journal of Game Theory, 2, pages 6567, 1973.

[23] Robert W. Rosenthal. The network equilibrium problem in integers.Networks, 3, pages 5359, 1973.

BIBLIOGRAFIA 56

[24] Andreas S. Schulz and Nicolás Stier Moses. On the performance ofuser equilibria in trac networks. In in SODA '03: Proceedings of thefourteenth annual ACM-SIAM symposium on Discrete algorithms, pages8687, 2003.

[25] Subhash Suri, Csaba D. Tóth, and Yunhong Zhou. Selsh load balancingand atomic congestion games. In in SPAA, pages 188195, 2004.

[26] Subhash Suri, Csaba D. Tóth, and Yunhong Zhou. Uncoordinated loadbalancing and congestion games in p2p systems. In In IPTPS, pages123130, 2004.

[27] John Glen Wardrop. Some theoretical aspects of road trac research.In in Proc. Institute of Civil Engineers, Pt. II, pages 325378, 1952.

Indice analitico

w-potential, 17(general) congestion game, 15

airtime metric, 11algorithm game theory, 3associazione in 802.11, 11atomic selsh routing, 16

condizione Nash, 22Congestion Games, 15Correlated Equilibrium, 15

dominant strategy solution, 13

exact potential, 17

generalized ordinal potential, 17gioco, 13

KP-model, 4, 10

Maximum Latency, 4, 22, 23, 34meccanismi, 50mechanism design, 3Mixed Strategy Nash Equilibria, 14

Nash Equilibrium, 14, 18Nash Inequality, 28, 30, 37, 48network congestion game, 16non-atomic selsh routing, 16

ordinal potential, 17, 34

potential function, 17, 33potential game, 17Price of Anarchy, 4, 18, 23, 25, 28, 30,

34, 35, 37, 45, 48

Price of Stability, 18, 50

Quadratic Latency, 5, 22, 30, 48

restricted selsh scheduling, 28, 30,32

RM-AODV, 11routing, 9routing game, 16RSSRI, 11

scheduling, 7selsh client assignment, 10selsh routing, 9, 30selsh scheduling, 8, 20Server Latency, 5, 22, 35single-choice congestion game, 16sistemi peer-to-peer, 10solution concepts, 13strategie miste, 14strategie pure, 14

Total Latency, 5, 22, 25, 28, 37, 50

unrestricted selsh scheduling, 22

web server farm, 10weighted potential, 17wireless mesh network, 11

57

Il problema del job scheduling in presenza di agenti egoistiferraioli/files/tesi.pdf · l'ambiente...

Documents

Transcript of Il problema del job scheduling in presenza di agenti egoistiferraioli/files/tesi.pdf · l'ambiente...