Теория на игрите

Тука сложи заглавие

Задача 7

Дадена е игра, определена от матрицата:

(1)

\begin{align} A = \begin{pmatrix} 4 & -3 \\ 2 & 1 \\ -1 & 3 \\ 0 & -1 \\ -3 & 0 \\ \end{pmatrix} \end{align}

Да се намери цената на играта и оптималните стратегии на 2^мата играчи.

покажи

(2)

\begin{eqnarray} v &=& \frac{7}{5} \\ x &=& \left(0, \frac{4}{5}, \frac{1}{5}, 0, 0\right) \\ y &=& \left(\frac{2}{5}, \frac{3}{5}\right) \\ \end{eqnarray}

Задача 14

Проверете дали векторите $(330, 490, 180)$, и $(330, 500, 190)$ принадлежат на ядрото на играта, зададена със следната характеристична функция:

(3)

\begin{eqnarray} & &v(\{1\}) = 200 \quad v(\{2\}) = 300 \quad v(\{3\}) = 0 \\ & &v(\{1, 2\}) = 800 \quad v(\{2,3\}) = 650 \quad v(\{1, 3\}) = 500 \\ & &v(\{1,2,3\}) = 1000 \\ \end{eqnarray}

покажи

Сумата на елементите на втората делба е $1200 \ne v(\{1,2,3\}) = 1000$, следователно тя не е от ядрото. Иначе за всяко същинско подмножество, сумата от числата в делбата е повече от сумата, която може да се изкара от подмножеството, следователно първата е от ядрото.

Задача 15

Дадена е кооперативна игра на $n$ играчи, определена от характеристичната функция $u$. Предполагаме, че:

(4)

\begin{eqnarray} \sum_{i=1}^{n} u(\{i\}) < u(N) \qquad N = \{1,\dots, n\} \\ u(N) = u(\{i\}) + u(N \setminus \{ i \}) \qquad \forall i \in N \\ \end{eqnarray}

Докажете, че ядрото на тази игра е празно.

покажи

Нека $x = (x_1, \dots, x_n)$ е една делба от ядрото.
Ако $x_1 > u(\{1\})$, то може да конструираме нова делба $y = (y_1, \dots, y_n)$ в която:

(5)

\begin{align} y_i = \begin{cases} u(\{1\}) & i = 1 \\ x_i + \frac{x_1 - u(\{1\})}{n-1} & i \ne 1 \\ \end{cases} \end{align}

Т.е всички без първия са се обединили и са обрали парите на първия, като не са надвишили техния потенциален максимум $u(N \setminus \{1\}) = u(N) - u(\{1\})$. Т.е получихме, че $x \underset{N\setminus\{1\}}< y$.
Като приложим разсъждението за всяко $i$ излиза, че всички координати на елемент от делбата са по $u(\{i\})$, което пак не е добре, защото сумата им не е $u(N)$ (от дефиницията на делба).
Следователно ядрото е празно.