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

ник69

Активный участник
Сообщения
5.763
Адрес
г. Донецк
Жизнь хитра! Когда у меня на руках все карты - она внезапно решает играть в шахматы…
(с) :-D

Уважаемый FMM я открыл тему, сразу вопрос Вы также как основатель теории игр случайно не "Уже в 6 лет он мог разделить в уме два восьмизначных числа и беседовать с отцом на древнегреческом. Янош всегда интересовался математикой, природой чисел и логикой окружающего мира." ??? :-D
 

FMM

Активный участник
Сообщения
1.536
Адрес
Москва
ник69 написал(а):
Жизнь хитра! Когда у меня на руках все карты - она внезапно решает играть в шахматы…
(с) :-D

Уважаемый FMM я открыл тему, сразу вопрос Вы также как основатель теории игр случайно не "Уже в 6 лет он мог разделить в уме два восьмизначных числа и беседовать с отцом на древнегреческом. Янош всегда интересовался математикой, природой чисел и логикой окружающего мира." ??? :-D
А что такое "разделить в уме два восьмизначных числа"?
Не надо меня сравнивать с великим Яношем. Неприлично как-то :-D
Действительно, наука, указанная в топике "официально" стартует со знаменитой работы Фон Неймана и Моргенштерна.
Сегодня постараюсь начать. :-D
 

mtu

Активный участник
Сообщения
519
Адрес
СПб
Поиск оптимальных стратегий ? Что ж ... интересно. Вам не знакома случайно госпожа Яновская из СПб ?
 

ник69

Активный участник
Сообщения
5.763
Адрес
г. Донецк
FMM написал(а):
а вот пару авторов глав этой книги знаю.
Это издевательство .... снова на аглиЦком ...
Случаем не автора этой главы???

12. Алгоритмический подход к поиску равновесия в моделях фиксированного обменного бюджет

И случаем одного из авторов глав , не слишком ли близко знаете ???
wink3.gif
 

FMM

Активный участник
Сообщения
1.536
Адрес
Москва
Слушайте, а кто-нибудь знает, как формулы вставлять, которые в Word написаны?
Ну, или как-нибудь по другому.. А то совсем без формул тяжело. Хотя буду стараться избегать математики.
 

aviator

Активный участник
Сообщения
1.069
FMM
Микрософт ейкьюейшн
Ворд - вставка - обьект - Vicrosoft equation 3/0
или вставить формулу
 

ник69

Активный участник
Сообщения
5.763
Адрес
г. Донецк
FMM написал(а):
Не надо меня сравнивать с великим Яношем. Неприлично как-то
Да я не сравниваю... Я интересуюсь , какие способности должны быть у изучающего теорию игр... :-D
FMM написал(а):
А что такое "разделить в уме два восьмизначных числа"?
Ну наверное в одном полушарии одно восьмизначное а в другом полушарии другое :-D параллельными так сказать потоками :-D
Это вообще вопрос к вики где пишут про "самый быстрый ум века" :-D
 

FMM

Активный участник
Сообщения
1.536
Адрес
Москва
aviator написал(а):
FMM
Микрософт ейкьюейшн
Ворд - вставка - обьект - Vicrosoft equation 3/0
или вставить формулу
Не понял
Формулы из Ворда сюда не переносятся. Я ее выделяю, а когда захожу в окошко, где пишу сообщение, то комп ничего не видит, что вставить можно.
 

aviator

Активный участник
Сообщения
1.069
FMM
через принтскрин и залить на фаило обменник
 

FMM

Активный участник
Сообщения
1.536
Адрес
Москва
ник69 написал(а):
Я интересуюсь , какие способности должны быть у изучающего теорию игр... :-D
желание
живой ум :-D
знание основных математических операций(сложение, вычитание,..) :-D

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

aviator написал(а):
FMM
через принтскрин и залить на фаило обменник
Ужас какой. :(
Ладно, я что-нибудь придумаю.
 

mtu

Активный участник
Сообщения
519
Адрес
СПб
Можно внести ложку дегдя ?
Не покупайтесь на название этого раздела математики,
несмотря на интригующее название это в первую очередь МАТЕМАТИКА, сухая и не романтичная :)


Что нужно знать для изучения ? Операции сравнения на больше/меньше, выбирать максимальное и минимальное число из нескольких :)
 

