Равновесие удовлетворенности

Равновесие удовлетворенности
Концепция решения в теории игр
Отношение
Подмножество	концепция решения
Суперсет	Теория некооперативных игр
Значение
Используется для	Все некооперативные игры

В теории игр равновесие удовлетворения — это концепция решения для класса некооперативных игр , а именно игр в форме удовлетворения . Игры с удовлетворением формируют модельные ситуации, в которых игроки стремятся удовлетворить заданному индивидуальному ограничению, например, показатель производительности должен быть меньше или больше заданного порога. Когда игрок удовлетворяет своему собственному ограничению, говорят, что игрок удовлетворен . Равновесие удовлетворения , если оно существует, возникает, когда все игроки в игре удовлетворены.

История

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

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

Игры в форме удовлетворения и понятие равновесия удовлетворения использовались в контексте пятого поколения сотовой связи (5G) для решения проблемы энергоэффективности. совместное использование спектра и управление мощностью передачи. В интеллектуальной сети игры в форме удовлетворения использовались для моделирования проблемы атак с внедрением данных.

Игры

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

---

Определение [Игры в форме удовлетворения ]
Игра в форме удовлетворения описывается кортежем

$\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace f_{k}\right\rbrace _{k\in {\mathcal {K}}}\right),$

где, набор ${\mathcal {K}}=\lbrace 1,\ldots ,K\rbrace \subset \mathrm {N}$, с $0<K<+\infty$, представляет набор игроков; набор ${\mathcal {A}}_{k}$, с $k\in {\mathcal {K}}$ и $0<|{\mathcal {A}}_{k}|<+\infty$, представляет собой набор действий, которые игрок $k$ можно играть. Отображение предпочтений

$f_{k}:{\mathcal {A}}_{1}\times \ldots \times {\mathcal {A}}_{k-1}\times {\mathcal {A}}_{k+1}\times \ldots ,\times {\mathcal {A}}_{K}\rightarrow 2^{{\mathcal {A}}_{k}}$

определяет набор действий, с помощью которых игрок $k$ удовлетворен действиями всех остальных игроков. Набор $2^{{\mathcal {A}}_{k}}$ это мощности набор ${\mathcal {A}}_{k}$.

---

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

Равновесие

Профиль действия представляет собой кортеж ${\boldsymbol {a}}=\left(a_{1},\ldots ,a_{K}\right)\in {\mathcal {A}}_{1}\times \ldots \times {\mathcal {A}}_{K}$. Профиль действия, при котором все игроки удовлетворены, является равновесием соответствующей игры в форме удовлетворения. При равновесии удовлетворения игроки не проявляют особого интереса к изменению своего текущего действия.

---

Определение. Равновесие удовлетворенности в чистых стратегиях. ]
Профиль действия ${\boldsymbol {a}}$ является равновесием удовлетворения в чистых стратегиях игры $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace f_{k}\right\rbrace _{k\in {\mathcal {K}}}\right),$ если для всех $k\in {\mathcal {K}}$,

$a_{k}\in f_{k}\left(a_{1},\ldots ,a_{k-1},a_{k+1},\ldots ,a_{K}\right)$.

---

удовлетворенности в

Для всех $k\in {\mathcal {K}}$, обозначаем множество всех возможных распределений вероятностей на множестве ${\mathcal {A}}_{k}=\lbrace A_{k,1},A_{k,2},\ldots ,A_{k,N_{k}}\rbrace$ к $\triangle \left({\mathcal {A}}_{k}\right)$, с $N_{k}=|{\mathcal {A}}_{k}|$. Обозначим через ${\boldsymbol {\pi }}_{k}=\left(\pi _{k,1},\pi _{k,2},\ldots ,\pi _{k,N_{k}}\right)$ распределение вероятностей ( смешанная стратегия ), принятое игроком $k$ выбирать свои действия. Для всех $j\in \lbrace 1,\ldots ,N_{k}\rbrace$, $\pi _{k,j}$ представляет вероятность, с которой игрок $k$ выбирает действие $A_{k,j}\in {\mathcal {A}}_{k}$. Обозначения ${\boldsymbol {\pi }}_{-k}$ представляет смешанные стратегии всех игроков, кроме игрока $k$.

---

Определение [Распространение формы удовлетворения на смешанные стратегии ] Расширение в смешанных стратегиях игры $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace f_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$ описывается кортежем $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace {\bar {f}}_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$, где переписка

