| Математические заметки |
|
|
|
|
|
Существование состязательных множеств для кооперативных игр с нечеткими выигрышами А. С. Шведов Национальный исследовательский университет "Высшая школа экономики", г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 4, Pages DOI: https://doi.org/10.1134/S0001434623090298 
Реферативные базы данных:
 1. ВведениеВ работе [1] рассматриваются кооперативные игры, в которых коалиция, состоящая из всех игроков (большая коалиция), является слабой, а коалиции меньшего размера – более сильными, и предлагаются состязательные множества в качестве решений для таких (и не только для таких) кооперативных игр. Наибольшее распространение в литературе из состязательных множеств, предложенных в [1], получило множество, традиционно обозначаемое $\mathscr M_1^{(i)}$. То, что множество $\mathscr M_1^{(i)}$ непусто, доказывается в работе [2] (для случая, когда коалиционная структура состоит из одной большой коалиции) и в работах [3], [4] (для общего случая). (Хотя работа [1] опубликована позднее работ [2], [3], в [2] указывается, что состязательные множества введены в [1].) Для доказательства существования (непустоты) состязательного множества в работах [3], [4] используется теорема Брауэра о неподвижной точке. В настоящее время более распространенным стало другое доказательство существования состязательных множеств, не опирающееся на теоремы о неподвижных точках, хотя это доказательство и является более длинным и логически сложным, чем первоначальное доказательство. В частности, именно такое доказательство непустоты множества $\mathscr M_1^{(i)}$ приводится в книге [5]. Однако в книге [6] даются оба доказательства. Известны и другие состязательные множества, обладающие своими преимуществами перед $\mathscr M_1^{(i)}$; обзор этого научного направления можно найти, например, в [7]. Когда говорят о нечетких кооперативных играх, то имеют в виду либо игры с нечеткими выигрышами и с обычными коалициями, либо игры с нечеткими коалициями и с четкими выигрышами. Состязательные множества для игр с нечеткими коалициями и с четкими выигрышами изучаются, например, в работах [8]–[10]. В работе [11] рассматриваются состязательные множества для кооперативных игр с нечеткими выигрышами и с обычными коалициями; в этой работе доказаны теоремы, утверждающие, что для выпуклых кооперативных игр состязательные множества совпадают с ядрами; эти теоремы являются аналогами классических теорем, относящихся к четким играм. Важность рассмотрения игр с нечеткими выигрышами объясняется тем, что в реальных задачах выигрыши могут не быть известны точно. В настоящей работе дается доказательство непустоты состязательного множества $\mathscr M_1^{(i)}$ для кооперативных игр с трапецеидальными нечеткими выигрышами. Это доказательство является обобщением первоначального доказательства, основанного на применении теоремы Брауэра. В п. 2 приводятся определения, относящиеся к нечетким числам и к состязательным множествам. В п. 3 собраны леммы. В п. 4 дается основной результат. 2. Нечеткие числа и состязательные множестваПусть $A$ – это подмножество пространства $\mathbb R^4$, состоящее из точек $a=(a_1,a_2,a_3,a_4)$ таких, что $a_1\leqslant a_2\leqslant a_3\leqslant a_4$. Множество $A$ можно отождествить с множеством трапецеидальных нечетких чисел, если считать, что функция принадлежности нечеткого числа $a$ имеет следующий вид:
