Потенциальная игра

В теории игр игра называется потенциальной игрой , если стимул всех игроков изменить свою стратегию может быть выражен с помощью одной глобальной функции, называемой потенциальной функцией . Эта концепция возникла в статье 1996 года Дова Мондерера и Ллойда Шепли . ^[1]

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

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

Потенциальные игры можно изучать как повторяющиеся игры с состоянием, так что каждый сыгранный раунд имеет прямое влияние на состояние игры в следующем раунде. ^[2] Этот подход находит применение в распределенном управлении, например, при распределенном распределении ресурсов, когда игроки без центрального механизма корреляции могут сотрудничать для достижения глобально оптимального распределения ресурсов.

Определение [ править ]

Позволять $N$ быть числом игроков, $A$ набор профилей действий над наборами действий $A_{i}$ каждого игрока и $u_{i}:A\to \mathbb {R}$ быть функцией выигрыша для игрока $1\leq i\leq N$ .

Учитывая игру $G=(N,A=A_{1}\times \ldots \times A_{N},u:A\rightarrow \mathbb {R} ^{N})$ , мы говорим, что $G$ является потенциальной игрой с точной (взвешенной, порядковой, обобщенной порядковой, лучшим ответом) потенциальной функцией , если $\Phi :A\rightarrow \mathbb {R}$ — точная (соответственно взвешенная, порядковая, обобщенная порядковая, лучший ответ) потенциальная функция для $G$ . Здесь, $\Phi$ называется

точная потенциальная функция, если $\forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}$ ,

\Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})

То есть: когда игрок

i

переключается с действия

a'

к действию

a''

, изменение потенциала

\Phi

равно изменению полезности этого игрока.

если взвешенная потенциальная функция, существует вектор $w\in \mathbb {R} _{++}^{N}$ такой, что $\forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}$ ,

\Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})=w_{i}(u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i}))

То есть: когда игрок переключает действие, изменение

\Phi

равно изменению полезности игрока, умноженному на положительный вес, специфичный для игрока. Каждый точный ПФ является взвешенным ПФ с w _i =1 для всех i .

порядковая потенциальная функция, если $\forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}$ ,

u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Leftrightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0

То есть: когда игрок переключает действие, знак изменения

\Phi

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

