Teoria 1 esonero di Games and equilibria

Capitolo 1: disequazioni variazionali e problemi di complementarietà

Definizione: disequazione variazionale

D at o u n i n s iem e K E R " n on v u o t o , c h iu s o e co n v es so e u n a f u n z io n e co n tin u a F : R " → IR "a ll o ra u n a disequazione variazionale V I 1K , F ) è il p r o b lem a d i t r ovar e u n vettore ✗ E K :(y - ✗ I" F A I ≥ 0 ∀ y E K

Ogni punto x che soddisfa la definizione è detto soluzione della disequazione variazionale e l'insieme di tutte le soluzioni è SOL (K,F)

Interpretazione geometrica

Un punto x appartenente a K è una soluzione di VI(K,F) se e solo se F(x) forma un angolo non ottuso (minore uguale a 90°) con ogni vettore dalla forma y-x.

Si può associare ad ogni punto x' appartenente a K il cono normale N(x';K):

N / ✗ 'i K / = { d e R " : d ' 4 - ✗ '1 2 0 H Y E K } tutti i vettori che stanno fuori da K e formano un angolo inferiore a 90° con le direzioni interne

Un vettore in questo cono viene detto vettore normale a K in x'

Quindi la disequazione variazionale dice che: un vettore xè una soluzione di VI (K,x) se e solo se -F (x) è un vettore normale a K in x, o anche se e solo se:

0 appartiene a F (x)+N(x;K)

Il caso in cui K=R" è quello più semplice per introdurre le disequazioni variazionali infatti, in questo caso, un vettore x appartiene a SOL(K,F) se e solo se x è uno zero della funzione F => SOL(K,F)=F-¹(0) per cui qualunque sia K se F(x)=0 allora x appartiene all'insieme delle soluzioni.

Se x è una soluzione di VI(K,F) e x è un punto interno a K allora F(x)=0

Definizione: problema di complementarietà

D a t o u n con o K E R " e u n a f u n z io n e F : K → R " , il C P 1K , F ) c o n s is t e n e l t rovar e u n v ett or e ✗ E R " c h e s o d d is f i: K ∃ ✗ ⟂ F IX ) E K " con K ' il con o du ale d i k , o vve r o

