Esami games and equilibria

1^o ESAME

1. Dare la definizione di punto fisso e di contrazione. Dimostrare quindi il seguente teorema Sia G : Ω ⊆ ℝⁿ → Ω una contrazione con costante η ∈ [0, 1), dove Ω ≠ ∅ è un insieme chiuso. Le seguenti due affermazioni sono vere.
   • (a) La G ha uno e un solo punto fisso x* in Ω.
   • (b) per qualunque punto iniziale x₀ in Ω, la successione definita da x_k+1 = G(x_k) genera una successione {x_k} che converge a x*.

Sia dato un VI (K, F), dove

F =

• (2x₁² + x₁x₂x₃ + x₃³)
• (x₁ + 2x₂ - x₃)
• (x₂¹ + x₃² - x₃)

e

K = {x ∈ ℝ³ : 2x₁ + x₂ - x₃ ≤ 4, 4x₁² - 2x₂ + x₃² ≤ 5, x ≤ 0}

Scrivere le corrispondenti condizioni di KKT

Dire, giustificando la risposta, se la funzione

F =

• (3x₁ + 4x₂ + 7)
• (2x₁ + 2x₂ - 2)

è fortemente monotona.

4. Sia dato un gioco con 3 giocatori in cui le coalizioni hanno i seguenti valori

Determinare il valore di Shapley del gioco

3)

F = (3x₁ + 4x₂ + 7 2x₁ + 2x₂ - 2)

è FORTEMENTE MONOTONA ?

∂F = (3 4 2 2)

A = ∂F_ini = 1/2 [ 3 4 ) + ( 3 2 ] [ 2 2 ) ( 4 2 ]

= 1/2 ( 6 6 ) = ( 3 3 ) SIMMETRICA ( 6 4 ) ( 3 2 )

det A = 6 - 9 < 0 ⟹ NON è MONOTONA ⟹ NON è FORTEMENTE MONOTONA

4)

• COALIZIONE | GUADAGNO
• 1 | 20
• 2 | 30
• 3 | 0
• 1, 2 | 80
• 1, 3 | 55
• 2, 3 | 60
• 1, 2, 3 | 100

Determinare il valore di Shapley.

|T| = (|T|-1)! (n-|T|)! |T|!

|T| = 1

1/3

S₁(V) = 1/3 [V(1) - V(∅)] +

1/6 [V(1, 2) - V(2)] +

1/3 [V(1, 2, 3) - V(2, 3)]

= 1/3 20 + 1/6 55 + 1/3 40 = 85/3

ESAME 2

1. FISHER - BURKEISTER
2. ORTANTE NON NEGATIVO

> Per x ≥ 0 è MONOTONA e STRETTAMENTE MONOTONA

> Verifico f. MONOTONA a > 0

(3-a)(4-a)(2x+1-a) - ¹/₄(2x+1-a) ≥ 0

(2x+1-a)(12-7a+a²) - ¹/₄(2x+1-a) ≥ 0

(2x+1-a)(12-7a+a² - ¹/₄) ≥ 0

(2x+1-a)(⁴⁷/₄-7a+a²) ≥ 0

2x+1-a ≥ 0

a ζ 2x+1

4t - 28a + 4a² ≥ 0

Dipende da a, NON POSSO DIRE NULLA

1.

Dare la definizione di

• Insieme convesso;
• Insieme chiuso;
• Proiezione di un punto su un insieme convesso e chiuso.

Dimostrare quindi che

• La proiezione di un punto su un insieme convesso e chiuso è ben definita e unica; x̄ ∈ K è la proiezione di x su K se e solo se risulta (x̄ - x)^T(y - x̄) ≥ 0,     ∀y ∈ K;
• Data una VI (K, F), x̄ ∈ K è una soluzione se e solo se x̄ = Π_K(x̄ - F(x̄)).

Mostrare quindi, usando i risultati dimostrati, che x̄ è una soluzione di una VI(K,F) se e solo se x̄ = Π_K(x - F(x)).

Sia data la funzione

F =

• 2x₁ - x₂ - x₃ - 1
• x₁ + x₂ + x₃
• -x₂ + 4x₃ - 4

e il punto

x̄ =

• 1
• 0
• 1

Determinare se x̄ è una soluzione di NCP (F).

Determinare se la funzione F nell'esercizio precedente è monotona, strettamente monotona, fortemente monotona su ℝⁿ₊.

4.

Sia dati due giochi con 3 giocatori in cui le coalizioni hanno i seguenti valori

Determinare se questi giochi sono bilanciati o meno.

0 ≤ 10h₁ + 50 + h₁ - u

0 ≤ 50 + h₂ + 10h₂ - u

u + h₁ + h₂ - 6 = 0

u ≥ 0

h₁ ≥ 0

h₂ ≥ 0

COMPLEMENTARITÀ

F = [10h₁ + 50 + h₁ - u

50 + h₂ + 10h₂ - u

h₁ + h₂ - 6]

CALCOLIAMO L'EQUILIBRIO

h₁ = 6 - h₂

60 - 10h₂ + 50 + 6 - h₂ - u = 0

50 + h₂ + 10h₂ - u = 0

h₁ = 6 - h₂ = 0

h₁ + h₂ = 6

h₁ = 3

h₂ = 3

h₁ = h₂ = 3 è intuitivo perché le funzioni di costo su h₁ e h₂ sono simmetriche.

Deve risultare quindi che:

Abbiamo quindi:

• (0) - (₁/^√2) λ₁ + (^2√2/₂) λ₂ = 0

• (0) = 1 [^-2√2] [_√2] [⁰] λ => (_-2)

• 0 = λ₁ - 2√2 λ₂
• 1 = √2 λ₁ - 2 λ₂

λ₁ = 2√2 λ₂

λ₂ = -1 + ^√2/₂ λ ⇒λ₂ = ^{√2 - 2√2 λ₂ - 1}/₂

λ₂ = ^{4 λ₂ - 1}/₂

λ₂ = 2 λ₂ - ¹/₂

^{0 ≤ λ} = [^√2 , ¹/₂] ^T

^{λ₂ = 1/₂}

^{λ₁ = √2}

SODDISFATTE

3) Calcolo la proiezione di x su h = { x | x₁² + x₂² ≤ r² }.

Verifichiamo che risulta:

Π_h(x) = r · X / ||X||

L'unico caso di interesse è quello in cui x ∉ haltrimenti Π_h(x) = x.

Risolviamo min (1/2) ||y - x||²

y₁² + y₂² ≤ r²

Siccome il vincolo soddisfa la CONDIZIONE DI SLATER(nel punto (0,0), abbiamo 0 < r² e la S.O. è fortementeconnessa -) un punto è soluzione di questo problema sono verificate le KKT.

∇f(y) = y - x∇g(y) = 2y vincolo attivo

∇L(Π_h(x)) = r · X / ||X|| - X + 2r X / ||X|| λ = 0

y = r · X / ||X||

0 ≤ λy₁² + y₂² ≤ r²

λ(y₁² + y₂² - r²) = 0

Basta verificare che il λ per cui ∇L(Π_h(x)) = 0 siapositivo.

λ = (1/2) ||X||(1 - r / ||X||)₂

poiché x ∉ h => ||X|| > r