Непрерывная игра

редактировать

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

В общем, игра с несчетно бесконечными наборами стратегий не обязательно будет иметь равновесное решение по Нэшу.. Если, однако, требуется, чтобы наборы стратегий были компактными, а функции полезности непрерывными, тогда равновесие по Нэшу будет гарантировано; это сделано в результате обобщения Гликсбергом теоремы Какутани о неподвижной точке. По этой причине класс непрерывных игр обычно определяется и изучается как подмножество более широкого класса бесконечных игр (то есть игр с бесконечными наборами стратегий), в которых наборы стратегий компактны, а функции полезности непрерывны.

Содержание

1 Формальное определение
- 1.1 Разделимые игры
2 Примеры
- 2.1 Разделимые игры
  - 2.1.1 Полиномиальная игра
- 2.2 Неразделимые игры
  - 2.2.1 Функция рациональной выплаты
  - 2.2.2 Требование распределения Кантора
3 Дополнительная литература
4 См. Также
5 Ссылки

Формальное определение

Определите непрерывное игра $G = (P, C, U) {\ displaystyle G = (P, \ mathbf {C}, \ mathbf {U})}$ $G = (P, {\ mathbf {C}}, {\ mathbf {U}})$ где

P = 1, 2, 3,…, n {\ displaystyle P = {1,2,3, \ ldots, n}}

P = {1,2,3, \ ldots, n}

- это набор

n {\ displaystyle n \,}

n \,

игроков,

C = (C 1, C 2,…, C n) {\ displaystyle \ mathbf {C} = (C_ {1}, C_ {2}, \ ldots, C_ {n})}

{\ mathbf {C}} = (C_ {1}, C_ {2}, \ ldots, C_ {n })

где каждый

C i {\ displaystyle C_ {i} \,}

C_ {i} \,

представляет собой компактный набор в метрическом пространстве, соответствующий к

i {\ displaystyle i \,}

i \,

набор чистых стратегий игрока,

U = (u 1, u 2,…, un) {\ displaystyle \ mathbf {U} = (u_ {1}, u_ {2}, \ ldots, u_ {n})}

{\ mathbf {U}} = ( u_ {1}, u_ {2}, \ ldots, u_ {n})

где

ui: C → R {\ displaystyle u_ {i}: \ mathbf {C} \ to \ mathbb {R}}

u_ {i}: {\ mathbf {C}} \ to \ mathbb {R}

- функция полезности игрока

i {\ displaystyle i \,}

i \,

Мы определяем

Δ я {\ displaystyle \ Delta _ {i} \,}

\ Delta _ {i} \,

как набор борелевских вероятностных мер на

C i {\ displaystyle C_ {i} \,}

C_ {i} \,

, что дает нам пространство смешанных стратегий игрока i.

Определите профиль стратегии

σ = (σ 1, σ 2,…, σ n) {\ displaystyle {\ boldsymbol {\ sigma}} = (\ sigma _ {1}, \ sigma _ {2}, \ ldots, \ sigma _ {n})}

{\ boldsymbol {\ sigma}} = (\ sigma _ {1}, \ sigma _ {2}, \ ldots, \ sigma _ {n})

где

σ i ∈ Δ i {\ displaystyle \ sigma _ {i} \ in \ Delta _ {i} \,}

\ sigma _ {i} \ in \ Delta _ {i} \,

Пусть $σ - i {\ displaystyle {\ boldsymbol {\ sigma}} _ {- i}}$ ${\ boldsymbol {\ sigma}} _ {{- i}}$ быть стратегическим профилем всех игроков, кроме игрока $i {\ displaystyle i}$ $i$ . Как и в случае с дискретными играми, мы можем определить лучший ответ соответствие для игрока $i {\ displaystyle i \,}$ $i \,$ , $bi {\ displaystyle b_ {i} \}$ $b_ {i} \$ . $bi {\ displaystyle b_ {i} \,}$ $b_ {i} \,$ - отношение из набора всех распределений вероятностей по профилям игроков оппонента к набору игроков $i {\ displaystyle i}$ Стратегии $i$ , такие, что каждый элемент

bi (σ - i) {\ displaystyle b_ {i} (\ sigma _ {- i}) \,}

b_ {i} (\ sigma _ {{- i}}) \,

является лучшим ответом на $σ - я {\ displaystyle \ sigma _ {- i}}$ $\ sigma _ {{- i}}$ . Определим

b (σ) = b 1 (σ - 1) × b 2 (σ - 2) × ⋯ × bn (σ - n) {\ displaystyle \ mathbf {b} ({\ boldsymbol {\ sigma}}) = b_ {1} (\ sigma _ {- 1}) \ times b_ {2} (\ sigma _ {- 2}) \ times \ cdots \ times b_ {n} (\ sigma _ {- n})}

{\ mathbf {b}} ({\ boldsymbol {\ sigma}}) = b_ {1} (\ sigma _ {{- 1}}) \ times b_ {2} (\ sigma _ {{- 2}}) \ times \ cdots \ times b_ {n} (\ sigma _ {{- n}})

Профиль стратегии $σ ∗ {\ displaystyle {\ boldsymbol {\ sigma}} *}$ ${\ boldsymbol {\ sigma}} *$ является равновесием по Нэшу тогда и только тогда, когда $σ ∗ ∈ b (σ ∗) {\ Displaystyle {\ boldsymbol {\ sigma}} * \ in \ mathbf {b} ({\ boldsymbol {\ sigma}} *)}$ ${\ boldsymbol {\ sigma }} * \ in {\ mathbf {b}} ({\ boldsymbol {\ sigma}} *)$ Существование равновесия по Нэшу для любого Непрерывная игра с непрерывными функциями полезности может быть доказана с помощью обобщения теоремы Какутани о неподвижной точке. В общем, решения может не быть, если мы разрешаем пространства стратегий, $C i {\ displaystyle C_ {i} \,}$ $C_ {i} \,$ , которые не являются компактными, или если мы разрешаем прерывистые служебные функции.

Разделимые игры

A разделимая игра - это непрерывная игра, в которой для любого i функция полезности $ui: C → R {\ displaystyle u_ {i}: \ mathbf {C} \ to \ mathbb {R}}$ $u_ {i}: {\ mathbf {C}} \ to \ mathbb {R}$ можно выразить в виде суммы произведений:

ui (s) = ∑ k 1 = 1 m 1… ∑ kn = 1 mnai, k 1 … Knf 1 (s 1)… fn (sn) {\ displaystyle u_ {i} (\ mathbf {s}) = \ sum _ {k_ {1} = 1} ^ {m_ {1}} \ ldots \ sum _ {k_ {n} = 1} ^ {m_ {n}} a_ {i \,, \, k_ {1} \ ldots k_ {n}} f_ {1} (s_ {1}) \ ldots f_ {n} (s_ {n})}

u_ {i} ({\ mathbf {s}}) = \ sum _ {{k_ {1} = 1}} ^ {{ m_ {1}}} \ ldots \ sum _ {{k_ {n} = 1}} ^ {{m_ {n}}} a _ {{i \,, \, k_ {1} \ ldots k_ {n}} } f_ {1} (s_ {1}) \ ldots f_ {n} (s_ {n})

, где

s ∈ C {\ displaystyle \ mathbf {s} \ in \ mathbf {C}}

{\ mathbf {s}} \ in {\ mathbf {C}}

si ∈ C i {\ displaystyle s_ {i } \ in C_ {i}}

s_ {i} \ in C_ {i}

ai, k 1… kn ∈ R {\ displaystyle a_ {i \,, \, k_ {1} \ ldots k_ {n}} \ in \ mathbb {R}}

a _ {{i \,, \, k_ {1} \ ldots k_ {n}}} \ in \ mathbb {R}

, а функции

fi, k: C i → R {\ displaystyle f_ {i \,, \, k}: C_ {i} \ to \ mathbb {R}}

f _ {{i \,, \, k}}: C_ {i} \ to \ mathbb {R}

являются непрерывными.

A полиномиальная игра - это разделяемая игра, в которой каждый $C i {\ displaystyle C_ {i} \,}$ $C_ {i} \,$ представляет собой компактный интервал на $R { \ displaystyle \ mathbb {R} \,}$ $\ mathbb {R} \,$ и каждая служебная функция может быть записанным как многомерный полином.

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

Для любой разделяемой игры существует по крайней мере одно равновесие по Нэшу, в котором игрок i смешивает большинство

mi + 1 {\ displaystyle m_ {i} +1 \,}

m_{i}+1\,

чистых стратегий.

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

Примеры

Разделимые игры

Полиномиальная игра

Рассмотрим игру двух игроков с нулевой суммой между игроками X и Y, где $CX = CY = [0, 1] {\ displaystyle C_ {X} = C_ {Y} = \ left [0,1 \ right]}$ $C_ {X} = C_ {Y} = \ left [0,1 \ right]$ . Обозначим элементы $CX {\ displaystyle C_ {X} \,}$ $C_ {X} \,$ и $CY {\ displaystyle C_ {Y} \,}$ $C_{Y}\,$ как $x { \ displaystyle x \,}$ $x \,$ и $y {\ displaystyle y \,}$ $y \,$ соответственно. Определите функции полезности $H (x, y) = ux (x, y) = - uy (x, y) {\ displaystyle H (x, y) = u_ {x} (x, y) = - u_ {y} (x, y) \,}$ $H ( x, y) = u_ {x} (x, y) = - u_ {y} (x, y) \,$ где

H (x, y) = (x - y) 2 {\ displaystyle H (x, y) = (xy) ^ {2 } \,}

H(x,y)=(xy)^{2}\,

Чистые отношения наилучшего ответа стратегии:

b X (y) = {1, если y ∈ [0, 1/2) 0 или 1, если y = 1/2 0, если y ∈ (1/2, 1] {\ displaystyle b_ {X} (y) = {\ begin {cases} 1, {\ t_dv {if}} y \ in \ left [0,1 / 2 \ right) \\ 0 {\ text {или}} 1, {\ t_dv {if}} y = 1/2 \\ 0, {\ t_dv {if}} y \ in \ left (1 / 2,1 \ right ] \ end {cases}}}

b_ {X} (y) = {\ begin {cases} 1, {\ t_dv {if}} y \ in \ left [0,1 / 2 \ right) \\ 0 {\ text {или}} 1, {\ t_dv {if}} y = 1/2 \\ 0, {\ t_dv {if}} y \ in \ left (1 / 2,1 \ right] \ end {case}}

b Y (x) = x {\ displaystyle b_ {Y} (x) = x \,}

b_ {Y} (x) = x \,

$b X (y) {\ displaystyle b_ {X} (y) \,}$ $b_ {X} (y) \,$ и $b Y (x) {\ displaystyle b_ {Y} (x) \,}$ $b_ {Y} (x) \,$ не пересекаются, поэтому существует

нет чистой стратегии равновесия по Нэшу. Однако должно быть смешанное стратегическое равновесие. Чтобы найти его, выразите математическое ожидание, $v = E [H (x, y)] {\ displaystyle v = \ mathbb {E} [H (x, y)]}$ $v = {\ mathbb {E}} [H (x, y)]$ как линейная комбинация первого и второго моментов p распределения надежности X и Y:

v = μ X 2 - 2 μ X 1 μ Y 1 + μ Y 2 {\ displaystyle v = \ mu _ {X2} -2 \ mu _ {X1} \ mu _ {Y1} + \ mu _ {Y2} \,}

v = \ mu _ {{X2}} - 2 \ mu _ {{X1}} \ mu _ {{Y1} } + \ mu _ {{Y2}} \,

(где $μ XN = E [x N] {\ displaystyle \ mu _ {XN} = \ mathbb {E} [x ^ {N}]}$ $\ mu _ {{XN}} = {\ mathbb {E}} [x ^ {N}]$ и аналогично для Y).

Ограничения для $μ X 1 {\ displaystyle \ mu _ {X1} \,}$ $\ mu _ {{X1}} \,$ и $μ X 2 {\ displaystyle \ mu _ {X2}}$ $\ mu _ {{X2}}$ (с аналогичными ограничениями для y,) задаются Хаусдорфом как:

μ X 1 ≥ μ X 2 μ X 1 2 ≤ μ X 2 μ Y 1 ≥ μ Y 2 μ Y 1 2 ≤ μ Y 2 {\ Displaystyle {\ begin {align} \ mu _ {X1} \ geq \ mu _ {X2} \\\ mu _ {X1} ^ {2} \ leq \ mu _ { X2} \ end {align}} \ qquad {\ begin {align} \ mu _ {Y1} \ geq \ mu _ {Y2} \\\ mu _ {Y1} ^ {2} \ leq \ mu _ {Y2} \ end {align}}}

{\ begin {align} \ mu _ { {X1}} \ geq \ mu _ {{X2}} \\\ mu _ {{X1}} ^ {2} \ leq \ mu _ {{X2}} \ end {align}} \ qquad {\ begin { выровнено} \ mu _ {{Y1}} \ geq \ mu _ {{Y2}} \\\ mu _ {{Y1}} ^ {2} \ leq \ mu _ {{Y2}} \ end {align}}

Каждая пара ограничений определяет компактное выпуклое подмножество на плоскости. Поскольку $v {\ displaystyle v \,}$ $v \,$ является линейным, любые экстремумы по отношению к первым двум моментам игрока будут лежать на границе этого подмножества. Стратегия равновесия игрока i будет лежать на

μ i 1 = μ i 2 или μ i 1 2 = μ i 2 {\ displaystyle \ mu _ {i1} = \ mu _ {i2} {\ text {or}} \ mu _ {i1} ^ {2} = \ mu _ {i2}}

\ mu _ {{i1}} = \ mu _ {{i2}} {\ text {или }} \ mu _ {{i1}} ^ {2} = \ mu _ {{i2}}

Обратите внимание, что первое уравнение допускает только смеси 0 и 1, тогда как второе уравнение допускает только чистые стратегии. Более того, если лучший ответ в определенный момент игроку i лежит на $μ i 1 = μ i 2 {\ displaystyle \ mu _ {i1} = \ mu _ {i2} \,}$ $\ mu _ {{i1}} = \ mu _ {{i2}} \,$ , он будет лежать на всей строке, так что и 0, и 1 являются лучшим ответом. $b Y (μ X 1, μ X 2) {\ displaystyle b_ {Y} (\ mu _ {X1}, \ mu _ {X2}) \,}$ $b_ {Y} (\ mu _ {{X1}}, \ mu _ {{X2}}) \,$ просто дает чистую стратегию $y = μ X 1 {\ displaystyle y = \ mu _ {X1} \,}$ $y = \ mu _ {{X1}} \,$ , поэтому $b Y {\ displaystyle b_ {Y} \,}$ $b_ {Y} \,$ никогда не даст одновременно 0 и 1. Однако $bx {\ displaystyle b_ {x} \,}$ $b_ {x} \,$ дает и 0, и 1, когда y = 1/2. Равновесие по Нэшу существует, когда:

(μ X 1 ∗, μ X 2 ∗, μ Y 1 ∗, μ Y 2 ∗) = (1/2, 1/2, 1/2, 1/4) {\ displaystyle (\ mu _ {X1} *, \ mu _ {X2} *, \ mu _ {Y1} *, \ mu _ {Y2} *) = (1 / 2,1 / 2,1 / 2,1 / 4) \,}

(\ mu _ {{X1}} *, \ mu _ {{X2}} *, \ mu _ {{Y1}} *, \ mu _ {{Y2}} *) = (1/2, 1 / 2,1 / 2,1 / 4) \,

Это определяет одно уникальное равновесие, в котором Игрок X играет случайную смесь 0 в течение 1/2 времени и 1 в течение другой 1/2 времени. Игрок Y использует чистую стратегию 1/2. Стоимость игры - 1/4.

Неразделимые игры

Рациональная функция выигрыша

H (x, y) = (1 + x) (1 + y) (1 - xy) (1 + xy) 2. {\ displaystyle H (x, y) = {\ frac {(1 + x) (1 + y) (1-xy)} {(1 + xy) ^ {2}}}.}

H (x, y) = {\ гидроразрыва {(1 + x) (1 + y) (1-xy)} {(1 + xy) ^ {2}}}.

В этой игре нет чистой стратегии равновесия по Нэшу. Можно показать, что единственная смешанная стратегия равновесия по Нэшу существует со следующей парой функций плотности вероятности :

f ∗ (x) = 2 π x (1 + x) g ∗ (y) = 2 π y ( 1 + у). {\ displaystyle f ^ {*} (x) = {\ frac {2} {\ pi {\ sqrt {x}} (1 + x)}} \ qquad g ^ {*} (y) = {\ frac { 2} {\ pi {\ sqrt {y}} (1 + y)}}.}

f ^ {*} (x) = {\ frac {2} {\ pi {\ sqrt {x}} (1 + x)}} \ qquad g ^ {*} (y) = {\ frac {2} { \ pi {\ sqrt {y}} (1 + y)}}.

Ценность игры: $4 / π {\ displaystyle 4 / \ pi}$ $4 / \ pi$ .

Требуется кантор распределение

Рассмотрим игру двух игроков с нулевой суммой между игроками X и Y с $CX = CY = [0, 1] {\ displaystyle C_ {X} = C_ {Y} = \ left [0,1 \ right]}$ $C_ {X} = C_ {Y} = \ left [0,1 \ right]$ . Обозначим элементы $CX {\ displaystyle C_ {X} \,}$ $C_ {X} \,$ и $CY {\ displaystyle C_ {Y} \,}$ $C_{Y}\,$ как $x { \ displaystyle x \,}$ $x \,$ и $y {\ displaystyle y \,}$ $y \,$ соответственно. Определите функции полезности $H (x, y) = ux (x, y) = - uy (x, y) {\ displaystyle H (x, y) = u_ {x} (x, y) = - u_ {y} (x, y) \,}$ $H ( x, y) = u_ {x} (x, y) = - u_ {y} (x, y) \,$ где

H (x, y) = ∑ n = 0 ∞ 1 2 n (2 xn - ((1 - x 3) n - ( Икс 3) n)) (2 yn - ((1 - y 3) n - (y 3) n)) {\ displaystyle H (x, y) = \ sum _ {n = 0} ^ {\ infty} { \ frac {1} {2 ^ {n}}} \ left (2x ^ {n} - \ left (\ left (1 - {\ frac {x} {3}} \ right) ^ {n} - \ left ({\ frac {x} {3}} \ right) ^ {n} \ right) \ right) \ left (2y ^ {n} - \ left (\ left (1 - {\ frac {y} {3}) } \ right) ^ {n} - \ left ({\ frac {y} {3}} \ right) ^ {n} \ right) \ right)}

