Теория игр... популярно о сложном и интересном

[FMM]

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

Почти все правильно. Уточню в личке. В том числе и строгую логику.

Добавлено спустя 2 минуты 31 секунду:

Это там где наши и немецкие пропогандоны увеличили в разы потери мирного населения..
Плохое начало.

– Зачем мятутся народы? – сказал он наконец. – Объяснил бы тебе спидометр чуткий, да глуп он, ибо прибор суть. Мнилось Роману, что бежал он от мира, ан мир его и поймал! Горе проспавшему перемены! Будет теперь тыкаться наугад, яко слепород… Эх, чего там – сыплются кости наши в челюсти преисподней! (с)

Там просто изначально фашики кричали о более 200000 жертв, наши писали про 135 тысяч. Официальное же число, основанное на исследованиях немецких историков - менее 20 тысяч.

Добавлено спустя 3 минуты:

Есть богач, который готов дать до 1 миллиарда долларов

Такая в мире творится хрень, что ты не поверишь! Появляются банки-однодневки, раздают кучу кредитов первым встречным и бесследно исчезают! Значит, кому-то это надо…

Такого еще в практике не было, чтобы миллиард давали. Рекорд одноразового пожертвования - 600 миллионов от Гордона Мура(один из основателей Интела)
А вот более 100 млн. - дают сравнительно часто.

Добавлено спустя 3 минуты 35 секунд:

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

Добавлено спустя 8 минут 54 секунды:

Кстати, доминирование есть сильное и слабое. Сильное, когда выигрыши строго больше. Слабое - когда есть и равные.

 

[FMM]

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

Здесь 2 игрока и 5 стратегий у каждого.
Ищем наилучшие ответы.
1 игрок: для стратегии 1 наилучшие ответы - B и D, для 2 - B, 3 - A,B, 4 - E, 5 - E.
2 игрок: для стратегии A наилучший ответ - 4, для B - 4, C - 1, D - 5, E - 1.

Добавлено спустя 8 минут 44 секунды:

Теперь можно вводить центральное понятие теории игр равновесие Нэша.
Набор стратегий называется равновесием Нэша, если каждая из стратегий является наилучшим ответом на остальные из данного набора.
Легко заметить, что в примере с поиском наилучших ответов нет равновесий по Нэшу. Для этого нужен был бы набор стратегий, отмеченный двумя плюсиками.
Этого легко добиться. Если бы набор стратегий (B,1) давал выигрыш (3,6), а не (3,4), то эта пара стратегий была бы равновесием по Нэшу.

Добавлено спустя 31 минуту 17 секунд:

Отметим основные минусы данного понятия. Кроме философских вопросов о рациональном поведении игроков, есть вполне серьезные изъяны.
Рассмотрим эти проблемы на примерах

Во-первых, равновесие может не быть оптимальным решением. Это показывает дилемма заключенных.(ее описал mtu на странице 1 топика). На иллюстрации числа со знаком минус означают, на сколько сядут в тюрьму подозреваемые в зависимости от выбранной стратегии. Здесь есть оптимальная пара стратегий - (молчать, молчать).
Но равновесием по Нэшу будет пара (настучать, настучать).
Во-вторых, равновесий может быть много. Пусть муж и жена раздельно решают проблему, куда пойти - в театр или на футбол. Если для них главным ценностью является общество друг друга(что выражено в выигрышах на рисунке), то возникнут 2 равновесия по Нэшу.

 

[ник69]

Уточню в личке.

Спасибо, прочитал и принял к сведению

В том числе и строгую логику.

Логика! Как много в этом слове для сердца русского слилось...

"Я использую "рассеянную" технику суфийских авторов. Отдельные темы в этой книге не всегда рассматриваются в линейном, "логическом" порядке - обычно я располагал их в порядке нелинейном, психо-логическом, рассчитанном на прокладывание новых путей мышления и восприятия." (с) Роберт А. Уилсон

Вы уважаемый FMM читали чего нибудь из ,мной очень уважаемого, Уилсона?
И не знакомы ли с работами доктора Э. Берна? (это я всякие вопросы задаю что бы немного разнообразить изложение поразившей меня "теории игр" )

Но равновесием по Нэшу будет пара (настучать, настучать).

"Итак, там, где аристотелевская логика признает лишь два класса - "истинное" и "ложное" , - пост-копенгагенистская наука склонна признавать четыре, хотя один лишь доктор Анатолий Рапопорт четко сформулировал их: "истинное", "ложное" , "неопределенное" и "бессмысленное" ... " (с) типа шутка

 