Существует большое число различных подходов к ранжированию нечетких чисел (см., например, [12]); в настоящей работе используются два метода ранжирования. На множестве $A$ можно ввести полное отношение порядка. Обозначим
$$
\begin{equation*}
F(a)=\lambda_1a_1+\lambda_2a_2+\lambda_3a_3+\lambda_4a_4,
\end{equation*}
\notag
$$
где $\lambda_1,\lambda_2,\lambda_3,\lambda_4$ – некоторые положительные числа. Без ограничения общности можно считать, что $\lambda_1+\lambda_2+\lambda_3+\lambda_4=1$. Для $a,b\in A$ будем использовать обозначение $a\succeq b$, если $F(a)\geqslant F(b)$, и обозначение $a\succ b$, если $F(a)>F(b)$. (В таком же смысле будем использовать обозначения $a\succeq b$, $a\succ b$ и в том случае, когда $a$ и $b$ – это четырехмерные векторы, не обязательно являющиеся нечеткими числами.) Обозначения $a\preceq b$, $a\prec b$ равнозначны обозначениям $b\succeq a$, $b\succ a$ соответственно. На множестве $A$ будем рассматривать также следующее частичное отношение порядка. Для точек $a=(a_1,a_2,a_3,a_4)$ и $b=(b_1,b_2,b_3,b_4)$, принадлежащих множеству $A$, будем использовать обозначение $a\unrhd b$, если
$$
\begin{equation*}
a_1\geqslant b_1,\qquad a_2\geqslant b_2,\qquad a_3\geqslant b_3,\qquad a_4\geqslant b_4.
\end{equation*}
\notag
$$
Равенство $a=b$ понимается в обычном смысле, т.е. при совпадении всех координат. Через $a+b$ обозначается точка $(a_1+b_1,\,a_2+b_2,\,a_3+b_3,\,a_4+b_4)$. Через $a-b$ обозначается точка $(a_1-b_1,\,a_2-b_2,\,a_3-b_3,\,a_4-b_4)$. Отметим, что из $a,b\in A$ следует, что $a+ b\in A$, но не следует, вообще говоря, что $a-b\in A$. Пусть $N=\{1,2,\dots,n\}$ – множество игроков. В дальнейшем через $x$, $y$, $z$ обозначаются точки множества $A^n$, т.е. наборы, состоящие из $n$ нечетких чисел. Таким образом, $x=(x_1,\dots,x_n)$, где $x_k\in A$ при $k=1,\dots,n$. При $S\subseteq N$, $x\in A^n$ через $x^S$ обозначается поднабор набора $(x_1,\dots,x_n)$, состоящий из нечетких чисел $x_k$ таких, что $k\in S$. Множество всех таких поднаборов, отвечающих всевозможным $x\in A^n$, обозначается $A^S$. Когда нужно дать полное описание нечеткого числа $x_k$, используется запись $x_k=(x_{k,1},x_{k,2},x_{k,3},x_{k,4})$; такая же запись используется и для других нечетких чисел $y_k$, $z_k$ и т.д., относящихся к игроку $k$. Игра считается заданной, если определена характеристическая функция, т.е. каждой коалиции $S\subseteq N$ поставлено в соответствие нечеткое число $v(S)$. Вместо $v(\{k\})$ используется обозначение $v_k$. В работе накладывается условие при любом $k\in\mathbb N$.Определение 1. Коалиционная структура – это разбиение множества $N$ на коалиции (подмножества) $P_1,\dots,P_m$. При $j=1,\dots,m$ определим следующее подмножество множества $A^{P_j}$:
$$
\begin{equation*}
\Lambda_j=\biggl\{x^{P_j}\colon x_k\unrhd v_k\text{ при любом }k\in P_j,\, \sum_{k\in P_j}x_k=v(P_j)\biggr\}.
\end{equation*}
\notag
$$
Будем предполагать, что при любом $j$ множество $\Lambda_j$ непустое. Например, это условие выполняется, если $v_{k,l}=0$ при любых $k\in \mathbb N$, $l=1,2,3,4$, а носители всех нечетких чисел $v(P_j)$ принадлежат множеству неотрицательных действительных чисел $\mathbb R_+$. Положим $X=\Lambda_1\times\dotsb\times\Lambda_m$. Пусть игроки $\nu$ и $\mu$ входят в одну коалицию $P_j$. Через $\mathscr T_{\nu\mu}$ обозначается множество коалиций $S\subset N$, в которые входит игрок $\nu$, но не входит игрок $\mu$. Пусть $x\in X$. Определение 3. Возражением игрока $\nu$ против игрока $\mu$ при $x$ называется набор $y^S\in A^S$, где $S\in\mathscr T_{\nu\mu}$, если выполняются следующие условия: Контрвозражением к данному возражению называется набор $z^T\in A^T$, где $T\in \mathscr T_{\mu\nu}$, если выполняются следующие условия: Определение 4. Игрок $\nu$ влиятельнее игрока $\mu$ при $x$, если у игрока $\nu$ есть возражение против игрока $\mu$ при $x$ такое, что у игрока $\mu$ нет контрвозражения к этому возражению. Определение 5. Состязательное множество – это множество профилей платежей $x\in X$ таких, что при этих $x$ не существует игрока, который был бы влиятельнее какого-то другого игрока из своей коалиции. 3. Вспомогательные результатыПусть множество $E_k$, $k\in\mathbb N$, состоит из профилей платежей $x\in X$ таких, что при этих $x$ не существует игрока, который был бы влиятельнее, чем игрок $k$. Сходимость нечетких чисел, т.е. элементов множества $A\subset\mathbb R^4$, понимается как обычная сходимость в евклидовом пространстве $\mathbb R^4$. Так же понимается сходимость элементов множества $A^n$ как сходимость в пространстве $\mathbb R^{4n}$. Доказательство. Ограниченность множества $E_k$ очевидна; поэтому доказать нужно только то, что это множество замкнутое. Предположим, что множество $E_k$ не является замкнутым. Тогда существует последовательность точек $x(i)\in E_k$ такая, что $x\notin E_k$. Это означает, что существует игрок $\nu$, который влиятельнее игрока $k$ при $x$. Пусть $y^S$, где $S\in\mathscr T_{\nu k}$, – возражение игрока $\nu$ против игрока $k$ при $x$ и для этого возражения у игрока $k$ нет контрвозражения. Тогда Очевидно, что коалиция $S$ не может состоять из одного игрока $\nu$, тогда должно было бы выполняться условие $y_\nu=v_\nu$, и не могло бы выполняться условие $y_\nu\succ x_\nu$.
Пусть $\varepsilon=y_\nu-x_\nu$, $F(\varepsilon)>0$. Положим тогда Будем рассматривать те $i$, при которых выполняется условие где $|S|$ – число игроков в коалиции $S$. Пусть $e=(1,1,1,1)$ – вектор пространства $\mathbb R^4$. Очевидно, что $F(e)=1$. Рассмотрим набор $w(i)^S$ следующего вида:
$$
\begin{equation*}
w(i)_\nu=y_\nu-\alpha(i)(|S|-1)e,\qquad w(i)_k=y_k+\alpha(i)e\quad \text{при}\ \ k\in S,\quad k\ne\nu.
\end{equation*}
\notag
$$
Очевидно, что Далее,
$$
\begin{equation*}
\begin{aligned} \, F(w(i)_\nu-x_\nu) &=F(y_\nu-x_\nu)-\alpha(i)(|S|-1)>\frac{F(\varepsilon)}{2}\,, \\ F(x(i)_\nu-x_\nu) &\leqslant\alpha(i)<\frac{F(\varepsilon)}{2}\,. \end{aligned}
\end{equation*}
\notag
$$
Поэтому
$$
\begin{equation*}
F(w(i)_\nu-x(i)_\nu)=F(w(i)_\nu-x_\nu)-F (x(i)_\nu-x_\nu)>0.
\end{equation*}
\notag
$$
При $k\in S$, $k\ne\nu$
$$
\begin{equation*}
F(w(i)_k-x_k) =F(y_k-x_k)+\alpha(i)\geqslant\alpha(i), \qquad F(x(i)_k-x_k) \leqslant\alpha(i).
\end{equation*}
\notag
$$
Поэтому
$$
\begin{equation*}
F(w(i)_k-x(i)_k)=F(w(i)_k-x_k)-F(x(i)_k-x_k)\geqslant 0.
\end{equation*}
\notag
$$
Это означает, что набор $w(i)^S$ является возражением игрока $\nu$ против игрока $k$ при $x(i)$. К этому возражению у игрока $k$ есть контрвозражение $z(i)^T$, где $T\in\mathscr T_{k\nu}$. (Коалиция $T$, вообще говоря, зависит от $i$. Однако, переходя к подпоследовательности, можно считать коалицию $T$ не зависящей от $i$.) Таким образом,
$$
\begin{equation*}
z(i)_k\succeq x(i)_k\quad \text{при}\ \ k\in T,\qquad z(i)_k\succeq w(i)_k\quad \text{при}\ \ k\in S\cap T.
\end{equation*}
\notag
$$
Отсюда следует, что
$$
\begin{equation*}
z(i)_k\succeq x_k-\alpha(i)e\quad \text{при}\ \ k\in T,\qquad z(i)_k\succeq y_k+\alpha(i)e\quad \text{при} \ \ k \in S \cap T.
\end{equation*}
\notag
$$
Выбирая из ограниченной последовательности $z(i)^T$ сходящуюся подпоследовательность, получаем, что ее предел является контрвозражением к возражению $y^S$ при $x$.
Лемма 1 доказана. Замечание 1. При любом $k\in\mathbb N$ если для профиля платежей $x$ выполняется условие $x_k=v_k$, то $x\in E_k$. Действительно, контрвозражением игрока $k$ к любому возражению является набор $z^T$, где $T=\{k\}$, $z_k=v_k$. То есть никакой игрок не может быть влиятельнее игрока $k$. Лемма 2. Для любого $x\in X$ и для любой коалиции $P_j$ существует игрок $k\in P_j$ такой, что $x\in E_k$. Доказательство. Если в коалиции $P_j$ всего один игрок, то множество $\Lambda_j$ состоит из одного нечеткого числа $v_k$. Тогда $x\in E_k$ на основании замечания 1. Предположим, что в коалиции $P_j$ больше одного игрока. Пусть $k_1,\dots,k_r$ – игроки из коалиции $P_j$. Предположим, что игрок $k_1$ влиятельнее игрока $k_2$ при $x$, игрок $k_2$ влиятельнее игрока $k_3$ при $x,\dots$, игрок $k_{r-1}$ влиятельнее игрока $k_r$ при $x$, игрок $k_r$ влиятельнее игрока $k_1$ при $x$. Обозначим $k_0=k_r$, $k_{r+1}=k_1$. Пусть $y^{U_h}$ – возражение игрока $k_h$ против игрока $k_{h+1}$ при $x$, $h=0,1,\dots,r$, для которого у игрока $k_{h+1}$ нет контрвозражения.
Для любой коалиции $S$ рассмотрим четырехмерный вектор (этот вектор называется эксцессом коалиции $S$ при $x$). Пусть $U_g$ – коалиция с максимальным значением $F(e(U_h))$ среди $U_0,U_1,\dots,U_r$ (или одна из этих коалиций, если таких коалиций несколько). Обозначим $U_g$ через $T$. По определению возражения $k_g\in T$.Утверждается, что $k_{g-1}\in T$. Предположим, что $k_{g-1}\notin T$ и обозначим через $S$ коалицию $U_{g-1}$. Утверждается, что следующий набор $z^T$ является контрвозражением игрока $k_g$ к возражению $y^S$ игрока $k_{g-1}$:
$$
\begin{equation*}
z_k=x_k\quad \text{при}\ \ k\in T\setminus S,\qquad z_k=y_k\quad \text{при}\ \ k\in T\cap S.
\end{equation*}
\notag
$$
Воспользовавшись тем, что $F(a+b)=F(a)+F(b)$ для любых $a,b\in\mathbb R^4$, имеем
$$
\begin{equation*}
\begin{aligned} \, \sum_{k\in T}z_k &=\sum_{k\in T}x_k+\sum_{k\in T\cap S}(y_k-x_k) =v(T)-e(T)+\sum_{k\in T\cap S}(y_k-x_k) \\ &\preceq v(T)-e(S)+\sum_{k\in S}(y_k-x_k) \preceq v(T)-e(S)+v(S)-\sum_{k\in S}x_k=v(T). \end{aligned}
\end{equation*}
\notag
$$
Таким образом, $k_{g-1}\in T$. Аналогично, обозначая через $S$ коалицию $U_{g-2}$, устанавливаем, что $k_{g-2}\in T$ и т.д. вплоть до $k_{g+1}\in T$. Но последнее включение невозможно, поскольку $y^T$ – это возражение игрока $k_g$ против игрока $k_{g+1}$. Таким образом, невозможно, чтобы для любого игрока, входящего в коалицию $P_j$, нашелся игрок, который был бы влиятельнее его при $x$.
Лемма 2 доказана. При доказательстве основной теоремы используется функция $\varphi$ следующего вида. Пусть $\gamma$ – неотрицательное число, $a=(a_1,a_2,a_3,a_4)$ – точка, принадлежащая множеству $A$, $a_1\geqslant 0$. Функция $\varphi$ ставит в соответствие точке $a$ и числу $\gamma$ точку $c=(c_1,c_2,c_3,c_4)$ следующего вида: где $s(\gamma)=(2/\pi)\operatorname{arctg}\gamma$.Замечание 2. Нетрудно увидеть, что $\varphi(a;\gamma)\in A$, $a-\varphi(a;\gamma)\in A$, носители нечетких чисел $\varphi(a;\gamma)$ и $a-\varphi(a;\gamma)$ принадлежат множеству $\mathbb R_+$, $a\unrhd\varphi(a;\gamma)$ при любых $a$ и $\gamma$ из области определения функции $\varphi$. 4. Основная теоремаУтверждение следующей теоремы означает непустоту состязательного множества. Доказательство. При $x\in X$, $k\in\mathbb N$ обозначим через $\rho(x,E_k)$ евклидово расстояние от точки $x$ до множества $E_k$. На основании леммы 1 для $x\notin E_k$ выполняется условие $\rho(x,E_k)>0$.
Рассмотрим профиль платежей $x=(x_1,\dots,x_n)$ и введем обозначение $u_k=x_k- v_k$, $k\in\mathbb N$. Пусть функция $f$ ставит в соответствие профилю платежей $x$ набор четырехмерных векторов $y_1,\dots,y_n$, где при $k\in P_j$
$$
\begin{equation*}
y_k=v_k+u_k-\varphi(u_k;\rho(x,E_k))+\sum_{\nu\in P_j} \frac{\varphi(u_\nu;\rho(x,E_\nu))}{|P_j|}\,,
\end{equation*}
\notag
$$
$|P_j|$ – число игроков в коалиции $P_j$. Очевидно, что при $j=1,\dots,m$. В силу замечания 2 при любом $k\in\mathbb N$ выполняются следующие условия: Таким образом, $f\colon X\to X$. Очевидно, что $f$ является непрерывной функцией.
Поскольку $X$ – это компактное выпуклое множество, применима теорема Брауэра о неподвижной точке, т.е. существует точка $x^0\in X$ такая, что $f(x^0)=x^0$. Предположим, что $x^0\notin E_k$ при некотором $k\in\mathbb N$. Пусть $k\in P_j$. В силу замечания 1 коалиция $P_j$ не может состоять из одного игрока, в этом случае должно быть $x_k^0=v_k$. На основании леммы 2 существует игрок $\nu\in P_j$ такой, что $x^0\in E_\nu$. Следовательно, $\rho(x^0,E_\nu)=0$. Значит,
$$
\begin{equation*}
\varphi(u_\nu^0;\rho(x^0,E_\nu))=0, \qquad \text{где}\quad u_\mu^0=x_\mu^0-v_\mu \quad \text{при любом}\ \ \mu\in P_j.
\end{equation*}
\notag
$$
Имеем
$$
\begin{equation*}
x_\nu^0=x_\nu^0-\varphi(u_\nu^0;\rho(x^0,E_\nu)) +\sum_{\mu\in P_j}\frac{\varphi(u_\mu^0;\rho(x^0,E_\mu))}{|P_j|} \succeq x_\nu^0+\frac{\varphi(u_k^0;\rho(x^0,E_k))}{|P_j|}\,.
\end{equation*}
\notag
$$
Однако точка $u_k^0$ ненулевая, иначе на основании замечания 1 имело бы место включение $x^0\in E_k$. С учетом того, что $\rho(x^0,E_k)>0$, получаем что является противоречием.
Теорема доказана. 
Цитирование в формате AMSBIB
\RBibitem{Shv23} |
|
||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|