Дана матрица некоторой игры. Необходимо найти все равновесия в чистых стратегиях. Вот сама матрица:
\begin{bmatrix}5,4 & 5,3 & 1,5 & 2,1 & 4,2 \\ 3,4 & 3,6 & 5,7 & 2,5 & 5,3 \\ 3,2 & 2,1 & 7,0 & 3,5 & 6,3 \\ 4,2 & 8,4 & 3,3 & 1,4 & 3,6\end{bmatrix} В этой матрице нет доминирующих стратегий, к сожалению. Простым перебором клеток матрицы нашел несколько равновесий. Вот они (взял их в скобки): \begin{bmatrix} 5,4 & 5,3 & 1,5 & 2,1 & 4,2 \\ 3,4 & 3,6 & 5,7 & 2,5 & 5,3 \\ 3,2 & 2,1 & 7,0 & \big(3,5) & 6,3 \\ 4,2 & 8,4 & 3,3 & 1,4 & 3,6\end{bmatrix} Есть ли тут еще какие-либо равновесия?

UPD Подправил вторую матрицу, поскольку в ней всего одно равновесие Теперь нужно найти смешанные равновесия. Считаю, что первый игрок (слева) выбирает свои стратегии с вероятностями p, q, r, s.
Соответственно считаю выигрыш второго игрока.
стратегия t1: 4p + 4q + 2r + 2s
стратегия t2: 3p + 6q + r + 4s
стратегия t3: 5p + 7q + 0r + 3s
стратегия t4: p + 5q + 5r + 4s
стратегия t4: 2p + 3q + 3r + 6s
Ну и необходимое условие: p + q + r + s = 1
Теперь необходимо решить эту систему. Получается как-то плохо.. я какую-то ошибку допустил?

задан 19 Окт '13 21:46

изменен 19 Окт '13 23:41

А по какому принципу Вы здесь искали равновесия?

