Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Класс теорем о профилях выигрышей в равновесии Нэша в повторяющихся играх
Class of theorems about Nash equilibrium payoff profiles in repeated games
В теории игр, народные теоремы – это класс теорем, описывающих множество профилей выигрышей в равновесии Нэша в повторяющихся играх. Оригинальная народная теорема касалась выигрышей во всех равновесиях Нэша бесконечно повторяемой игры. Этот результат получил название народной теоремы, поскольку он был широко известен среди специалистов по теории игр в 1950-х годах, хотя никто его не опубликовал. Теорема Фридмана (1971) относится к выигрышам определенных совершенных подигровых равновесий Нэша (SPE) бесконечно повторяемой игры и, таким образом, усиливает оригинальную народную теорему, используя более сильное понятие равновесия: совершенные подигровые равновесия Нэша, а не просто равновесия Нэша. Народная теорема предполагает, что если игроки достаточно терпеливы и обладают дальновидностью (то есть, если дисконтный фактор достаточно мал), то повторное взаимодействие может привести практически к любому среднему выигрышу в равновесии SPE. "Практически любой" в данном случае технически определяется как "достижимый" и "индивидуально рациональный".
In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame perfect Nash equilibria rather than Nash equilibria. The Folk Theorem suggests that if the players are patient enough and far sighted (i. e. if the discount factor ), then repeated interaction can result in virtually any average payoff in an SPE equilibrium. "Virtually any" is here technically defined as "feasible" and "individually rational".
Бесконечно повторяющиеся игры без дисконтирования
В модели без дисконтирования игроки терпеливы. Они не различают полезность в разные периоды времени. Следовательно, их полезность в повторяющейся игре представляется суммой полезностей в базовых играх. Когда игра бесконечна, общепринятой моделью полезности в бесконечно повторяемой игре является нижний предел среднего значения полезности: если игра приводит к траектории исходов , где обозначает коллективный выбор игроков на итерации t (t=0,1,2,…), то полезность игрока i определяется как
In the undiscounted model, the players are patient. They do not differentiate between utilities in different time periods. Hence, their utility in the repeated game is represented by the sum of utilities in the basic games. When the game is infinite, a common model for the utility in the infinitely repeated game is the limit inferior of mean utility: If the game results in a path of outcomes , where denotes the collective choices of the players at iteration t (t=0,1,2, ), player i utility is defined as
где – функция полезности игрока i в базовой игре. Бесконечно повторяемая игра без дисконтирования часто называется "суперигрой". Теорема народности в этом случае очень проста и не содержит предварительных условий: любой индивидуально рациональный и достижимый профиль выигрышей в базовой игре является профилем выигрышей равновесия Нэша в повторяемой игре. Доказательство использует так называемый "мрачный триггер". Наказание не должно быть вечным; оно должно длиться лишь конечное время, достаточное для устранения выгоды от отклонения. После этого остальные игроки должны вернуться к равновесной траектории. Критерий предельного среднего значения гарантирует, что любое конечное наказание не повлияет на конечный исход. Следовательно, ограниченное по времени наказание является совершенным подигровым равновесием. Коалиционные совершенные подигровые равновесия: при использовании критерия предельного среднего значения профиль выигрышей достижим в коалиционном равновесии Нэша или в коалиционном совершенном подигровом равновесии тогда и только тогда, когда он является парето-эффективным и слабо коалиционно индивидуально рациональным.
where is the basic game utility function of player i. An infinitely repeated game without discounting is often called a "supergame". The folk theorem in this case is very simple and contains no pre conditions: every individually rational and feasible payoff profile in the basic game is a Nash equilibrium payoff profile in the repeated game. The proof employs what is called a grim or grim trigger The punishment should not last forever; it should last only a finite time which is sufficient to wipe out the gains from deviation. After that, the other players should return to the equilibrium path. The limit of means criterion ensures that any finite time punishment has no effect on the final outcome. Hence, limited time punishment is a subgame perfect equilibrium. Coalition subgame perfect equilibria: With the limit of means criterion, a payoff profile is attainable in coalition Nash equilibrium or in coalition subgame perfect equilibrium, if and only if it is Pareto efficient and weakly coalition individually rational.