Что такое алгоритмическая теория игр? Объяснение с примерами

В 1999 году, когда Нисан и Ронен представили свои идеи в статье, мир увидел новую концепцию проектирования алгоритмических механизмов. Он пытается отрицать «Цену анархии», где личный интерес всегда приводит к деградации системы.

Их статья доказала, что несколько эгоистичных сторон могут создать производственную систему в состоянии равновесия. Таким образом, вместо того, чтобы смотреть на деградирующую экономику, мы будем смотреть на социальное обеспечение и максимизацию доходов.

Алгоритмическая теория игр (AGT) основана на понимании разработки алгоритмических механизмов (AMD) .

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

Прежде чем мы рассмотрим, как AGT работает в стратегической среде, давайте посмотрим, как работает теория игр!

Давайте разберемся в теории игр на примере

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

Идея расчета следующего шага разумных, рациональных граждан одновременно захватывающая и пугающая.

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

Хотя это может показаться азартной игрой, теоретики восстановили объяснимую стратегию, которая искореняет убеждение, что это азартная игра.

Наиболее часто упоминаемым примером является дилемма заключенного.

Узнайте: 8 лучших проектов, которые каждый разработчик должен обязательно попробовать

Объяснение дилеммы заключенного

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

Итак, окружной прокурор решил упростить это, поставив перед ними три условия, поскольку они сидят рядом.

• Условие 1: Если ни один из них не признается в преступлении, они отправляются в тюрьму на шесть лет.
• Условие 2: если один из них сдаст другого, осведомитель может свободно разгуливать, а другой останется на десять лет.
• Условие 3: Если оба признаются, они отправляются в тюрьму на один год.

Сразу после выслушивания условий их отводят в отдельную комнату для принятия решения.

Мы можем передать эти данные в виде матрицы, как таковой;

Источник

Решение этой проблемы простое;

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

Теория игр — мощное оружие в руках того, кто ею владеет. Мы можем расшифровать даже самые сложные ситуации, поняв природу чисел и их положение в обществе.

Алгоритмическая теория игр

Теперь рассмотрим диаграмму Венна из теории игр и информатики. Представьте себе резкое повышение уровня точности, зачем строить графики вероятности получения ответов.

Именно это и делает Алгоритмическая Теория Игр (АГТ) !

Он пытается решить современные проблемы, достигая идеального баланса между компьютерными алгоритмами и теорией игр.

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

Давайте возьмем небольшой пример, чтобы понять работу алгоритмической теории игр.

Давайте вернемся в школу, когда мы играли в такие игры, как Kho-Kho, Ice & Water, Chain-Cut и т. д. Каждая из этих игр имеет красивый дизайн и механизм игры.

Возьмем, к примеру, Ice & Water;

• Есть несколько игроков и один ловец. Ловец должен превратить всех в лед.
• Другие игроки могут превратить кого-то обратно в воду при прикосновении.
• Есть свободные зоны, где игроки могут отдохнуть 30 секунд.

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

• Игроки могут играть в эту игру до тех пор, пока они находят ее интересной. Здесь Равновесие Нэша описывает, что до тех пор, пока игроки находят свою стратегию работающей и игру интересной, они будут играть.
• Паек игрока - не попасться. И она действует на этом пайке, понимая установку. Она реализует подход, основанный на цели, когда она выигрывает игру, не попадаясь. И это широко известно как дизайн механизмов или теория обратной игры.
• Теперь, если каждый игрок рассматривает только один мотив — «Чтобы не попасться» — и не учитывает вторую его часть — «Спасение других игроков», тогда эта концепция называется Цена Анархии. Это объясняет, как эффективность любой системы будет снижаться из-за эгоистичного поведения игроков.

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

Оформить заказ: 42 захватывающих идеи и темы проектов Python для начинающих

Теперь возникает вопрос: «Как мы можем представить стратегическую среду с точки зрения алгоритмов?»

Давайте теперь посмотрим, как мы можем использовать Python для определения стратегической среды и понимания реализации Nashpy для данной ситуации.

Представьте, что вы играете в «камень-ножницы-бумага» с одним из ваших друзей. У каждого из вас есть любой из трех вариантов;

• Камень
• Бумага
• Ножницы

И рубрика, чтобы выиграть игру

• Камень давит ножницы
• Ножницы режет бумагу
• Бумага покрывает камень

А это значит, что если оба игрока представляют рок, это объясняет переигрывание.

Мы можем представить это в виде матрицы 3 × 3, где Aij;

Источник

Примечание. Здесь i и j — ходы, сыгранные двумя игроками.

Здесь,

• Ноль означает, что вы оба играли один и тот же объект (рок-рок или бумага-бумага).
• Один представляет, что один из вас превзошел другого (как камень-ножницы)
• Минус один означает, что один из вас проиграл, потому что другой превзошел вас (как каменная бумага).

Теперь, чтобы представить это в Nashpy, вы напишете код, который выглядит примерно так:

Источник

Последние мысли

Алгоритмическая теория игр — совершенный принцип в современном мире, где конкуренция проистекает из личного интереса, а победа — это достижение личного интереса.

Итак, как современные менеджеры, учителя, главные директора или бизнесмены, если вы понимаете доминирование алгоритмической теории игр, позвольте мне изменить цитату Северуса Снейпа из «Гарри Поттера»;

«Алгоритмическая теория игр может научить вас разливать славу по бутылкам, варить славу и даже останавливать убытки».

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

Мы уже знаем, что наука о данных может превратить бизнес в прибыльную арену, но AGT может поднять порог.

Предположим, вы все еще скептически относитесь к теории игр и к тому, что наука о данных — самая прибыльная и конкурентоспособная профессия сегодня.

Если вам интересно узнать о науке о данных, ознакомьтесь с дипломом IIIT-B & upGrad PG в области науки о данных, который создан для работающих профессионалов и предлагает более 10 тематических исследований и проектов, практические семинары, наставничество с отраслевыми экспертами, 1- on-1 с отраслевыми наставниками, более 400 часов обучения и помощи в трудоустройстве в ведущих фирмах.