Экономист

Активный участник
Сообщения
9.171
Адрес
РФ, Москва
mtu написал(а):
несмотря на интригующее название это в первую очередь МАТЕМАТИКА, сухая и не романтичная
Да. Мне вот, когда я услышал это словосочетание в первый раз, фантазия живо нарисовала что-то вроде карточного стола, рулетки или, на худой конец, игрового автомата. Короче кучу денег. :grin: А когда понял, что это такое, чуть не свихнулся. :)
 

aviator

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

mtu

Активный участник
Сообщения
519
Адрес
СПб
Вот неплохой пример задачи в теории игр(задача простая, честно скопированная из Википедии)



[править] Классическая дилемма заключённого
Во всех судебных системах кара за бандитизм (совершение преступлений в составе организованной группы) намного тяжелее, чем за те же преступления, совершённые в одиночку (отсюда альтернативное название — «дилемма бандита»).

Классическая формулировка дилеммы заключённого такова:

Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок (10 лет). Если оба молчат, дело проходит по другой статье, и они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?

Игру можно представить в виде следующей таблицы:

Заключённый Б хранит молчание Заключённый Б даёт показания
Заключённый А хранит молчание Оба получают полгода. А получает 10 лет,
Б освобождается
Заключённый А даёт показания А освобождается,
Б получает 10 лет тюрьмы Оба получают 2 года тюрьмы
«Дилемма заключённого» в нормальной форме.

Дилемма появляется, если предположить, что оба заботятся только о минимизации собственного срока заключения.

Представим рассуждения одного из заключённых. Если партнёр молчит, то лучше его предать и выйти на свободу (иначе — полгода тюрьмы). Если партнёр свидетельствует, то лучше тоже свидетельствовать против него, чтобы получить 2 года (иначе — 10 лет). Стратегия «свидетельствовать» строго доминирует над стратегией «молчать». Аналогично другой заключённый приходит к тому же выводу.

С точки зрения группы (этих двух заключённых) лучше всего сотрудничать друг с другом, хранить молчание и получить по полгода, так как это уменьшит суммарный срок заключения. Любое другое решение будет менее выгодным. Это очень наглядно демонстрирует, что в игре с ненулевой суммой Парето-оптимум может быть противоположным равновесию Нэша.
 

FMM

Активный участник
Сообщения
1.536
Адрес
Москва
ник69 написал(а):
Это издевательство .... снова на аглиЦком ...
Случаем не автора этой главы???

12. Алгоритмический подход к поиску равновесия в моделях фиксированного обменного бюджет

И случаем одного из авторов глав , не слишком ли близко знаете ???
wink3.gif

Так я ее к чтению не предлагаю. Я эту книгу и не читал.
И смысла особого в данной книге не вижу. Для кого она написана? Для патриотического воспитания? Тогда можно было и на русском писать. Для Запада - а оно им надо?

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

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

mtu написал(а):
Можно внести ложку дегдя ?
Не покупайтесь на название этого раздела математики,
несмотря на интригующее название это в первую очередь МАТЕМАТИКА, сухая и не романтичная :)
Что нужно знать для изучения ? Операции сравнения на больше/меньше, выбирать максимальное и минимальное число из нескольких :)
Можно ответить на ложку дегтя?
1)Несмотря на всевозможные математические расчеты, теория игр пестрит красивейшими результатами и решениями, где математика на уровне детского сада. Глупо отрицать, что в теории игр нет сложной математики. Есть такие разделы. Но такова далеко не вся теория игр.
2)Давайте придерживаться мирового подхода к классификации теории игр.
Все-таки теория игр - уже раздел экономики, а не математики.
То, что теория игр формализована не делает ее разделом математики. Просто таково развитие самой экономики. Спасибо Самуэльсону и Ко.
Достаточно симптоматично, что все специалисты по теории игр в мире работают именно на экономических, а не математических факультетах. То, что у нас по-другому - наша проблема.

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

mtu написал(а):
Классическая дилемма заключённого
Отличная вещь - Википедия. Там много интересного написано. Хотя для изучения теории игр недостаточно :-D
Пример действительно классический. Ник69 - можете почитать, хотя некоторые термины лучше объяснить. Поэтому я постараюсь вначале дать базовые понятия, а потом уже переходить к играм.
Кстати, mtu, дилемма о заключенном в итоге была разрешена в определенном смысле. Т.е. Парето-оптимум в итоге оказывается равновесием Нэша..

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