обобщенная порядковая потенциальная функция, если $\forall i,\forall {a_{-i}\in A_{-i}},\ \forall {a'_{i},\ a''_{i}\in A_{i}}$ ,

u_{i}(a'_{i},a_{-i})-u_{i}(a''_{i},a_{-i})>0\Rightarrow \Phi (a'_{i},a_{-i})-\Phi (a''_{i},a_{-i})>0

То есть: когда игрок меняет действие, если полезность игрока увеличивается, то и потенциал увеличивается (но не обязательно обратное). Всякая порядковая ПФ является обобщенно-порядковой ПФ.

потенциальная функция наилучшего ответа, если $\forall i\in N,\ \forall {a_{-i}\in A_{-i}}$ ,

b_{i}(a_{-i})=\arg \max _{a_{i}\in A_{i}}\Phi (a_{i},a_{-i})

где

b_{i}(a_{-i})

это лучшее действие для игрока

i

данный

a_{-i}

.

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

Простой пример [ править ]

В игре двумя игроками и двумя действиями с внешними эффектами выигрыши отдельных игроков определяются функцией $u i (a i, a j) = b i a i + wa i a с j$ , где $a i$ - действие игрока i. , $a j$ — действие противника, а w — положительный от внешний эффект выбора того же действия. Варианты действий — +1 и —1, как видно из матрицы выигрышей на рисунке 1.

В этой игре есть P потенциальная функция $(a 1, a 2) = b 1 a 1 + b 2 a 2 + w a 1 a 2$ .

Если игрок 1 перемещается от −1 к +1, разница выигрышей равна $Δ u 1 = u 1 (+1, a 2) - u 1 (-1, a 2) = 2 b 1 + 2 w a 2$ .

Изменение потенциала равно $ΔP = P(+1, a 2) - P(-1, a 2) = (b 1 + b 2 a 2 + w a 2) - (- b 1 + b 2 a 2 - w а 2) знак равно 2 б 1 + 2 ш а 2 знак равно Δ ты 1$ .

Решение для игрока 2 эквивалентно. Используя числовые значения $b 1 = 2$ , $b 2 = -1$ , $w = 3$ , этот пример превращается в простую ( битву полов , как показано на рисунке 2. В игре есть два чистых равновесия Нэша $+1, +1).$ и $(-1, -1)$ . Это и есть локальные максимумы потенциальной функции (рис. 3). Единственное стохастически устойчивое равновесие — это $(+1, +1)$ глобальный максимум потенциальной функции.

	+1	–1
+1	$+ б 1 + ш, + б 2 + ш$	$+ б 1 - ш, - б 2 - ш$
–1	$- б 1 - ж, + б 2 - ш$	$- б 1 + ш, - б 2 + ш$
Рис. 1: Пример потенциальной игры

	+1	–1
+1	5, 2	–1, –2
–1	–5, –4	1, 4
Рис. 2: Битва полов (выплаты)

	+1	–1
+1	4	0
–1	–6	2
Рис. 3: Битва полов (потенциалы)

Игра для двух игроков и двух действий не может быть потенциальной игрой, если только

[u_{1}(+1,-1)+u_{1}(-1,+1)]-[u_{1}(+1,+1)+u_{1}(-1,-1)]=[u_{2}(+1,-1)+u_{2}(-1,+1)]-[u_{2}(+1,+1)+u_{2}(-1,-1)]

Потенциальные игры и перегрузками с игры

Точные потенциальные игры эквивалентны играм с перегрузками : Розенталь ^[3] доказал, что каждая игра с перегрузками имеет точный потенциал; Мондерер и Шепли ^[1] доказал обратное: всякая игра с точной потенциальной функцией является игрой с перегруженностью .

Потенциальные игры и пути улучшения [ править ]

Путь улучшения (также называемый динамикой Нэша ) — это последовательность векторов стратегий, в которой каждый вектор достигается из предыдущего вектора, когда один игрок переключает свою стратегию на стратегию, которая строго увеличивает его полезность. Если игра имеет функцию обобщенного порядкового потенциала $\Phi$ , затем $\Phi$ строго возрастает на каждом пути улучшения, поэтому каждый путь улучшения является ациклическим. Если, кроме того, в игре конечное число стратегий, то каждый путь улучшения должен быть конечным. Это свойство называется свойством конечного улучшения (FIP) . Мы только что доказали, что каждая конечная игра с обобщенным порядковым потенциалом имеет FIP. Верно и обратное: в каждой конечной игре FIP имеет функцию обобщенного порядкового потенциала. ^[4]^{[ нужны разъяснения ]} Конечное состояние на каждом пути конечного улучшения представляет собой равновесие Нэша, поэтому FIP подразумевает существование равновесия Нэша чистой стратегии. Более того, это означает, что равновесие Нэша может быть вычислено с помощью распределенного процесса, в котором каждому агенту нужно только улучшить свою собственную стратегию.

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

Еще более слабое свойство — слабая ацикличность (WA) . ^[5] Это означает, что для любого начального вектора стратегии существует конечный путь наилучшего ответа, начинающийся с этого вектора. Слабой ацикличности недостаточно для существования потенциальной функции (поскольку некоторые пути улучшения могут быть циклическими), но ее достаточно для существования равновесия по Нэшу в чистой стратегии. вычислить Это означает, что равновесие Нэша можно почти наверняка с помощью стохастического распределенного процесса, в котором в каждой точке игрок выбирается случайным образом, и этот игрок случайным образом выбирает лучшую стратегию. ^[4]

См. также [ править ]

Игра с пробками
Эконофизика
Характеристика ординальных потенциальных игр. ^[6]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Мондерер, Дов; Шепли, Ллойд (1996). «Потенциальные игры». Игры и экономическое поведение . 14 : 124–143. дои : 10.1006/game.1996.0044 .
^ Марден, Дж., (2012) Потенциальные игры на уровне штата http://ecee.colorado.edu/marden/files/state-based-games.pdf
^ Розенталь, Роберт В. (1973), «Класс игр, обладающих равновесием Нэша в чистой стратегии», International Journal of Game Theory , 2 : 65–67, doi : 10.1007/BF01737559 , MR 0319584 , S2CID 121904640 .
^ Jump up to: Перейти обратно: ^а ^б Мильхтайх, Игаль (1 марта 1996 г.). «Игры с перегрузками и функциями выигрыша для конкретного игрока» . Игры и экономическое поведение . 13 (1): 111–124. дои : 10.1006/game.1996.0027 . ISSN 0899-8256 .
^ Янг, Х. Пейтон (1993). «Эволюция конвенций» . Эконометрика . 61 (1): 57–84. дои : 10.2307/2951778 . ISSN 0012-9682 . JSTOR 2951778 .
^ Воорневельд, Марк; Норде, Хенк (1 мая 1997 г.). «Характеристика порядковых потенциальных игр» . Игры и экономическое поведение . 19 (2): 235–242. дои : 10.1006/game.1997.0554 . ISSN 0899-8256 . S2CID 122795041 .

Внешние ссылки [ править ]

Конспект лекций Ишая Мансура о Потенциальных играх и играх с перегрузками
Раздел 19 в: Вазирани, Виджай В .; Нисан, Ноам ; Рафгарден, Тим ; Тардос, Ева (2007). Алгоритмическая теория игр (PDF) . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 0-521-87282-0 .
Нетехническое изложение Хью Диксоном неизбежности сговора. Глава 8, Мир пончиков и архипелаг дуополии , Surfing Economics .

[MS-1] Jump up to: Перейти обратно: ^а ^б Мондерер, Дов; Шепли, Ллойд (1996). «Потенциальные игры». Игры и экономическое поведение . 14 : 124–143. дои : 10.1006/game.1996.0044 .

[2] Марден, Дж., (2012) Потенциальные игры на уровне штата http://ecee.colorado.edu/marden/files/state-based-games.pdf

[:1-3] Розенталь, Роберт В. (1973), «Класс игр, обладающих равновесием Нэша в чистой стратегии», International Journal of Game Theory , 2 : 65–67, doi : 10.1007/BF01737559 , MR 0319584 , S2CID 121904640 .

[:2-4] Jump up to: Перейти обратно: ^а ^б Мильхтайх, Игаль (1 марта 1996 г.). «Игры с перегрузками и функциями выигрыша для конкретного игрока» . Игры и экономическое поведение . 13 (1): 111–124. дои : 10.1006/game.1996.0027 . ISSN 0899-8256 .

[5] Янг, Х. Пейтон (1993). «Эволюция конвенций» . Эконометрика . 61 (1): 57–84. дои : 10.2307/2951778 . ISSN 0012-9682 . JSTOR 2951778 .

[6] Воорневельд, Марк; Норде, Хенк (1 мая 1997 г.). «Характеристика порядковых потенциальных игр» . Игры и экономическое поведение . 19 (2): 235–242. дои : 10.1006/game.1997.0554 . ISSN 0899-8256 . S2CID 122795041 .

[1]

[2]

[3]

[4]

[5]

[6]

v т и Темы теории игр
Definitions	Congestion game Cooperative game Determinacy Escalation of commitment Extensive-form game First-player and second-player win Game complexity Graphical game Hierarchy of beliefs Information set Normal-form game Preference Sequential game Simultaneous game Simultaneous action selection Solved game Succinct game Mechanism design
Equilibrium concepts	Bayes correlated equilibrium Bayesian Nash equilibrium Berge equilibrium Core Correlated equilibrium Coalition-proof Nash equilibrium Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Mertens-stable equilibrium Markov perfect equilibrium Nash equilibrium Pareto efficiency Perfect Bayesian equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Backward induction Bid shading Collusion Cheap talk De-escalation Deterrence Escalation Forward induction Grim trigger Markov strategy Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat
Classes of games	Auction Bargaining problem Global game Intransitive game Mean-field game n-player game Perfect information Large Poisson game Potential game Repeated game Screening game Signaling game Strictly determined game Stochastic game Symmetric game Zero-sum game
Games	Go Chess Infinite chess Checkers All-pay auction Prisoner's dilemma Gift-exchange game Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Lewis signaling game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock paper scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Bertrand competition Cournot competition Stackelberg competition Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Induction puzzles Trust game Princess and monster game Rendezvous problem
Theorems	Aumann's agreement theorem Folk theorem Minimax theorem Nash's theorem Negamax theorem Purification theorem Revelation principle Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin John Conway Jean Tirole Jean-François Mertens Jennifer Tour Chayes John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey
Miscellaneous	Alpha–beta pruning Bounded rationality Combinatorial game theory Confrontation analysis Coopetition Evolutionary game theory Glossary of game theory List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons

v т и Микроэкономика
Major topics	Aggregation Budget set Consumer choice Convexity and non-convexity Cost Average Marginal Opportunity Implicit Social Sunk Transaction Cost–benefit analysis Deadweight loss Distribution Economies of scale Economies of scope Elasticity Cross elasticity of demand Income elasticity of demand Price elasticity of demand Price elasticity of supply Equilibrium General Exchange Externality Firms Goods and services Goods Service Household Income–consumption curve Information Indifference curve Intertemporal choice Market Market failure Market structure Competition Monopolistic Perfect Duopoly Monopoly Bilateral Complementary Monopsony Oligopoly Oligopsony Pareto efficiency Preferences Price Price controls Price ceiling Price floor Price discrimination Price signal Price system/Free Pricing Production Profit Public goods Rationing Rent Returns to scale Risk aversion Scarcity Shortage/Excess supply Substitution effect Surplus Social choice Supply and demand Demand/Law of demand Supply/Law of supply Uncertainty Utility Expected Marginal Wage
Subfields	Behavioral Business Computational Development Statistical decision theory Econometrics Engineering economics Civil engineering economics Evolutionary Experimental Game theory Green Industrial organization Institutional Labor Law Managerial Mathematical Microfoundations of macroeconomics Operations research Optimization Welfare
See also	Economics Applied Macroeconomics Political economy
Business portal Category