Теория игр

Evilution · Сообщение **Evilution** » 19 июл 2010, 09:52

Здравствуйте уважаемые форумчане.
Возникли вопросы по поводу некоторых зачачек по теории игр, поэтому публикую их на проверку. Заранее спасибо.

№1. Условие:
Найти все равновесия по Нэшу.
$\begin{pmatrix} & A_2 & B_2 & C_2 \\ A_1 & (2;1) & (1;1) & (4;2) \\ B_1 & (3;4) & (1;2) & (2;3) \\ C_1 & (1;3) & (0;2) & (3;0) \end{pmatrix}$

Решение:
Равновесие по Нэшу - такое значение игры, при котором игрок, отклонившись от данной стратегии, только ухудшит свое положение.
Исключаем доминируемую стратегию $$C_1$$

. Затем доминируемую стратегию $$B_2$$

. Итого существует 2 равновесия по Нэшу - это $$(3;4)$$

и

.

№2. Условие:
Игроки I и II торгуются по поводу одного доллара. Они одновременно называют доли $$S_1$$

и

, которые хотят иметь ( $S_1;S_2\ge 0$ ). Если окажется, что $$S_1+S_2>1$$

, то оба игрока не получают ничего. Каково равновесие по Нэшу?

Решение:
Тут на ум приходит сразу $$(0,5;0,5)$$

, так как оба игрока рациональны, и им будет не выгодно отклоняться от своих стратегий в этом случае.

Ho не уверен, правильно ли это... Ведь кто-то из них может назвать долю $$0,4$$

, другой

, тогда им тоже невыгодно будет откланяться от этой стратегии, означает ли это, что тут бесконечно много равновесий по Нэшу?

Либо, исключая доминируемые стратегии, оба игрока назовут долю $$1$$

, то есть забрать доллар, и тогда равновесие по Нэшу - это $$(0;0)$$

?

№3. Условие:
Пусть есть $$n$$

фирм, выпускающих однородную продукцию. Пусть каждая фирма выпускает объем продукции $$q_i$$

. Весь объем продукции обозначим $$Q=q_1+q_2+...+q_n$$

. Кривая спроса имеет вид $$P=a-Q$$

. Затраты на производство одной единицы продукции равны $$c$$

. Фирмы выбирают свои объемы производства независимо. Найти равновесие по Нэшу.

Решение:
Прибыль предприятия определяется, как
$\lambda_i=P\cdot q_i-c\cdot q_i$

Предприятия максимизируют прибыть, поэтому найдем максимум всех $$n$$

функций прибыли. частные производные и приравняем их к нулю:
$\frac {\delta \lambda_i} {\delta q_i}=a-2q_i-\sum_{j=1,i\ne j}^{n}{q_j}-c=0$

Отсюда получаем:
$q_1=\frac {1} {2}(a-(q_2+q_3+...+q_n)-c)$
$q_2=\frac {1} {2}(a-(q_1+q_3+...+q_n)-c)$
.....................................................................................
$q_n=\frac {1} {2}(a-(q_1+q_2+...+q_{n-1})-c)$

Решая систему получаем $q_1=q_2=...=q_n=\frac {a-c} {n+1}$

№4. Условие:
Сохраняются условия задачи №3, однако теперь фирмы имеют разные затраты $$c_1$$

и

.
a) Найти равновесие по Нэшу, если $$0<c_i<a/2 $$

б) Найти равновесие по Нэшу, если $$c_1<c_2<a$$

, но

Решение:
Решая аналогично предыдущей задаче, получаем
$q_1=\frac {a-2c_2-c_1} {3}$

$q_2=\frac {a-2c_1-c_2} {3}$

a) Ничего, по видимому, не меняется.
б) Тут у фирмы №1 производится отрицательный объем продукции, следовательно равновесие по Нэшу - это $(0;\frac {a-c_2} {2})$ , то есть фирма №2 производит объем продукции из расчета, что фирма №1 не произведет ничего. Однако тут вопрос, может все таки верный ответ - это $(0;\frac {a-2c_1-c_2} {3})$ , так как фирмы фирмы выбирают объемы одновременно и независимо?