K E { d e r " : i d r o ☑ V E K } ⇒ in s i e m e d e i v e t t o r i ch e f o r m a u n a n g o lo n o n ott u s o co n t u tt i i v ett o r i d i k .

P er cu i l e c o n d i z io n i s o n o : ✗ E K , F I N E K ' , ✗ 'F A I = O

✗ è a m m is si b i le se v a l e c iò

✗ è s tr ett a m en t e a m m is s i b i l e c o n F IX E i n t E e x e k

I c p h a u n v ettor e s t r et t o a n n i . , p e r f c o n t in u a e i n t k # ∅ , s e e s olo s e ✗ 'e in t k e F A ' / E i n t r i

L a r e g i o n e a m m i s s ibi l e è d e t t a F E A IK .F I

Il c p l k .F I p u ò e ss e r e r i s c r itt o c o m e : ✗ E K , F I X I E K "e ☒ F A I: O

Esprimendo la condizione di complementarità ✗ ' F IX /= Dcomponente per componente si ottiene la formulazione equivalente: ☒ > O F A R O X iF I X i ) : O t i - 1 . . . in

Connessione tra VI(K,F) e CP(K,F): un vettore x è una soluzione di VI(K,F) se e solo se x è una soluzione del CP(K,F)( Y - X I' F I A : O H Y E K K A X I F IX IE V YI ◦

Definizione: problema di complementarietà non lineare

D a t a u n a f u n z io n e F : R " + → R " , l ' N C P ( F ) C o n s is t e n el t r o v a r e u n v e t t o re ✗ E IR " : 0 : X 1 F A ) 2 0n

Questo perché quando K è l'ortante non negativo, quindi quando K=R+ si ha che il cono duale di K è di nuovo K stesso

Definizione: problema di complementarietà mista

Si ottiene quando si considera un problema di CP(K,F) con il cono K dato da Ru xR" ' con n1+n2=n, partizionando i vettori x e F(x) distinguendo le prime n1 componenti dalle ultime n2:

S ia n o G e H d u e f u n z io n i d a 12 " ✗ R " ⅔ a 12 " e 12 " r i s p e t t iv a m e n t e : i l M I C P ( G , H , c o n s is t en el t r o v a r e u n a c o p p ia d i v ett or i in N e a r " e r " r i s pe tti v a m e n t e e t ali ch e :

G I U , V I = D c o n µ l ib e r a

O E V ⟂ H IM , V I 2 0

Problema di ottimizzazione vincolata

Considero il seguente problema di ottimizzazione vincolata:

la funzione obiettivo è di classe C¹ su un insieme aperto contenente min 01h s.t. XEK l'insieme convesso K

Per il principio del minimo abbiamo che se x è un minimo locale di questo problema allora:

VOIXI (y-✗ 120 ∀ YEK ⇒ è la soluzione di IK.TO)

Quindi il principio del minimo dice che x è soluzione se e solo se risolve la disequazione variazionale VI(TO,K)

Viene definito un punto stazionario primale del problema ogni soluzione della VIIK.TO)

Se la funzione è convessa allora ogni punto stazionario è un punto di minimo globale

Riprendo il problema di 1.2.1e suppongo che K sia definito: KELXEIR" : 41×1=0, g/✗ 120} con 4: R"→ Re e g: R" → 12" funzioni continuamente differenziabili e hj lineari e gi convesse.

Prendo x punto di minimo locale del problema allora si ha il seguente sistema di KKT:

0-TO + e È µ, Thy CAFÈ litigi (X)= h (x) e coincide con un particolare problema di complementarietà mista infatti:

O ≤ 1 ⟂ g/×) ≤ 0 m GIU,VI:O in libera

☑ O#µ µ, thy AI + E ti ☑ gitaG- (4:(I ✓ =L OEVLHIM.NO) Hi-ga,hai

Ricordiamo che ogni punto di minimo è anche un punto di KKT solo nei problemi di ottimizzazione convessa, quindi tutti i punti stazionari sono buoni

Problemi di equilibrio di Nash

In un gioco non cooperativo si assume che ci siano N giocatori, ognuno dei quali ha una certa funzione di costo e insieme ammissibile, dove questo e l'insieme di tutte le strategie possibili del giocatore i siano indipendenti dalle strategie adottate dagli altri giocatori.

La funzione di costo del giocatore i O i k i invece dipende dalle strategie adottate dagli altri

Indichiamo le variabili che descrivono l'insieme delle strategie adottate dai vari giocatori con x che e composto dai sottovettori:

"∈ 12 " " p er i - 1 ,.. . N → strategie del giocatore i

Il problema del giocatore i è quello di trovare per ogni prefissata ma arbitraria scelta " ( x ' : F i)× ' che risolva il problema:

degli altri giocatori u. na strategia

m in O il y ", I i)

s .t o y ' E k i

la minimizzazione è rispetto a yi che rappresentano le possibili scelte dell'iesimo giocatore, mentre le variabili xi sono quelle di tutti gli altri giocatori e sono considerate fisse nel momento in cui si risolve il problema.

Indico con s i l E ' ) l'insieme delle soluzioni ottime per un fissato xi. ✗ " E S C E " )

Un equilibrio di Nash è una tupla di strategie ✗ = / x i : i - 1 , . . . . N ) tali che per ogni i risulti

Un equilibrio di Nash è un insieme di strategie, una per ogni giocatore, tali che nessun giocatore possa diminuire la sua funzione obiettivo deviando unilateralmente dalla stategia data

Equilibri di Nash, sotto alcune ipotesi, sono anche le soluzioni di VI opportune: dati i Ki, ciascuno è un sotto insieme chiuso e convesso di R' ,

• Suppongo che per ogni fissata tupla le funzioni di costo siano convesse e continuamente differenziabili in yi, allora la tupla x è un equilibrio di Nash se solo se ✗ E S O L 1k , F ) d ov e K Σ K i e F I X ) E V I 0 : A ) 2 0 K y E K= 1= 1

Problemi di equilibrio del traffico

Ha come scopo quello di predire i flussi di traffico di una rete congestionata.

Viene data una rete descritta da un insieme di nodi N e archi A, gli utenti della rete competono in modo non cooperativo nel tentativo di minimizzare i costi di viaggio. L'insieme di nodi viene suddiviso in due sottoinsiemi:

• Nodi di origine di flusso del traffico: O
• Nodi che rappresentano le destinazioni: D

L'insieme di tutte le coppie origine destinazione è un sottoinsieme W di OxD

Per ogni coppia w di W sia Pw l'insieme di tutti i percorsi che connettono la coppia di OD w e sia P l'unione di tutti gli insiemi Pw per ogni w di W Rappresento con i colori i possibili percorsi eseguibili per ciascuna coppia origine destinazione effettivamente raggiungibili:

P12

P11

P22

P23

Sia hp il flusso sul percorso p appartenente a P e sia Cp(h) il costo su questo percorso; per ogni w di W si suppone sia data una funzione dw(u) che rappresenta la domanda di viaggio di w:

• Modello viene chiamato con domande elastica se u è il vettore incognito del costo di viaggio minimo tra tutte le coppie origine destinazione.
• Modello viene chiamato con domanda fissa se la domanda dw(u) sia una costante indipendente da u

Il principio di eq