aviator написал(а):
На самом деле ничего сложного в ней нет,главное поянть оптимальную стратегию, максимальный выигрыш и минимальный проигрыш ,помоему так звучало .. давно был 3 курс ....
В теории игр много очень и очень сложного.

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

Итак, поехали.
Прежде, чем переходить к интересным задачам и примерам, надо дать некоторые понятия, котрые могут понадобиться не сразу, но очень важны.
1)Предпочтение(будет знак >_ хотя на самом деле должно быть "больше, либо равно", причем нижняя палочка волнистая)
Интуитивно понятно, что это такое. Человек может любить груши, больше чем яблоки.
Это значит, что груша>_яблоко
При этом вполне может быть, что груша+яблоко>_2 груши - хочется разнообразия

Экономика изучает в 1 очередь рациональные предпочтения, которые удовлетворяют 2 условиям
Во-первых, для любых объектов 1 и 2 можно сказать, хотя бы
1>_2 или 2>_1 (понятие полноты)
Второе - транзитивность.
Если 1>_2, 2>_3, то 1>_3

Ну и еще одна очевидная ремарка.
Если 1>_2 и 2>_1, то тогда они эквивалентны с точки зрения выбора.

2)Далее, экономисты решили ввести функцию полезности - u(.). Значение функции - число. Аргументом является объект
Данная функция тесно связана с предпочтением. Если для человека груша>_яблоко, то u(груша)>=u(яблоко).
Т.е. теперь экономисты могли выражать все предпочтения через числа. Например, яблоко приносит полезность 1, а груша - полезность 2.
Естественно, функция может зависеть от нескольких аргументов.
Например 1 аргумент - число груш, а второй - число яблок. Тогда несложно придумать такую функцию, что u(1 груша, 1 яблоко)>u(2 груши, 0 яблоков)>u(0 груш, 2 яблока)
В экономике, когда рассматривают полезность от работы, то в качестве основных аргументов используются зарплата и отдых - u(зарплата, отдых)

Рекламная пауза, эти понятия слишком базовые, чтобы их не ввести.

Следующий пункт остановки - Парето-оптимум.
Строго говоря парето-оптимум - такое состояние системы, при котором нельзя улучшить "жизнь" одним элементам, не ухудшив ее другим.
Например, есть Вася и Петя. Они пошли в поход, взяв 4 бутерброда - два с сыром, два с ветчиной. Вася обожает бутерброды с сыром, но не прочь и с ветчиной съесть, а Петя - наоборот.
Если каждому дать по бутерброду обоих типов, то это не будет Парето-оптимумом.
Ведь, если Васе отдать оба с сыром, а Пете с ветчиной - оба выиграют. Данное состояние будет уже Парето-оптимальным. Можно еще улучшить позицию Васи, но тока отняв один из оставшихся бутеров Пети, тем самым ухудшив его позицию.

Полезно представить все это в полезностях.
Для Васи полезность бутера с сыром - 10, с ветчиной - 3. Для Пети - наоборот. Тогда при 1 дележке полезность каждого - 13, а при второй - 20.


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

Экономист написал(а):
Да. Мне вот, когда я услышал это словосочетание в первый раз, фантазия живо нарисовала что-то вроде карточного стола, рулетки или, на худой конец, игрового автомата. Короче кучу денег. :grin: А когда понял, что это такое, чуть не свихнулся. :)
Что поделаешь.. Красивых задач там полно. Просто стандартные курсы преподают самую базовую и сухую технику. Вроде поиска равновесий в смешанных стратегиях.
а по поводу сумасшествия - есть доля истины. :-D
По слухам каждый пятый, кто профессионально занимается темой mechanism design сходит с ума. Как русская рулетка. :-D
 

ник69