№5. Условие:
Рассмотрим совокупность избирателей, равномерно распределенных вдоль идеологического спектра (отрезок единичной длины $$(0;1)$$

). Одновременно каждый кандидат выбирает платформу кампании (точку на этом идеологическом спектре). Избиратели голосуют за того, кто оказался ближе к ним. Если кандидаты выберут одно и тоже место, победитель определяется c помощью бросания монеты.
a) Если есть всего 2 кандидата, каково равновесие по Нэшу?
б) Каково равновесие по Нэшу при участии трех кандидатов?

Решение:
a) Исходя из определения равновесия по Нэшу, ответ будет $$(0,5;0,5)$$

.
б) Опять же, $$(0,5;0,5;0,5)$$

, и пусть бросают монетку?

Ian · Сообщение **Ian** » 19 июл 2010, 13:46

ИМХО, Нэш и не утверждал что равновесие по Нэшу достигается на стратегиях разумных во всех отношениях. Просто формальное условие.
1. Я понимаю, что тут игра не c нулевой суммой, но не помню какое из чисел что значит. Действительно ли $$C_1$$

доминируемая. B любом случае ответ надо давать перечислением наборов стратегий, например $$(B_1,A_2),..$$

A может тут спрашивают и ответ в смешанных стратегиях(еще один добавится к списку)?
2.Любые $$S_1>0;1-S_1>0$$

равновесны по Нэшу. Вы и обосновали.
3.B первой формуле опечатка, издержки c минусом. A дальше верно
4a) верно, 4б) первый вариант.
5a)верно,5б)Равновесие по Нэшу не достигается никогда. При неравных значениях крайним (-ему) кандидатам выгодно сместиться к среднему, a при равных каждому "слегка отбежать".

Evilution · Сообщение **Evilution** » 19 июл 2010, 15:29

Спасибо за отклик Ian.

1) Например, если игроки играют $$A_1A_2$$

, то первый получает 2, второй получает 1. B смешанных стратегиях наверняка есть, но искать долго

2) Ясно, спасибо.

3) Исправил

5б) Да, точно, двое же делят голоса пополам.

He сочтите за наглость, я опубликую еще пару задачек.

№6. Условие:
B каждой из двух фирм есть по одной вакансии. Фирма $$A$$

предлагает зарплату $$w_1$$

, фирма

предлагает зарплату $$w_2$$

, причем $\frac {1} {2} w_1<w_2<2w_1$ . Два работника ищет работу. Если они обращаются в разные фирмы, то получают соответствующие ЗП. Если в одну и ту же, то фирма нанимает работника случайным образом, второй остается без работы. Игра представлена в следующей форме:

$\begin{pmatrix} & A_2 & B_2 \\ A_1 & (\frac {1} {2}w_1;\frac {1} {2}w_1) & (w_1;w_2) \\ B_1 & (w_2;w_1) & (\frac {1} {2}w_2;\frac {1} {2}w_2) \end{pmatrix}$

Решение:
Тут по видимому существует равновесие по Нэшу в смешанных стратегиях, это $\frac {1} {2} A; \frac {1} {2} B$ .

№7. Условие:
Армия $$A$$

обладает единственным самолетом, a армия $$B$$

- единственным зенитным орудием. Существует 3 цели, одну из которых армия $$A$$

может выбрать для бомбежки, армия $$B$$

выставляет зенитное орудие для защиты одной из целей.
Ценность целей определяется, как $$v_1>v_2>v_3>0$$

. Армия

пытается максимизировать ущерб, армия $$B$$

- минимизировать. Найти равновесие по Нэшу в смешанных стратегиях.

Решение:
Вот тут мне как то не понятно, c чего начать. Выписал матрицу игры:

$\begin{pmatrix} & B_1 & B_2 & B_3 \\ A_1 & (0;0) & (3;-3) & (3;-3) \\ A_2 & (2;-2) & (0;0) & (2;-2) \\ A_3 & (1;-1) & (1;-1) & (0;0) \end{pmatrix}$

Далее надо искать равновесие по Нэшу как обычно?:

$\{{p(0n+3m+3(1-n-m))=q(2n+0m+2(1-n-m)) \\ q(2n+0m+2(1-n-m))=(1-p-q)(1n+1m+0(1-n-m))}$
и
$\{{n(0p-2q-1(1-p-q))=m(-3p-0q-1(1-p-q)) \\ m(-3p-0q-1(1-p-q))=(1-n-m)(-3p-2q-0(1-p-q))}$

Или надо выписать функции прибылей, максимизировать их, a затем оттуда находить $$n$$

,

и

?

Спасибо.

СергейП

Если я правильно понял

Evilution писал(а):Source of the post 1) Например, если игроки играют , то первый получает 2, второй получает 1. B смешанных стратегиях наверняка есть, но искать долго

то 1 задача имеет седловую точку.
Так как

Evilution писал(а):Source of the post Исключаем доминируемую стратегию . Затем доминируемую стратегию . Итого существует 2 равновесия по Нэшу - это и .

Стратегия

не доминируемая (по 3-ему столбцу), a $$B_2$$

не только не доминируемая, a доминирующая.
Поэтому убираем 1-ый и 3-ий столбцы, a потом уже 2-ю и 3-ю строки.
Получаем седловую точку - $$(1,1)$$

, т.e. стратегии $$A_1$$

и

Ian · Сообщение **Ian** » 19 июл 2010, 16:47

Evilution писал(а):Source of the post №6. Условие:
B каждой из двух фирм есть по одной вакансии. Фирма предлагает зарплату , фирма предлагает зарплату , причем $\frac {1} {2} w_1<w_2<2w_1$ . Два работника ищет работу. Если они обращаются в разные фирмы, то получают соответствующие ЗП. Если в одну и ту же, то фирма нанимает работника случайным образом, второй остается без работы. Игра представлена в следующей форме:
$\begin{pmatrix} & A_2 & B_2 \\ A_1 & (\frac {1} {2}w_1;\frac {1} {2}w_1) & (w_1;w_2) \\ B_1 & (w_2;w_1) & (\frac {1} {2}w_2;\frac {1} {2}w_2) \end{pmatrix}$
Решение:
Тут по видимому существует равновесие по Нэшу в смешанных стратегиях, это $\frac {1} {2} A; \frac {1} {2} B$ .

р-вероятность выбора 1й фирмы 1м работником.,q- вероятность выбора ee вторым работником.Приравнивая к 0 производную от функции среднего дохода 1го работника, получил $q=\frac {2w_1-w_2}{w_1+w_2}$ . Делая то же самое c функцией дохода 2го работника,получаем,что этому же числу должно быть равно р.Ответ стратегии $(A_1\frac {2w_1-w_2}{w_1+w_2}+B_1\frac {2w_2-w_1}{w_1+w_2};A_2\frac {2w_1-w_2}{w_1+w_2}+B_2\frac {2w_2-w_1}{w_1+w_2})$

№7. Условие:
Армия обладает единственным самолетом, a армия - единственным зенитным орудием. Существует 3 цели, одну из которых армия может выбрать для бомбежки, армия выставляет зенитное орудие для защиты одной из целей.
Ценность целей определяется, как . Армия пытается максимизировать ущерб, армия - минимизировать. Найти равновесие по Нэшу в смешанных стратегиях.
Решение:
надо выписать функции прибылей, максимизировать их, a затем оттуда находить ,, и ?

Конечно,это же по определению равновесия по Нэшу
Мне кажется так
$\{{(0n+3m+3(1-n-m))=(2n+0m+2(1-n-m)) \\ (2n+0m+2(1-n-m))=(1n+1m+0(1-n-m))}$ то есть изменение вероятности атаки 1й цели для атакующих ни за счет вероятности атаки 2й цели, ни 2й за счет 3й не улучшает матожидания.Однако двух положительных (m,n) в сумме меньших 1 не получилось.Надо разбираться дальше.
Предполагаю,что не будет равновесия

Evilution · Сообщение **Evilution** » 19 июл 2010, 16:59

СергейП писал(а):Source of the post
Получаем седловую точку - , т.e. стратегии и

Стратегия

строго доминируется стратегией $$A_1$$

, исключаем $$C_1$$

. Далее смотрим на то, что осталось. Стратегия $$B_1$$

строго доминируется стратегией $$C_2$$

, исключаем $$B_1$$

.
Далее у нас получается матрица $$2x2$$

c двумя равновесиями по Нэшу.

Ian писал(а):Source of the post
Однако двух положительных (m,n) в сумме меньших 1 не получилось.Надо разбираться дальше.
Предполагаю,что не будет равновесия

У меня тоже самое, после попытки решить получил отрицательную вероятность.
Равновесие здесь должно быть, так как тут задачи без подвохов. Раз спрашивается, значит есть. Пытался минимизировать функцию выигрыша, получил вероятность больше единицы

СергейП

Пробуем еще раз читать:

Evilution писал(а):Source of the post 1) Например, если игроки играют , то первый получает 2, второй получает 1.

Тогда, если 1-ый выбирает $$A_1$$

, в 2-ой - $$C_2$$

, то выигрыш 1-ого составит $$4-2=2$$

, a если 1-ый выберет $$C_1$$

, то выигрыш 1-ого $$3-0=3$$

, наконец

, т.e. повторяю стратегия $$C_1$$

не доминируется $$A_1$$

Evilution · Сообщение **Evilution** » 19 июл 2010, 17:32

СергейП писал(а):Source of the post
Пробуем еще раз читать:
Evilution писал(а):Source of the post 1) Например, если игроки играют , то первый получает 2, второй получает 1.
Тогда, если 1-ый выбирает , в 2-ой - , то выигрыш 1-ого составит , a если 1-ый выберет , то выигрыш 1-ого , наконец , т.e. повторяю стратегия не доминируется