${\bar {f}}_{k}:\prod _{j\in {\mathcal {K}}\setminus \lbrace k\rbrace }\triangle \left({\mathcal {A}}_{j}\right)\rightarrow 2^{\triangle \left({\mathcal {A}}_{k}\right)}$

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

${\bar {f}}_{k}\left({\boldsymbol {\pi }}_{-k}\right)=\left\lbrace {\boldsymbol {\pi }}_{k}\in \triangle \left({\mathcal {A}}_{k}\right):\mathrm {Pr} \left(a_{k}\in f_{k}\left({\boldsymbol {a}}_{-k}\right)|a_{k}\sim {\boldsymbol {\pi }}_{k},{\boldsymbol {a}}_{-k}\sim {\boldsymbol {\pi }}_{-k}\right)=1\right\rbrace .$

---

Равновесие удовлетворения в смешанных стратегиях определяется следующим образом.

---

Определение. Равновесие удовлетворенности в смешанных стратегиях. ]
Профиль смешанной стратегии ${\boldsymbol {\pi }}^{*}\in \triangle \left({\mathcal {A}}_{1}\right)\times \ldots \times \triangle \left({\mathcal {A}}_{K}\right)$ является SE в смешанных стратегиях, если для всех $k\in {\mathcal {K}}$,

${\boldsymbol {\pi }}_{k}^{*}\in {\bar {f}}_{k}\left({\boldsymbol {\pi }}_{-k}^{*}\right)$.

---

Пусть $j$-е действие игрока $k$, то есть, $A_{k,j}$, быть сопоставлено с унитарным вектором ${\boldsymbol {e}}_{j}=\left(e_{1},e_{2}\ldots ,e_{N_{k}}\right)\in \mathrm {R} ^{N_{k}}$, где все компоненты равны нулю, кроме $j$-ая компонента, равная единице. Вектор ${\boldsymbol {e}}_{j}$ представляет собой вырожденное распределение вероятностей, где действие $A_{k,j}$ выбирается детерминированно. Используя этот аргумент, становится ясно, что любое равновесие удовлетворения в чистых стратегиях игры $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace f_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$ также является равновесием удовлетворения в смешанных стратегиях игры $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace {\bar {f}}_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$.

В SE игры $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace f_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$, игроки выбирают свои действия в соответствии с распределением вероятностей, так что с положительной вероятностью разыгрываются только те профили действий, которые позволяют всем игрокам одновременно удовлетворять свои индивидуальные условия с вероятностью единица. Следовательно, в случае, когда одного УЭ в чистых стратегиях не существует, то не существует и УЭ в смешанных стратегиях в игре. $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace {\bar {f}}_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$.

ε

При определенных условиях всегда можно построить смешанные стратегии, позволяющие игрокам довольствоваться вероятностью. $1-\epsilon$, для некоторых $\epsilon >0$. Это наблюдение приводит к определению концепции решения, известной как $\epsilon$- равновесие удовлетворения ( $\epsilon$-СЭ).

---

Определение: [Равновесие ε-удовлетворения ]
Позволять $\epsilon$ удовлетворить $\epsilon \in \left]0,1\right]$. Профиль смешанной стратегии ${\boldsymbol {\pi }}^{*}\in \triangle \left({\mathcal {A}}_{1}\right)\times \triangle \left({\mathcal {A}}_{2}\right)\times \ldots \times \triangle \left({\mathcal {A}}_{K}\right)$ представляет собой равновесие эпсилон-удовлетворения ( $\epsilon$-SE) игры $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace {\bar {f}}_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$, если для всех $k\in {\mathcal {K}}$, отсюда следует, что

${\boldsymbol {\pi }}_{k}^{*}\in {\bar {\bar {f}}}_{k}\left({\boldsymbol {\pi }}_{-k}^{*}\right)$,

где

${\bar {\bar {f}}}_{k}\left({\boldsymbol {\pi }}_{-k}^{*}\right)=\left\lbrace {\boldsymbol {\pi }}_{k}\in \triangle \left({\mathcal {A}}_{k}\right):\mathrm {Pr} \left(a_{k}\in f_{k}\left({\boldsymbol {a}}_{-k}\right)|a_{k}\sim {\boldsymbol {\pi }}_{k},{\boldsymbol {a}}_{-k}\sim {\boldsymbol {\pi }}_{-k}^{*}\right)\geqslant 1-\epsilon \right\rbrace .$