Активный участник
Сообщения
5.763
Адрес
г. Донецк
FMM написал(а):
Ник69 - можете почитать,
:-D Прочитал с нескрываемым интересом.
FMM написал(а):
Если хотите найти , с кем я пил, ищите в других научных заведениях.
Можно ли трактовать Ваши слова так что без бутылки сие знание не осилишь? :-D
FMM написал(а):
Кстати, mtu, дилемма о заключенном в итоге была разрешена в определенном смысле. Т.е. Парето-оптимум в итоге оказывается равновесием Нэша..
С ума сойти , как интересно :-D

FMM написал(а):
В теории игр много очень и очень сложного.
студент написал(а):
Счастливый человек, ты хоть понял! А я - так нет...
Ну , вот ... а так все хорошо начиналось.
FMM написал(а):
Прочитал и даже кажись немного уяснил :-D
FMM написал(а):
Можно ответить на ложку дегтя?
Даже нужно!!!! :-D
FMM написал(а):
По слухам каждый пятый, сходит с ума. Как русская рулетка.
Не хило ответили на ложку ... :-D
Но я готов рискнуть :-D терять терять то все равно нечего :-D (эк тонко то! :-D )

З.Ы. никто не подскажет фильм "Игры разума" основывается на настоящих событиях??
 

FMM

Активный участник
Сообщения
1.536
Адрес
Москва
ник69 написал(а):
Можно ли трактовать Ваши слова так что без бутылки сие знание не осилишь?
Нет, не надо. :-D

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

ник69 написал(а):
Не хило ответили на ложку ... :-D
Но я готов рискнуть :-D терять терять то все равно нечего :-D (эк тонко то! :-D )
Ну, mechanism design - это еще не скоро. Пока займемся более простыми вещами.
Тока я продолжу завтра - сегодня дел полно.

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

ник69 написал(а):
никто не подскажет фильм "Игры разума" основывается на настоящих событиях??
Подскажем. Все более менее верно. Не знаю насчет работ на секретную службу, но шизофрения действительно была. И что еще более удивительно, что Нэш вылечился и сейчас совершенно адекватный человек.
Ник69, если помните момент, когда Нэш продул игру в го и смахнул доску, то этот момент также был в реальности. Причем продул он Джону Милнору, который впоследствии стал великим математиком. Впрочем, как и Нэш.
 

FMM

Активный участник
Сообщения
1.536
Адрес
Москва
Итак, переходим к самой игре.
В каждой игре присутствуют 3 компоненты
1) Игроки
2) Стратегии игроков
3) Выигрыши, которые реализуются после того, как выбраны стратегии
Например, в качестве игроков можно взять политические партии.
Стратегиями будут политические платформы, которые они предлагают.
Для каждого набора стратегий будет соответствующий итог выборов(в качестве выигрыша можно взять процент избирателей, проголосовавших за данную партию)

Если на любом моменте возникают вопросы, то я постараюсь на любой из них ответить
В чем же основная проблема. Конечно, каждый участник пытается максимизировать свой выигрыш. Но выигрыш игрока зависит не только от его стратегии, но и от выбора остальных. Поэтому игрок всегда должен держать в голове возможные действия остальных игроков.
Т.к. есть проблемы с размещением рисунков, сошлется на Википедию
http://ru.wikipedia.org/wiki/Теория_игр
Здесь надо посмотреть абзацы Нормальная форма и Экстенсивная форма(чаще называется развернутой формой игры)
В играх из Вики 2 игрока, у каждого по 2 стратегии.
С нормальной формой все просто.
Слева - 1 игрок, сверху - 2 игрок.
Далее по строчкам будут идти стратегии 1 игрока, а по столбикам - стратегии 2 игрока.
Пересечния строк и столбцов дают выигрыши игроков.
Развернутая форма выглядит поинтересней.(понятия графа, дерева можно прочитать в той же Вики)
Берется 1 игрок, он будет вершиной дерева. Из него выходит 2 стрелки(графа). Они обозначают стратегии игрока. Далее, для каждой стратегии 1 игрока у 2 игрока есть тоже по две стратегии. Если игроки делают выбор одновременно, то не важно как рисовать дерево игры - можно начинать как с 1 игрока, так и со второго. Но во многих играх действия игроков последовательны. В таких случаях дерево рисуется в строго в соответсвии с последовательностью ходов игроков.
В качестве упражнения можно перерисовать пример с нормальной формой в развернутую и наоборот, а также нарисовать дерево, начиная с ходов 2 игрока.
 
Сверху