[FMM]

И не знакомы ли с работами доктора Э. Берна?

Моя девушка сейчас читает книгу Берна (Игры, в которые играют люди)
Может и я почитаю.

Добавлено спустя 2 минуты 3 секунды:

FMM читали чего нибудь из ,мной очень уважаемого, Уилсона?

Нет

 

[FMM]

Продолжим обсуждение понятия равновесия по Нэшу.

Кроме уже упомянутых недостатков(проблемы неоптимальности и множественности), есть еще одна. А именно реалистичность в жизни. И здесь есть несомненные проблемы.

Рассмотрим простой пример(но важный). Есть 2 человека. Им предлагают сыграть в простую игру. 1 игроку дают 100 долларов и предлагают разделить между собой и 2 игроком. Если 2 игроку не понравится дележ, то оба ничего не получают.
Так вот, по теории игр 1 игрок может взять себе 99 долларов 99 центов, а второму дать 1 цент и тот согласится, т.к. 1 цент лучше, чем ничего.

Но в реальности все намного сложнее. Здесь на сцену выходит экспериментальная теория игр.

1 подобную игру проводили между студентами Гарварда. Им также предлагали 100 долларов. Выяснилось, что 2 игрок начинает соглашаться где-то между 30 и 40 долларами. Если меньше, то отказывался.

Понимая, что кроме чувства справедливости играло большую роль самомнение студентов данного универа(100 долларов - не та сумма для них, чтобы соглашаться на позорный дележ), ученые поехали в Африку.

И начали предлагать деньги племенам. Для тех 100 баксов огромные деньги(ехали не в совсем дикие племена, где вообще не знают, что такое деньги). За такую сумму можно целый год племя содержать. Но даже там племя, получавшее менее 30 долларов при дележе, отказывалось от денег. Все-таки чувство справедливости(зависти) победило даже здесь.

Но мы все же будем считать, что игроки рациональны и скорее согласятся на кроху, чем на ноль.
Далее, небольшое, но важное замечание. В игре с дележом будем считать, что равновесием является не (99.99, 0.01), а (100,0). Это в теории игр сделано для удобства. Себе можно представлять, что 2 игрок все же получает какую-то минимальную кроху(некий эпсилон - цент, копейка и т.д.).
Для владеющих математикой здесь есть проблема недискретности множества действительных чисел. кто не знает, можете забить, это непринципиально.

Добавлено спустя 4 минуты 24 секунды:

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

Добавлено спустя 5 минут:

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

 

[ник69]

Кстати, скоро уже вручение Нобеля по экономике.

Русские в списках есть?

В прошлом году я играл на "академическом тотализаторе" и угадал.

Поздравляю! Но сдается слово "угадал" надо было бы в кавычки взять, небось рассчитали все по теории?

У меня был, правда, список из 4 фамилий..

Вот и я об энтом...

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

Ну и отлично!! :good: Чес гря никогда бы не подумал что буду на "экономических ветках" чего то разговаривать... Не зря я грил шо экономика ,для моего подвижного организма , скучна... Но Вы меня дико заинтриговали! Правда в связи выходом "СТАЛКЕРА зов Припяти" , я немного выбыл из "игры" но сейчас смею Вас уверить я почти в строю...

Из простой задачи с дележом денег можно получить знаменитую проблему

:good: тут конечно без комментариев

 

[FMM]

Кстати, скоро уже вручение Нобеля по экономике.

Русские в списках есть?

В ближайшие лет 15 ждать не стоит..

Добавлено спустя 15 минут 23 секунды:

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

Какие тут могут быть теории..
Просто есть несколько основных областей экономики, и обычно их чередуют. Вот и вся логика.
Если по финансам дадут, то Юджин Фама - явный фаворит (ему в пару могут еще Кеннета Френча добавить). Но в прошлом году рухнул финансовый сектор и я не стал на него ставить
Я кроме Пола Кругмана(который выиграл) еще ставил на Питера Даймонда (экономика общественного сектора), Оливера Харта(теория контрактов) и Томаса Сарджента(макроэкономика).
Еще есть группа явных кандидатов. Хансен по эконометрике, Барро в макре, Милгром по аукционам
Могут наконец европейцу дать - тогда Жану Тиролю.
Есть Диксит, Гроссман, но им вряд ли сейчас, слишком близко к Кругману.
Ну и есть еще Ллойд Шепли - один из моих любимцев. Ему уже очень много лет, похоже про него забыли..
Могут, конечно, молодым дать, но вряд ли.