---

Из определения, приведенного выше, можно предположить, что если профиль смешанной стратегии ${\boldsymbol {\pi }}^{*}$ это $\epsilon$-SE, он утверждает, что,

$\mathrm {Pr} \left(a_{k}\in f_{k}\left({\boldsymbol {a}}_{-k}\right)|a_{k}\sim {\boldsymbol {\pi }}_{k}^{*},{\boldsymbol {a}}_{-k}\sim {\boldsymbol {\pi }}_{-k}^{*}\right)\geqslant 1-\epsilon .$

То есть игроков не устраивает вероятность $\epsilon$. Актуальность $\epsilon$-SE заключается в том, что он моделирует тот факт, что игроки могут быть терпимы к определенному уровню неудовлетворенности. При данном $\epsilon$-SE, ни один из игроков не заинтересован в изменении своего профиля смешанной стратегии, пока его устраивает вероятность выше или равная $1-\epsilon$, для некоторых $\epsilon >0$.

В отличие от условий существования СЭ как в чистой, так и в смешанной стратегиях, условия существования СЭ $\epsilon$-SE мягкие.

---

Предложение [Существование $\epsilon$- ЮВ ]
Позволять $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace f_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$, быть конечной игрой в форме удовлетворения. Тогда, если для всех $k\in {\mathcal {K}}$, всегда существует профиль действия ${\boldsymbol {a}}\in {\mathcal {A}}$ такой, что

$a_{k}\in f_{k}\left({\boldsymbol {a}}_{-k}\right)$,

тогда всегда существует профиль стратегии ${\boldsymbol {\pi }}^{*}\in \triangle \left({\mathcal {A}}_{1}\right)\times \triangle \left({\mathcal {A}}_{2}\right)\times \ldots \times \triangle \left({\mathcal {A}}_{K}\right)$ и настоящий $\epsilon$, с $1>\epsilon >0$, такой, что, ${\boldsymbol {\pi }}^{\star }$ это $\epsilon$- СЭ.

---

Выбор

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

