Как стать автором
Обновить

Комментарии 26

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

Если интересно могу как нибудь написать статью по теории конфликтных равновесий (это развитие теории игр исправляющее недочёты и спорные ситуации) с алгоритмом расчёта на C#.
Из реальных примеров — покер. Использовать равновесие по Нэшу для поиска оптимальной стратегии бота — очень модно.
Меня интересовали примеры из экономики — как правильно составлять стратегии и рассчитывать выигрыши.
Интересно где это реально применяется в бизнесе.
Тут все намного глубже, чем описанный пример в статье. Если в двух словах, то в пример можно привести выпуск каталога товаров с ценами двух фирм бытовой техники, и риски\прибыль в случае выпуска позже и раньше конкурента. Пример имел место быть в середине 2000-х, когда Эльдорадо строил себе рекламную кампанию именно на более низких ценах, чем у конкурентов.
А по правильности составления стратегий и т.п. попытаюсь ответить в одной из следующих статей
Продолжайте, интересная тема.

Кстати, фильм называется «Игры разума», пример теории игр показан отлично.
Мне, из реальных примеров рассматриваемых с точки зрения теории игр, нравятся вот эти:
Материальная демотивация,
Теоретико-игровое обоснование кидалова,
Измерение честности деньгами
Среди аудитории Хабра его не нашел, но это Максим Дорофеев, очень рекомендую его остальные слайдкасты посмотреть.
НЛО прилетело и опубликовало эту надпись здесь
Хорошая статья, но если было бы что-то не из википедии, то стала бы еще лучше.
Из вики, тут, собственно, история развития, не самому же мне ее придумывать. А все остальное — общеизвестные факты, которые я попытался донести до сообщества понятным мне языком.
НЛО прилетело и опубликовало эту надпись здесь
Вот эта мне больше понравилась — www.youtube.com/watch?v=S0qjK3TWZE8
Правда условия в игре конечно другие.
Если бы заключенные при обоюдном предательстве получали пожизненное, то больше похоже было бы…
Мне кажется, применять такие математические методы «в лоб» очень опасно, поскольку слишком много зависит от психологии конкретных участников.
Например, читал про такое исследование:
Вы — мэр города, в котором началась эпидемия. Все люди заражены. Есть 2 вакцины, А и В. Обе дадут эффект через некоторое время, так что выбрать вакцину для массовых прививок надо сейчас. Вакцина А гарантированно спасёт 1/3 населения, остальные 2/3 погибнут. Вакцина В с вероятностью 1/3 спасёт всех, с вероятностью 2/3 — никого. Какую выбрать?
С математической точки зрения, выбор равный. С человеческой — нет.
Во-первых, люди более склонны бояться потерять, чем стремиться выйграть (поэтому заключённый наверняка выберет «сдать подельника», ведь «надёжнее» получить лишние полтора года, чем рискнуть аж десяткой).
Во-вторых, ответ сильно зависит даже от того, как задать вопрос. В том же исследовании, при вопросе «спасёте ли вы гарантированно 1/3 города» и «возьмёте ли вы на себя верную смерть 2/3 города», ответы были, как правило, противоположные. А ведь предлагалось одно и то же (вакцина А).
Прием с формулированием вопроса в референдумах используют. Когда большинство опрашиваемых некомпетентны в решаемой задаче, то результат опроса полностью зависит от формулировки вопроса.
Здравствуйте! Начну с того, что порадовало. Порадовало наличие на Хабре статьи на такую интересную для меня тему, спасибо Вам за это. Но есть ряд замечаний по поводу изложенного материала. Первое — это определение равновесия по Нэшу, это хорошо, что Вы пытаетесь дать материал как можно проще, но не надо отходить из-за этого от истины:
«методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия «равновесие по Нэшу». По его теории, стороны должны использовать оптимальную стратегию, что приводит к созданию устойчивого равновесия» — мне не понравился этот отрывок. Во-первых, Вы употребили термины «выигрывать» и «проигрывать», в то время как в большинстве задач нет понятия выигравший, проигравший, есть только различные исходы и выигрыши, слова «выигрывать», «проигрывать» при мне запутывали очень многих людей именно при поиске равновесия по Нэшу. Во-вторых, само содержание этого отрывка никак не относится к определению равновесия. В-третьих слово «оптимальная» тоже лучше не использовать, сразу же возникает вопрос «оптимальная по чему?». Дальше Вы продолжаете определять равновесие: «Игрокам выгодно сохранять это равновесие, так как любое изменение ухудшит их положение» — тут допущена ошибка, правильно: «Игрокам выгодно сохранять это равновесие, так как любое изменение не улучшит их положение», не говоря уже о том, что надо добавлять, что стратегии остальных игроков должны быть неизменны, иначе это неправда. Второе — это определение кооперативных игр, Ваше определение не соответствует ни тому, что говорит Википедия, ни тому, которое знаю я, причем достаточно сильно. И в-третьих было бы хорошо упомянуть Баесовсекие игры, когда описывается проблема с разной информацией у игроков. В четвертых, но это уже мелочи, основная заслуга Нэша была не в том, что он предложил «равновесие по Нэшу», оно было известно задолго до него, а то что он доказал, что в смешанных стратегиях равновесие всегда существует.
Все же теория игр — раздел математики, методы которого применяются не только в экономике. Иначе и теорию вероятностей следовало бы считать разделом игорного бизнеса :)
Забавный пример применения теории игр есть в фэнтезийной книжке Энтони Пирса «Бравый голем»
Много текста
– Смысл того, что я сейчас вам всем продемонстрирую, – начал Гранди, – заключается в наборе необходимого количества баллов. Баллы могут быть самыми различными – все зависит от комбинации решений, которые принимаются участниками игры. К примеру, предположим, что каждый участник свидетельствует против своего товарища по игре. В этом случае каждому участнику можно присудить по одному очку!
– Одно очко! – сказала Морская Ведьма, проявляя к игре неожиданный интерес. Очевидно, колдунья хотела удостовериться в том, что у голема нет никаких шансов, чтобы демон Ксант остался им доволен.
– А теперь давайте предположим, что каждый из участников игры не свидетельствует против своего товарища! – продолжал Гранди. – В этом случае каждому можно присудить по три балла. Я хочу особенно отметить, что покуда все участники действуют одинаково, то им присуждается одинаковое количество баллов. Ни у кого нет никаких преимуществ перед другим.
– Три очка! – сказала вторая ведьма.
– Но вот теперь мы вправе предложить, что один из игроков начал давать показания против второго, а второй все равно молчит! – сказал Гранди. – В таком случае тот, кто эти показания дает, получает сразу пять очков, а тот, который молчит, не получает ни одного очка!
– Ага! – в один голос воскликнули обе ведьмы, хищно облизывая губы. Было видно, что обе они явно собирались получить по пять очков.
– Я все время терял очки! – воскликнул демон. – Но ведь ты пока только обрисовал ситуацию, а способа ее разрешения еще не представил! Так в чем заключается твоя стратегия? Не надо тянуть время!
– Погоди, сейчас я все объясню! – воскликнул Гранди. – Каждый из нас четверых – нас тут двое големов и две ведьмы – будет сражаться против своих противников. Конечно же, ведьмы постараются никому ни в чем не уступить…
– Конечно! – воскликнули снова обе ведьмы в унисон. Они отлично понимали голема с полуслова!
– А второй голем будет следовать моей тактике, – продолжал Гранди невозмутимо. Он посмотрел на своего двойника. – Ты, конечно, в курсе?
– Да, конечно! Я ведь твоя копия! Я прекрасно все понимаю, что ты думаешь!
– Вот и отлично! В таком случае, давайте-ка сделаем первый ход, чтобы демон смог сам все увидеть. В каждом поединке будет несколько раундов, чтобы вся стратегия смогла проявиться до конца и произвела впечатление целостной системы. Пожалуй, мне следует начать.

– Теперь каждый из нас должен наносить отметки на своих листках бумаги! – обратился голем к ведьме. – Сначала следует нарисовать улыбающееся лицо. Это будет означать, что мы не будем давать показания на товарища по заключению. Можно также нарисовать насупленное лицо, которое означает, что мы думаем только о себе и нужные показания на своего товарища даем. Мы оба сознаем, что лучше было бы, если бы никто не оказался тем самым насупленным лицом, но ведь, с другой стороны, насупленное лицо получает определенные преимущества перед улыбающимся! Но суть заключается в том, что каждый из нас не знает, что выберет другой! Не будем знать до тех пор, покуда партнер по игре не откроет своего рисунка!
– Начинай ты, сволочь! – выругалась ведьма. Она, как всегда, не могла обойтись без бранных эпитетов!
– Готово! – воскликнул Гранди, нарисовав большое улыбающееся лицо на своем листочке бумаги таким образом, чтобы ведьма не смогла увидеть, что он изобразил там. Ведьма сделала свой ход, тоже изобразив лицо. Надо думать, она непременно изобразила недобрую физиономию!
– Ну, а теперь нам остается только показать друг другу наши рисунки, – объявил Гранди. Обернувшись назад, он открыл рисунок публике и показал его во все стороны, чтобы рисунок смогли увидеть все. Что-то недовольно ворча, то же самое сделала и Морская Ведьма.
Как Гранди и рассчитывал, с рисунка колдуньи смотрело злое, недовольное лицо.
– Теперь вы, уважаемые зрители, – сказал Гранди торжественно, – видите, что ведьма предпочла давать на меня показания. Я не собираюсь этого делать. Таким образом, Морская Ведьма набирает пять очков. А я, соответственно, не получаю ни одного балла. И тут…
По рядам зрителей снова прокатился легкий шумок. Все явно сочувствовали голему и страстно желали, чтобы Морская Ведьма проиграла.
Но ведь игра только-только началась! Если только его стратегия была верной…
– Теперь мы можем перейти ко второму раунду! – объявил Гранди торжественно. – Мы снова должны повторить ходы. Каждый рисует лицо, которое ему ближе!
Так и сделали. Гранди изображал теперь хмурое, недовольное лицо.
Как только игроки показали свои рисунки, публика увидела, что теперь оба они изобразили злые лица.
– По два очка каждому! – сказал Гранди.
– Семь два в мою пользу! – заорала ведьма радостно. – Ты никуда отсюда не выберешься, мерзавец!
– Начинаем снова! – воскликнул Гранди. Они сделали по очередному рисунку и показали их публике. Снова те же самые злые лица.
– Каждый из нас повторил предыдущий ход, повел себя эгоистично, а потому, как мне кажется, лучше никому не присуждать очков! – заявил голем.
– Но я все равно веду в игре! – сказала ведьма, радостно потирая руки.
– Ладно, не шуми! – сказал Гранди. – Игра ведь не закончилась. Посмотрим, что будет! Итак, уважаемая публика, мы начинаем четвертый по счету раунд!
Игроки снова сделали рисунки, показав публике то, что они изобразили на своих листках. Оба листка снова явили зрителям те же злые физиономии.
– Восемь – три! – закричала ведьма, заливаясь злобным смехом. – Своей дурацкой стратегией ты выкопал себе могилу, голем!
– Пятый раунд! – закричал Гранди. Повторилось то же самое, что и в прежние раунды, – снова злые лица, только счет изменился – он стал девять – четыре в пользу колдуньи.
– Теперь последний, шестой раунд! – возвестил Гранди. Его предварительные расчеты показывали, что именно этот раунд должен стать судьбоносным. Теперь теория должна была подтвердиться либо быть опровергнута практикой.
Несколько быстрых и нервных движений карандаша по бумаге – и оба рисунка предстали перед глазами публики. Снова два лица, теперь даже с оскаленными зубами!
– Десять – пять в мою пользу! Моя игра! Я победила! – загоготала Морская Ведьма.

– Ты действительно выиграла, – согласился Гранди мрачно. Аудитория зловеще молчала.
Демон шевельнул было губами, чтобы что-то сказать.

– Но наше состязание еще не закончено! – крикнул звонко Гранди. – Это ведь была только первая часть игры.
– Да вам целую вечность подавай! – заворчал демон Ксант недовольно.
– Это верно! – сказал Гранди спокойно. – Но ведь один тур ничего не решает, только методичность указывает на лучший результат.
Теперь голем подошел к другой ведьме.
– Я хотел бы сыграть этот тур с другим противником! – объявил он. – Каждый из нас будет изображать лица, как это было в предыдущий раз, потом будет демонстрировать нарисованное публике!
Так они и сделали. Результат был таким же, как и в прошлый раз – Гранди нарисовал улыбающуюся рожицу, а ведьма – так вообще череп. Она сразу набрала преимущество в целых пять баллов, оставив Гранди позади.
Оставшиеся пять раундов окончились с теми результатами, которых и можно было ожидать. Снова счет стал десять – пять в пользу Морской Ведьмы.
– Голем, мне очень нравится твоя стратегия! – хохотала колдунья.
– Итак, вы просмотрели два тура игры, уважаемые зрители! – воскликнул Гранди. – Я, таким образом, набрал десять очков, а мои соперницы – двадцать!
Публика, которая тоже вела подсчет очков, скорбно закивала головами. Их подсчет совпал с подсчетами голема. Только облако по имени Фракто казалось весьма довольным, хотя, конечно, ведьме оно тоже не симпатизировало.
Но Рапунцелия одобряюще улыбнулась голему – она продолжала верить в него. Она, возможно, осталась единственной, кто верил ему теперь. Гранди надеялся, что он оправдает это безграничное доверие.
Теперь Гранди подошел к своему третьему сопернику – своему двойнику. Он должен был стать его последним противником. Быстро чиркнув карандашами по бумаге, големы показали листочки публике. Все увидели две смеющихся рожицы.
– Заметьте, дорогие зрители, каждый из нас предпочел быть добрым сокамерником! – воскликнул Гранди. – А посему никто из нас не получил в этой игре необходимого преимущества перед соперником. Таким образом, мы оба получаем по три балла и приступаем к следующему раунду!
Второй раунд начался. Результат был тот же, что и в предыдущий раз. Затем оставшиеся раунды. И в каждый раунд оба противника набирали опять по три балла! Это было просто невероятно, но публика была готова подтвердить все происходящее.