(19 Окт '13 22:09) falcao

Обычным перебором. Если находится клетка, из которой ни первому, ни второму игроку двигаться не выгодно, то это равновесие Нэша. Более красивого способа не знаю.. если бы хотя бы слабо доминируемые стратегии были, то было бы проще

(19 Окт '13 22:10) Stas0n

Какие-то замечания? ошибки? идеи?

(19 Окт '13 22:34) Stas0n

Давайте проверим. Прежде всего, нужно уточнить, кому выгодно увеличение, а кому уменьшение (это часть постановки задачи). В любом случае, интересы у игроков противоположны. Поэтому я не вижу, почему элемент $%5,4$% считается точкой равновесия. Допустим, игрок А стремится получить как можно большее число из таблицы, тогда для В всё наоборот. И если А выберет первую строку, то В не выгодно останавливаться на первом столбце -- он выберет третий, чтобы минимизировать свой проигрыш.

(19 Окт '13 23:31) falcao

да, нашел этот косяк. уже исправил.
Добавил комментарий новый. Нужно Ваше мнение.

(19 Окт '13 23:36) Stas0n

@Stas0n: число $%3,5$% является наибольшим в своём столбце, но оно не будет наименьшим в строке. Если А выбирает 3-ю строку, то В может уменьшить свой проигрыш, выбирая не 4-й столбец, а 2-й.

(19 Окт '13 23:38) falcao

@falcao, ниже комментарии не разрешаются, поэтому добавлю здесь... Осталось одну вещь уточнить: верно ли то, что каждый стремится максимизировать свой личный выигрыш, а выигрыш противника не играет никакой роли? - Да, конечно... рациональность игроков - это одно из основополагающих предположений теории игр... поэтому каждый игрок старается максимизировать свой выигрыш , используя всю имеющуюся у него информацию (с)...

(20 Окт '13 0:49) all_exist

@stas0n, к сожалению под моим ответом мне комментировать не получается ... поэтому опять же отвечу здесь...

Во-первых, несмотря на Вашу "запись" отыскания смешанных стратегий, замечание от @falcao, побуждает задать вопрос - а не антагонистическая ли у Вас игра?...

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

(20 Окт '13 0:58) all_exist

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

(20 Окт '13 1:03) Stas0n

@stas0n, как же эта игра может быть антогонистической, если выигрыши игроков не противоположны? - Так в записи антагонистической игры записываются только выигрыши первого игрока, которые равны проигрышу второго... (для краткости записи)... поэтому вопрос остаётся в силе - например, $%(5,\;4)$% - это два выигрыша, записанные целыми числами, или один - $%5.4$%, записанный дробным числом?...

(20 Окт '13 1:07) all_exist
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
1

@stas0n, Какие-то замечания? ошибки? идеи? - В данной игре только одно равновесие Нэша - это профиль $%(s_3; t_4)$% с вектором выигрышей $%(3; 5)$%...

Профиль $%(s_1; t_1)$% с вектором выигрышей $%(5; 4)$% не является равновесием, поскольку $%t_1$% не является наилучшим ответом на $%s_1$%... здесь наилучшим ответом будет $%t_3$%...

Профиль $%(s_4; t_2)$% с вектором выигрышей $%(8; 4)$% не является равновесием, поскольку $%t_2$% не является наилучшим ответом на $%s_4$%... здесь наилучшим ответом будет $%t_5$%...

Других вариантов, кроме перебора, по сути, нет... доминирование даёт уменьшение размера игры, но дальше всё равно перебор...

=======================================

UPD: Я уже сказал, что не сталкивался с решением подобных задач в биматричном случае... поэтому дальше пойдут мои "измышления"...

Доминирование смешанной стратегии над чистой означает, что соответствующий вектор выигрышей чистой стратегии можно представить линейной комбинацией векторов других стратегий... то есть задача сводится к проверке линейной зависимости векторов (определения ранга матрицы)... и проверке того, что возможна линейная комбинация с коэффициентами, в сумме равными 1...

Как это делается "руками" я пока себе слабо представляю... а других мыслей пока нет... Хотя сделанное "измышление", видимо, не до конца правильное...

UPD2: может всё-таки уточните у преподавателя насчёт антоганистичнсоти... тогда бы и "руками" можно было бы порешать...

ссылка

отвечен 19 Окт '13 23:29

изменен 20 Окт '13 1:48

@stas0n, А что касается смешанных стратегий? - Насколько я знаю, то если в игре есть равновесие Нэша в чистых стратегиях, то оно будет равновесием и в смешанном расширении...

(19 Окт '13 23:45) all_exist

Хм... увидел дополнения...

Вообще-то системы Вы пока не получили... у Вас написаны пока какие-то выражения, а не уравнения или неравенства... Наиболее простая ситуация нахождения смешанных стратегий в антагонистическом случае, там хорошо работает линейное программирование и теория двойственности... А в произвольном случае биматричной игры, кроме вышеупомянутого утверждения, я каких-то подробностей нахождения не встречал...

(19 Окт '13 23:56) all_exist

Система соответственно получится, если приравнять выигрыши второго игрока от всех стратегий. Т.е. вот так:
4p + 4q + 2r + 2s = 3p + 6q + r + 4s
и т.д...

(20 Окт '13 0:11) Stas0n

Система соответственно получится, если приравнять выигрыши второго игрока от всех стратегий - даже в антагонистических играх это не так...

(20 Окт '13 0:18) all_exist

@all_exist: судя по всему, я неправильно понял само условие. Мне подумалось, что в матрице представлены десятичные числа с запятой, в то время как из контекста обсуждения стало понятно, что подразумеваются пары целых чисел. Поэтому то, что я сказал выше про $%3,5$%, не соответствовало предполагаемому описанию.

Чтобы я полностью вник, может быть, Вы мне в двух словах опишете все правила и "условности", связанные с этой игрой?

(20 Окт '13 0:29) falcao

@falcao, простое обобщение... первое число - выигрыш первого игрока... второе - выигрыш второго...

(20 Окт '13 0:33) all_exist

@all_exist: спасибо, теперь я понял. Осталось одну вещь уточнить: верно ли то, что каждый стремится максимизировать свой личный выигрыш, а выигрыш противника не играет никакой роли? В смысле того, что 3,100 мне предпочтительнее, чем 2,1?

(20 Окт '13 0:44) falcao

@all_exist, как же тогда тут искать смешанные равновесия?

(20 Окт '13 0:52) Stas0n

В описании задачи вот что: (a) Найти все чистые равновесия Нэша
(b) Последовательно исключите все доминируемые стратегии. При удалении стратегий указывайте, какой чистой или смешанной стратегией она доминируется.
(c) Найдите все смешанные равновесия.

У меня еще вопрос - как указать, что какая-то стратегия доминируется смешанной?

(20 Окт '13 0:53) Stas0n

Насчет антагонистичности - мы попросту не добрались еще до игр с нулевой суммой.

(20 Окт '13 2:21) Stas0n
показано 5 из 10 показать еще 5
10|600 символов нужно символов осталось
0

В чистых стратегиях здесь только одной равновесие - это профиль (s3;t4) с вектором выигрышей (3;5).
Оно же, так же, является равновесием в смешанных стратегиях.
Осталось найти еще какие-либо смешанные стратегии или показать, что их нет.

ссылка

отвечен 20 Окт '13 1:10

@all_exist, место кончилось, так что продолжу здесь. Это не антогонистическая игра. Так, 3,5 - это выигрыш первого и второго игроков соответственно.

(20 Окт '13 1:11) Stas0n

Осталось найти еще какие-либо смешанные стратегии или показать, что их нет. - То есть это у Вас всё-таки биматричная игра... тогда вопрос - решение предполагалось "руками" или "компьютерными вычислениями"?...

(20 Окт '13 1:13) all_exist

Честно говоря - не знаю. Но, на сколько я могу предположить, то тут вовсе не обязательно привлекать какие-то дополнительные мощности, кроме своего мозга.

(20 Окт '13 1:16) Stas0n
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×54
×29

задан
19 Окт '13 21:46

показан
1346 раз

обновлен
20 Окт '13 2:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru