Определение решения игры

Исход можно считать оптимальным только в том случае, если он может быть реализуем в условиях, когда каждая коалиция выбирает стратегии, направленные на наиболее предпочитаемые ею исходы игры. Будем обозначать S={s} множество всех исходов коалиционной игры, X_K={x_K} множество стратегий коалиции K, S(x_K) подмножество исходов, которые могут реализоваться при использовании коалицией K стратегии x_K.

Введем следующие определения.

Определение 1. Пару (K, x_K), где X_K={x_K} непустое множество, будем называть угрозой против исхода s, если все исходы из подмножества S(x_K) более предпочтительны для коалиции K, чем исход s. Будем в этом случае говорить, что коалиция K имеет угрозу x_K против исхода s.

Определение 2. Пару (Q, x_Q), где X_Q={x_Q} непустое множество, будем называть контругрозой против угрозы (K, x_K), если Q∩ K непустое множество и существует по крайней мере один исход s’ из подмножества S(x_K), который менее предпочтителен, чем все исходы из подмножества S(x_Q). Будем в этом случае говорить, что коалиция Q имеет контругрозу x_Q на угрозу x_K коалиции K.

Определение 3. Угроза называется эффективной, если на нее нет контругрозы.

Определение 4. Оптимальными называются те исходы игры, против которых нет эффективных угроз. Множество всех оптимальным решением будем называть V-решением коалиционной игры, или просто решением игры.

Выясним содержательный смысл введенных определений. Пусть s некоторый исход. Если есть коалиция K, которая с помощью стратегии x_K может добиться исходов S(x_K), более благоприятных для нее, чем s, то она заинтересована в в том, чтобы исключить исход s из числа возможных и может это сделать с помощью стратегии x_K. Поэтому x_K является угрозой против исхода s. Но, с другой стороны, само существование коалиции K тоже может находиться под угрозой. Если существует коалиция Q, имеющая общих игроков с коалицией K, и применение коалицией Q некоторой стратегии x_Q приводит к исходам, более благоприятным для Q, чем один из исходов, к которым приводит стратегия x_K, то часть игроков из K может предпочесть участие в коалиции Q. Тогда образование коалиции Q может помешать образованию коалиции K, а значит помешать реализации угрозы x_K против исхода s. Угроза x_K в этом случае не является эффективной, и реализации исхода s ничто не мешает.

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

Пример. Парламент, состоящий из депутатов I={ a, b, c, d, e, f, g } выбирает решения из множества S ={1, 2, 3, 4, 5, 6, 7}. Депутат a предпочитает все исходы 1, 2, 3 исходу 4, и все исходы 4, 5, 6 исходу 1. Депутат a может войти в коалицию K={ a, b, c }, которая также предпочитает исходы 1, 2, 3 исходу 4, и может применить стратегию x_K, в результате которой может реализоваться один из исходов 1, 2, 3. Но a может войти в коалицию Q={ a, d, e, f, g }, которая предпочитает исходу 1 любой исход из множества исходов {5, 6, 7}, к которым приводит стратегия x_Q. Другие коалиции кроме K и Q не могут организоваться в силу личных пристрастий депутатов. Является ли исход 4 оптимальным?

Решение.

Депутат a может предпочесть войти в коалицию Q, т.к. у нее есть стратегия x_Q, исключающая неблагоприятный для a исход 1. Следовательно, коалиция K может распасться, и стратегия x_K, угрожающая решению 4 может не осуществиться. Следовательно, исход 4 нельзя исключить из числа потенциально реализуемых, т.е. оптимальных исходов.