Наконец и этот тур подошел к концу, и Гранди, быстро водя своим карандашиком по бумаге, стал подсчитывать результат. Наконец он объявил торжественно:
– Восемнадцать на восемнадцать! В общей сложности я набрал двадцать восемь очков, а мои соперники набрали тридцать восемь!
– Значит, ты проиграл, – возвестила Морская Ведьма радостно. – Победителем станет, таким образом, кто-то из нас!
– Возможно! – спокойно отозвался Гранди. Теперь наступал еще один важный момент. Если все пройдет так, как им и было задумано…
– Нужно довести дело до конца! – воскликнул второй голем. – Мне ведь тоже еще нужно сразиться с двумя Морскими Ведьмами! Игра еще не закончена!
– Да, конечно, давай! – сказал Гранди. – Но только руководствуйся стратегией!
– Да, конечно! – заверил его двойник.
Этот голем подошел к одной из ведьм, и тур начался. Завершился он с тем же результатом, с которым из подобного раунда вышел сам Гранди – счет был десять-пять в пользу колдуньи. Ведьма прямо-таки сияла от невыразимой радости, а публика угрюмо замолчала. Демон Ксант выглядел несколько уставшим, что было не слишком добрым предзнаменованием.
Теперь пришло время заключительного раунда – одна ведьма должна была сражаться против второй. Каждая имела в активе по двадцать очков, которые она смогла получить, сражаясь с големами.
– А теперь, если ты позволишь набрать мне хотя бы несколько лишних очков… – заговорщицки прошептала Морская Ведьма своему двойнику.
Гранди старался сохранить спокойствие хотя бы внешне, хотя в душе его бушевал ураган противоречивых чувств. Его удача сейчас зависела от того, насколько верно он предугадал возможное поведение обеих ведьм – ведь характер их был, в сущности, одним и тем же!
Сейчас наступал самый, пожалуй, критический момент. Но если он ошибся!
– С какой это стати я должна тебе уступать! – прокаркала вторая ведьма первой. – Я сама хочу набрать больше очков и выбраться отсюда!
– Ну, если ты так нахально ведешь себя, – завопила претендентка, – то я тебя сейчас отделаю так, что ты больше не будешь похожа на меня!
Ведьмы, одарив друг друга ненавидящими взглядами, начертили свои рисунки и показали их публике. Конечно же, ничего другого, кроме двух черепов, там оказаться просто не могло! Каждая набрала по одному очку.
Ведьмы, осыпая друг друга проклятьями, приступили ко второму раунду. Результат опять тот же самый – снова два коряво нарисованных черепа. Ведьмы, таким образом, набрали еще по одному очку. Публика старательно все фиксировала.
Так продолжалось и в дальнейшем. Когда тур закончился, усталые ведьмы обнаружили, что каждая из них набрала по шесть очков. Снова ничья!
– Теперь давайте подсчитаем получившиеся результаты и все сравним! – торжествующе сказал Гранди. – Каждая из ведьм набрала по двадцать шесть очков, а големы набрали по двадцать восемь баллов. Итак, что мы имеем? А имеем мы тот результат, что големы имеют большее количество очков!
По рядам зрителей прокатился вздох удивления. Взволнованные зрители стали писать на своих листочках столбики цифр, проверяя правильность подсчета. Многие за это время просто не считали количество набранных баллов, считая, что результат игры им уже известен. Обе ведьмы стали рычать от негодования, непонятно, кого именно обвиняя в происшедшем. Глаза демона Ксанта вновь загорелись настороженным огнем. Его доверие оправдалось!
– Я прошу вас, уважаемая публика, обратить внимание на тот факт, – поднял руку Гранди, требуя от зрителей успокоиться, – что ни один из големов не выиграл ни единого раунда. Но окончательная победа все-таки будет за одним из нас, из големов. Результаты будут более красноречивыми, если состязание продолжится и дальше! Я хочу сказать, дорогие мои зрители, что в вечном поединке моя стратегия будет неизменно оказываться выигрышной!
Демон Ксант с интересом прислушивался к тому, что говорил Гранди. Наконец он, испуская клубы пара, открыл рот:
– А в чем конкретно заключается твоя стратегия?
– Я называю ее «Быть твердым, но честным»! – пояснил Гранди. – Я начинаю игру честно, но затем начинаю проигрывать, потому что мне попадаются очень специфические партнеры. Поэтому в первом раунде, когда оказывается, что Морская Ведьма начинает давать против меня показания, я автоматически остаюсь проигравшим и во втором раунде – и так продолжается до конца. Результат может быть другим, ежели ведьма переменит свою тактику ведения игры. Но поскольку ей такое даже в голову прийти не может, мы продолжали играть по предыдущему шаблону. Когда я начал играть со своим двойником, то он хорошо отнесся ко мне, а я хорошо относился к нему в следующем раунде игры. Поэтому игра у нас пошла тоже по-другому и несколько однообразно, поскольку мы не хотели изменять тактику…
– Но ведь вы не выиграли ни единого тура! – удивленно возразил демон.
– Да, а эти ведьмы не проиграли ни одного тура! – подтвердил Гранди. – Но ведь победа не автоматически достается тому, за кем остались туры. Победа достается тому, кто набрал большее количество баллов, а это совсем другое дело! Мне удалось набрать больше очков, когда мы играли вместе с моим двойником, чем когда я играл с ведьмами. Их эгоистическое отношение принесло им сиюминутную победу, но в плане более долгосрочном оказалось, что именно из-за этого обе они проиграли игру целиком. Часто случается и такое!
Я вот не совсем понял смысл вот это фразы «превращая пешку в ферзя игрок А увеличивает общую сумму своих фигур». Может быть шашки имелись ввиду?
Фигуры в шахматах имеют «цену», характеризующую общую полезность фигуры. Пешка 1, конь и слон 3, ладья 5, ферзь 9.
То есть в сферической партии в вакууме отдать коня за 2 пешек — проигрыш материала, а за 4 — выйгрыш.
> выйгрыш

А, так вот откуда берется «андройд» :-) Извините, не удежался
Подскажите пожалуйста что-нибудь стоящее для почитать на эту тему.
Можете поискать публикации Е.С. Вентцель или книги Оуэна
Полезно посмотреть фильм BBC «Западня: что сталось с мечтой о свободе?» В первой серии берут интервью у Нэша. Его равновесие не предполагает наличия альтруизма у людей. Это все идеи какого-то жутковатого бесчеловечного общества.
Таким образом, если каждый игрок выбирает, что лучше для него, оба сдадут друг друга, и получат два года, что не является идеальной ситуацией для обоих. Если бы каждый думал об общем благе, они бы получили всего по пол года.

Но при этом если сдать подельника, а он будет молчать — то тебя вообще отпустят. С другой стороны, если ты молчишь, а твой подельник тебя сдаст — ты получишь 10 лет.
Поскольку игра некооперативная и параллельная — то оптимальной стратегией с точки зрения каждого из участников все же является «предать». Равновесие по Нэшу, однако.
Вариант «молчать» может иметь смысл только в случае не одного, а нескольких раундов (как это несколькими постами выше DanXai показал), т.е. — для профессиональных уголовников:).
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.