Этот пример я привел, как ответ Ian'у на вопрос, что означают какие цифры.

Ha счет стратегий. Посмотрите, первая цифра - это выигрыш первого игрока. Какую бы стратегию не играл второй игрок, первый игрок всегда получит меньше от игры $$C_1$$

, нежели от игры $$A_1$$

. Поэтому первый игрок никогда не будет играть $$C_1$$

.

PS: Тут мы не вычитаем выигрыш второго игрока из выигрыша первого.

Evilution · Сообщение **Evilution** » 19 июл 2010, 17:44

Ian писал(а):Source of the post
Предполагаю,что не будет равновесия

Обозначим

,

и

- вероятности игры первым игроком своих стратегий. $$n$$

,

и

- аналогично для второго игрока.

Составим систему:

$\{{-2p-1(1-p-q)=-3p-1(1-p-q) \\ -3p-1(1-p-q)=-3p-2q}$

Решая, получим: $p=\frac {2} {11}$ , $q=\frac {3} {11}$ и $1-p-q=\frac {6} {11}$

Аналогично для второго игрока.

СергейП

Evilution писал(а):Source of the post Ha счет стратегий. Посмотрите, первая цифра - это выигрыш первого игрока. Какую бы стратегию не играл второй игрок, первый игрок всегда получит меньше от игры , нежели от игры . Поэтому первый игрок никогда не будет играть .

PS: Тут мы не вычитаем выигрыш второго игрока из выигрыша первого.

Понятно.
Почему-то не понял сразу, что игра c ненулевой суммой, хотя Ian писал об этом.

yourdomain.com