Для всех $k\in {\mathcal {K}}$, пусть функция $c_{k}:{\mathcal {A}}_{k}\rightarrow \left[0,1\right]$ определить усилия или затраты, заплаченные игроком $k$ за использование каждого из его действий. Точнее, учитывая пару действий $(a_{k},a_{k}')\in {\mathcal {A}}_{k}^{2}$, действие $a_{k}$ предпочтительнее против $a_{k}'$ по игроку $k$ если

$c_{k}\left(a_{k}\right)<c_{k}\left(a_{k}'\right),$

Обратите внимание, что это предпочтение для игрока $k$ не зависит от действий всех остальных игроков.

---

Определение: [Эффективное равновесие удовлетворенности (ESE)]
Позволять ${\mathcal {S}}$ — множество равновесий удовлетворения в чистых стратегиях игры в форме удовлетворения $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace f_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$. Профиль стратегии ${\boldsymbol {a}}^{\star }=\left(a_{1}^{\star },a_{2}^{\star },\ldots ,a_{K}^{\star }\right)\in {\mathcal {A}}$ это эффективное равновесие удовлетворения если для всех ${\boldsymbol {a}}\in {\mathcal {A}}$, отсюда следует, что

$\sum _{k=1}^{K}c_{k}\left(a_{k}^{\star }\right)\leqslant \sum _{k=1}^{K}c_{k}\left(a_{k}\right)$.

---

В тривиальном случае, когда для всех $k\in {\mathcal {K}}$ функция $c_{k}$ является постоянной функцией, набор ESE и набор SE идентичны. Это подчеркивает актуальность способности игроков дифференцировать усилия по совершению того или иного действия с целью выбора одного равновесия (удовлетворения) среди всех существующих равновесий.

В играх в форме удовлетворения с непустыми множествами равновесий удовлетворения, когда все игроки приписывают своим действиям разные затраты, т. е. для всех $k\in {\mathcal {K}}$ и для всех $(a,a')\in {\mathcal {A}}_{k}\times {\mathcal {A}}_{k}$, он утверждает, что $c_{k}(a)\neq c_{k}(a')$, всегда существует ESE. Тем не менее, оно не обязательно уникально, а это означает, что все еще существует место для других уточнений равновесия, помимо понятия индивидуальных функций затрат.

Обобщения

Говорят, что игры в форме удовлетворения, для которых не существует профиля действий, в котором все игроки удовлетворены, не обладают равновесием удовлетворения. В этом случае профиль действия вызывает разбиение множества ${\mathcal {K}}$ образованный наборами ${\mathcal {K}}_{\mathrm {s} }$ и ${\mathcal {K}}_{\mathrm {u} }$. С одной стороны, игроки в ${\mathcal {K}}_{\mathrm {s} }$ удовлетворены. С другой стороны, игроки в ${\mathcal {K}}_{\mathrm {u} }$ недовольны. Если игроки в сете ${\mathcal {K}}_{\mathrm {u} }$ не может быть удовлетворен ни одним из своих действий, учитывая действия всех остальных игроков, эти игроки не заинтересованы в изменении своего текущего действия. Это означает, что профили действий, удовлетворяющие этому условию, также являются равновесиями. Это происходит потому, что никто из игроков не особо заинтересован в изменении своих текущих действий, даже тех, которые не удовлетворены. Это рассуждение привело к другой концепции решения , известной как равновесие общего удовлетворения (GSE).Это обобщение предлагается в контексте новой формулировки игры, а именно формы обобщенного удовлетворения.

---

Определение: [Обобщенная форма удовлетворенности]
Игра в форме обобщенного удовлетворения описывается кортежем $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace g_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$,где, набор ${\mathcal {K}}=\lbrace 1,\ldots ,K\rbrace \subset \mathrm {N}$, с $0<K<+\infty$, представляет набор игроков; набор ${\mathcal {A}}_{k}$, с $k\in {\mathcal {K}}$ и $0<|{\mathcal {A}}_{k}|<+\infty$, представляет собой набор действий, которые игрок $k$ может играть; и отображение предпочтений

$g_{k}:\prod _{j\in {\mathcal {K}}\setminus \lbrace k\rbrace }\triangle \left({\mathcal {A}}_{j}\right)\rightarrow 2^{\triangle \left({\mathcal {A}}_{k}\right)}$,

определяет набор функций массы вероятности (смешанных стратегий) с поддержкой ${\mathcal {A}}_{k}$ которые удовлетворяют игрока $k$ учитывая смешанные стратегии, принятые всеми остальными игроками.

---

Обобщенное равновесие удовлетворения определяется следующим образом.

---

Определение: [Обобщенное равновесие удовлетворенности (GSE) ]
Профиль смешанной стратегии ${\boldsymbol {\pi }}^{*}\in \triangle \left({\mathcal {A}}_{1}\right)\times \ldots \times \triangle \left({\mathcal {A}}_{K}\right)$ представляет собой обобщенное равновесие удовлетворения в игре в форме обобщенного удовлетворения. $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace g_{k}\right\rbrace _{k\in {\mathcal {K}}}\right)$ если существует раздел множества ${\mathcal {K}}$ образованный наборами ${\mathcal {K}}_{\mathrm {s} }$ и ${\mathcal {K}}_{\mathrm {u} }$ и имеет место следующее:
(и) Для всех $k\in {\mathcal {K}}_{\mathrm {s} }$, ${\boldsymbol {\pi }}_{k}\in g_{k}\left({\boldsymbol {\pi }}_{-k}\right)$; и
(ii) Для всех $k\in {\mathcal {K}}_{\mathrm {u} }$, $g_{k}\left({\boldsymbol {\pi }}_{-k}\right)=\emptyset .$

---

Обратите внимание, что GSE сводится к понятию $\epsilon$-SE игры в форме удовлетворения $\left({\mathcal {K}},\left\lbrace {\mathcal {A}}_{k}\right\rbrace _{k\in {\mathcal {K}}},\left\lbrace {\bar {f}}_{k}\right\rbrace _{k\in {\mathcal {K}}}\right),$ когда, ${\mathcal {K}}_{\mathrm {u} }=\emptyset$ и для всех $k\in {\mathcal {K}}$, переписка $g_{k}$ выбран быть

$g({\boldsymbol {a}}_{-k})={\bar {\bar {f}}}_{k}\left({\boldsymbol {\pi }}_{-k}^{*}\right),$

с $\epsilon >0$.Точно так же GSE сводится к понятию SE в смешанных стратегиях, когда $\epsilon =0$ и ${\mathcal {K}}_{\mathrm {u} }=\emptyset$. Наконец, заметим, что любая SE является GSE, но обратное неверно.