Добавлено спустя 1 час 16 минут 41 секунду:

Ну и отлично!! :good: Чес гря никогда бы не подумал что буду на "экономических ветках" чего то разговаривать... Но Вы меня дико заинтриговали! Правда в связи выходом "СТАЛКЕРА зов Припяти" , я немного выбыл из "игры" но сейчас смею Вас уверить я почти в строю...

Меня больше волнует, что у вас вопросов нет.. Это бывает в 2 случаях - когда все понятно или ничего не понятно.
Ибо равновесие по Нэшу - ключевое понятие. Поэтому его желательно понять, как оно находится.

 

[ник69]

Это бывает в 2 случаях - когда все понятно или ничего не понятно.

:OK-) Пока верно скорее второе чем первое , (сами понимаете всякие "Зовы припяти" ) На работе всякие дэмоны сосредоточится не сильно дают... Но я исправлюсь , дома посижу внимательно померкую шо к чему... Вопросы задам :OK-)

 

[FMM]

http://www.lenta.ru/news/2009/10/12/nobeleconom/
Оригинально. Если Уильямсон еще рассматривался как кандидат, то про Олстром я вообще впервые слышу..
Век живи, век учись.. :???:

Добавлено спустя 6 минут 18 секунд:

Это бывает в 2 случаях - когда все понятно или ничего не понятно.

:OK-) Пока верно скорее второе чем первое , (сами понимаете всякие "Зовы припяти" ) На работе всякие дэмоны сосредоточится не сильно дают... Но я исправлюсь , дома посижу внимательно померкую шо к чему... Вопросы задам :OK-)

По теме я пока паузу взял, вам пока с текущим материалом разобраться надо.

 

[ник69]

Век живи, век учись.

Вот и я ж об этом!

По теме я пока паузу взял, вам пока с текущим материалом разобраться надо.

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

 

[FMM]

Вопросы по поводу обсуждаемого, задам в личку

Главное, задайте.

 

[ник69]

Главное, задайте.

Спасибо за развернутые и главное доступные пониманию , ответы (в личке)
Я смотрю Вас не поставить в тупик даже самыми глупыми вопросами :good:

 

[FMM]

Главное, задайте.

Спасибо за развернутые и главное доступные пониманию , ответы (в личке)
Я смотрю Вас не поставить в тупик даже самыми глупыми вопросами :good:

Кстати, можно и на "ты". Мы с Экономистом так общаемся.

Добавлено спустя 2 часа:

Итак, продолжим.
Во-первых, еще подробней изучим нормальную и развернутую форму игры(здесь я не все разъяснил), а во-вторых продвинемся в понятии равновесия по Нэшу.
Рассмотрим знаменитый пример "Crying Game", где ребенок может заплакать, чтобы заставить родителей купить ему игрушку.
Родители могут купить или не купить игрушку, а ребенок - заплакать или не заплакать.
Полезность родителей следующая: -2 за рыдания и -1 за покупку игрушки
У ребенка: -1 - за рыдания и 1 за игрушку. Выглядит это так в развернутой форме

Здесь я забыл надписать игрока child(ребенок).
Как же это все выглядит в нормальной форме. Вроде бы так

но на самом деле ситуация более тонкая. Стратегией малыша является не пара плакать и не плакать, а более сложная конструкция. Ведь стратегии определяются еще до игры. Поэтому они должны будут описывать действе малыша в зависимости от ситуации. Он должен иметь ходы на любое действие родителей. Всего стратегий - четыре:
1)плакать в случае покупки, плакать, когда не купили
2)плакать, не плакать
3)не плакать, плакать
4)не плакать, не плакать
И выглядеть игра в нормальной форме должна следующим образом

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

 

[ник69]

Кстати, можно и на "ты". Мы с Экономистом так общаемся.

Я тоже .... ".. Значит, цепочка спрямляется, и мы становимся сопричастны уже напрямую!" (с) Можно и на "ты"

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

Сижу это я значит на работе задумчиво размышляя на вашими задачами, и такая наверное умственная деятельность на лице отражается что коллега проходя мимо остановился , с удивлением заглянул на монитор потом еще раз на меня и вынес строгий вердикт - "Печальное зрелище ! " затем торжественно помолчав добавил " Евгений Головин утверждал что всякий кто сходит с ума делает это сознательно и после серьёзного размышления"
В личку отпишу чуть позже :OK-)

 