H (x, y) = \ sum _ {{n = 0}} ^ {\ infty} {\ frac {1} {2 ^ {n}}} \ left (2x ^ {n} - \ left (\ left (1 - {\ frac {x} {3}} \ right) ^ {n} - \ left ({\ frac {x}) {3}} \ right) ^ {n} \ right) \ right) \ left (2y ^ {n} - \ left (\ left (1 - {\ frac {y} {3}} \ right) ^ {n} - \ left ( {\ frac {y} {3}} \ right) ^ {n} \ right) \ right)

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

Дополнительная литература

H. W. Kuhn и A. W. Tucker, ред. (1950). Вклад в теорию игр: Vol. II. Анналы математических исследований 28 . Издательство Принстонского университета. ISBN 0-691-07935-8.

См. Также

Непрерывный график

Ссылки

^I.L. Гликсберг. Дальнейшее обобщение теоремы Какутани о неподвижной точке с применением к точкам равновесия по Нэшу. Труды Американского математического общества, 3 (1): 170–174, февраль 1952 г.
^Н. Штейн, А. Оздаглар, П.А. Паррило. «Разделимые и непрерывные игры низкого ранга». International Journal of Game Theory, 37 (4): 475–504, декабрь 2008 г. https://arxiv.org/abs/0707.3462
^Гликсберг, И. и Гросс, О. (1950). «Записки об играх над площадью». Кун, Х.В. И Такер, A.W. ред. Вклад в теорию игр: Том II. Анналы математических исследований 28, с.173–183. Издательство Принстонского университета.
^Гросс, О. (1952). «Рациональная характеристика выигрыша распределения Кантора». Технический отчет D-1349, Корпорация РЭНД.