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 d i s e q u a z i o n e v a r i a z io n a l e 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 complementarità

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 /= D

componente 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 Y

I ◦

Definizione: problema di complementarità 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 0

n

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 complementarità 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 e

n 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

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 ☑ gita

G- (

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