[FMM]

Сижу это я значит на работе задумчиво размышляя на вашими задачами

Главное, не забывай, что наилучших ответов может быть несколько.
И здесь пока не надо какого-то креатива. Просто надо найти, где пересекаются наилучшие ответы игроков.

 

[FMM]

Итак, в чем же проблема в игре "Crying Game".
Найдем равновесия в этой игре. Берем нормальную форму игры, где у ребенка 4 стратегии.
Фиксируем стратегию "покупать игрушку". Наилучшие ответы - "не плакать, плакать" и "не плакать, не плакать" с полезностью 1.
При стратегии "не покупать игрушку", наилучшие ответы - "плакать, не плакать" и "не плакать, не плакать" с полезностью 0. Получаем 4 претендентов на равновесия по Нэшу.
Далее фиксируем стратегии ребенка.
При стратегии "плакать, не плакать", "не покупать игрушку" является наилучшим ответом, следовательно это равновесие по Нэшу(0>-3).
Аналогично с "не плакать, плакать" и "покупать игрушку"(-1>-2).
Но в случае "не плакать, не плакать", стратегия "не покупать игрушку" лучше, чем "покупать игрушку"(1>0).
В итоге, из 4 претендентов 3 оказались равновесиями по Нэшу.
Что же получается. Когда мы не совсем корректно ввели стратегии ребенка(2 стратегии, а не 4), то равновесие одно - не покупать и не плакать. Это легко проверить.
Как только мы все правильно определили(взяли 4 стратегии), равновесий стало много.

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

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

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

Решается проблема достаточно просто. Для этого введем самое простое очищение от равновесий - равновесие по Нэшу, совершенное по подыграм.(Subgame Perfect Nash Equilibrium).

 

[FMM]

Продолжаем. Введем простое понятие подыгры. Это просто любое поддерево в развернутой форме игры. Берем любую вершину, и дерево, выходящее из нее будет подыгрой.
В игре с родителями и ребенком сразу видно 2 подыгры, с вершинами, когда ходит ребенок.

Так вот набор стратегий является равновесием по Нэшу, совершенном по подыграм, если он является равновесием по Нэшу в каждой подыгре. Тогда такие равновесия легко искать и в развернутой форме игры. Для этого используется метод Backward Induction, т.е. обратная индукция. Игра решается снизу вверх, начиная от конечных вершин


Итак, смотрим подыгру, где родители уже решили покупать игрушку. Там у родителей 1 фиксированная стратегия - Buy. У ребенка 2 варианта - плакать(полезность 0) и не плакать(полезность 1), конечно, он выбирает стратегию "не плакать".


Смотрим подыгру, где родители уже решили не покупать игрушку. Там у родителей 1 фиксированная стратегия - Don't Buy. Здесь аналогично ребенок выбирает стратегию не плакать с полезностью 0.

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

Здесь родители знают, что ребенок плакать не будет, поэтому они выбирают "не покупать"(так как 0>-1).
В итоге, имеем единственное равновесие SPNE(Subgame Perfect Nash Equilibrium): "не покупать игрушку", "не плакать, не плакать".
Еще раз напомним, чего мы добились, введя более узкий тип равновесий SPNE.
Во-первых, мы можем сократить количество обычных равновесий по Нэшу, оставив только SPNE.
Во-вторых, их легко искать в развернутой форме игры. В итоге, нормальная форма терпит поражение в битве с развернутой.
Рисовать развернутую форму всегда было проще, она наглядней, так теперь еще и равновесия легче искать.

 

[FMM]

Итак, первое отступление от теории игр. Рассказ будет идти об эпохальной работе Джорджа Акерлофа - "Рынок Лимонов".
Суть работы занимает несколько строчек, но за нее в 1 очередь Акерлоф получил в 2001 году Нобелевскую премию.
Забавна история данной статьи.
3 из 5 ведущих журналов отвергли данную работу, два из них - за тривиальность, а еще один - за некорректность. И только 4 журнал принял ее к публикации.
Итак, в чем же идея.
Лимонами в США называют подержанные автомобили.
Пусть есть рынок автомобилей. На рынке предлагаются автомобили любого качества - от 0 до 1. Будем считать, что 0 - полная рухлядь, 1 - новая машина.
Предположим, что за машину качества р из отрезка [0,1] продавец хочет получить сумму р. А покупатель за машину качества р готов заплатить цену 3/2 р.
Теперь главная идея работы: если покупатель и продавец обладают одинаковой информацией о машине, т.е. знают его качество, то автомобиль качества р будет продан.
Причем участников сделки устроит цена из отрезка [р, 3/2 р].
Но часто на рынке присутствует АСИММЕТРИЯ ИНФОРМАЦИИ. Продавец знает качество автомобиля, а покупатель - нет.
Что же теперь произойдет на рынке. Акерлоф говорит, что при асимметрии информации на таком рынке не будет продана ни одна машина(разве что нулевой цены)
Как же так получается.
Пусть на рынке есть определенная рыночная цена р'. Кто же из продавцов захочет продавать машины по такой цене? Очевидно все продавцы с машинами качества из
[0, р']. А сколько же готов заплатить покупатель? Он понимает, что на цену р' готовы откликнуться все продавцы с машинами качества из [0, р'], поэтому среднее качество машины составит р'/2. Поэтому покупатель будет готов дать 3/2 * р'/2=3/4 р'<р'.
И такая логика будет для любой цены р'. В итоге, рынок полностью схлопнется.

Можно придумать пример попроще. Есть продавец коровы, который уезжает из деревни в город(ему корова уже не столь важна), и покупатель, который наоборот, перебирается в деревню(ему корова нужнее). Продавец готов отдать корову за 80 тугриков.
Коровы в деревне есть 2 типов - хорошие и плохие. За хорошие покупатель готов платить 100 тугриков, за плохую - 50.
У продавца корова хорошая. Но понятно, что владельцы плохих коров тоже попытались бы подать свою корову, как хорошую. В итоге, покупатель готов платить (50+100)/2 = 75 тугриков, что не устроит продавца. И сделка сорвется.

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

Как же дальше стала развиваться экономика. Очень серьезное направление данной науки связано с попытками преодолеть данную неэффективность, а также с исследованием экономических процессов через призму асимметрии информации.

 

[ник69]

FMM
снова отослал тебе решение на равновесие... слушай ты мне своими нуль точка нуль весь моск разорвал

Как же дальше стала развиваться экономика.

Открыв трофейного Конфуция, Достоевский стал листать его наугад. Чем дольше он читал, тем бес­смысленнее казался текст — вернее, в нем все ярче просвечивал тот тонкий мерцающий смысл, которого много в любой телефонной книге. (с) "t"

 

[FMM]

Перенес свой старый пост сюда.

Алгоритм Гейла - Шепли

На мой взгляд, это один из самых красивых результатов в экономике.
Данный алгоритм не только объясняет, почему Бог создал именно 2 пола(мужчину и женщину, но также показывает, у какого из них есть преимущество).

Предположим, что в мире есть одинаковое число мужчин и женщин. Нам надо разбить их на пары.
Так вот, разбиение на пары называется стабильным, если не найдется мужчины и женщины из разных пар, что обоим лучше быть вместе.
Алгоритм Гейла - Шепли наглядно доказывает, что такое разбиение всегда существует. При этом Гейл и Шепли показали, что если полов будет больше 2 или равен 1, то результат верен не будет. Тоже самое можно сказать и про полигамные варианты, гаремы и прочее. Т.е. именно пары являются идеальным варинтом.

Приведу пример, где нельзя придумать стаб. разбиение.
Есть 3 девушки 1, 2 и 3 и 2 комнаты. Девушка 1 хочет жить с девушкой 2, вторая - с третьей, а третья - с первой. Каждая комната вмещает только 2 человек. Очевидно, что как не расселять двушек, они постоянно будут перебегать из комнаты в комнату.

Сам алгоритм Гейла - Шепли очень прост.
Каждый мужчина пишет список из всех женщин в порядке предпочтения. Тоже самое делает и каждая женщина. На первом шаге каждый мужчина с букетом цветов идет к лучшей кандидатке. Если к одной женщине пришли несколько человек, то она всем, кроме лучшего швыряет букет в лицо, а лучшему говорит, что подумает. И так далее. Те, кто в первый раз получил букет в лицо идет к следующей по списку, а те кто не был послан, идут снова к данной женщине. В итоге, все будут разбиты на стабильные пары.
При этом необязательно условие, что мужчин и женщин одинаковое число. Тогда, из тех, кого больше, останется нескоторе число в одиночестве.
Какому же полу лучше всего. Выясняется, что если поменять местами мужчин и женщин, то все женщины получат лучший расклад(не худший), а мужчины - наоборот. Поэтому, нам мужчинам очень повезло, что именно мы дарим цветы, а не нам.