WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 48 | 49 || 51 | 52 |   ...   | 82 |

Acknowledgements The work had been performed thanks to the support of ISTC (Project B-986).

Bibliography 1. Povarov G.N. About functional decomposition of Boolean functions. – Reports of the AS of USSR, 1954. – V. 4, No 5 (in Russian).

2. Ashenhurst R.L. The decomposition of switching functions. Proc. International Symposium on the Theory of Switching, Part 1. – Harvard University Press, Cambridge, 1959, pp. 75-116.

3. Curtis H.A. Design of switching circuits. – Van Nostrand, Princeton, N. J., 1962.

4. Zakrevskij A.D. Algorithm of a Boolean function decomposition. – Annals of Siberian Physical-Technical Institute, 1964. – V. 44, pp. 5-16 (in Russian).

Author’s Information Arkadij Zakrevskij – The United Institute of Informatics Problems of the NAS of Belarus, Surganov Str. 6, 220012, Minsk, Belarus; e-mail: zakr@newman.bas-net.by XII-th International Conference "Knowledge - Dialogue - Solution" ПРИНЦИП ИНДИВИДУАЛЬНОЙ ОПТИМАЛЬНОСТИ В ИГРАХ Сергей Мащенко Abstract: A new conception of a individual-optimum equilibrium in the conditions of the complete being of players inform is offered.

Keywords: Nesh’s equilibria, Pareto optimum, а coalition equilibria, а individual-optimum equilibria.

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

Рассмотрим игру G в нормальной форме (Xi,ui ;i N), где N = {1,2,...n}- множество из n игроков; Xi - множество стратегий і-го игрока; ui (x) - функция его выигрыша, которая определена на множестве ситуаций игры X = и максимизируется.

Xi iN Наиболее привлекательными концепциями оптимальности в условиях полной информированности игроков является оптимальность по Парето и по Нешу [1].

Концепция оптимальности по Парето базируется на, так называемых, сильной и слабой аксиомах Парето [2]. Говорят, что вектор выигрыша игроков UN (x) = (ui (x))iN в ситуации х игры G доминирует вектор выигрыша UN (y) в ситуации y (обозначают это через UN (x) UN (y) ), если ui (x) ui (y), i N и хоть одно неравенство строгое, то есть j N : uj (x) > uj (y).

В соответствии со слабой аксиомой Парето вектор выигрыша игроков UN (x) = (ui (x))iN в ситуации х игры G сильно доминирует вектор выигрыша UN (y) в ситуации y (обозначают это через UN (x) UN (y) ), если ui (x) > ui (y), i N.

Ситуация x* игры G называется оптимальной по Парето (множество этих ситуаций будем обозначать через PO(G) ), если не существует ситуации, которая бы ее доминировала, то есть x* PO(G) ¬x X :UN (x) UN (x*). (1) Ситуация x* игры G называется слабо оптимальной по Парето (оптимальной за Слейтером, множество этих ситуаций будем обозначать через SO(G) ), если не существует ситуации, которая бы ее сильно доминировала, то есть x* SO(G) ¬x X :UN (x) UN (x*). (2) «Коллективная оптимальность» сильной (слабой) Парето-оптимальной ситуации является залогом того, что для всех игроков найти какую-то лучшую (сильно лучшую) ситуацию невозможно. Условия существования Парето-оптимальных ситуаций являются достаточно «слабыми» и, грубо говоря, сводятся к условиям существования максимумов функций выигрыша игроков (конечность множеств стратегий игроков или компактность множеств стратегий и непрерывность функций выигрыша). Поскольку таких ситуаций, как правило не одна [2], то возникает вопрос – которую выбрать В одних Парето-оптимальных ситуациях больший выигрыш могут иметь одни игроки, в других – другие игроки. Поэтому соглашения, которые базируются на них, являются «неустойчивыми» относительно отклонений игроков от согласованных стратегий.

218 Mathematical Foundations of AI Концепция равновесия по Нешу, базируется на принципе «собственной оптимальности». Ситуация x* называется равновесием по Нешу (множество этих ситуаций будем обозначать через NE(G) ), если:

* * i N, ui(x*) ui(xi,xN\i), xi Xi или ¬xi Xi :ui(xi,xN\i)> ui(x*). (3) Из этого определения следует, что данная ситуация является равновесием Неша, если от нее невыгодно отклоняться любому одному игроку (все другие свои стратегии не изменяют), поскольку значение его функции выигрыша не улучшается (является оптимальным для каждого игрока).

Если игроки заключают соглашение о своем будущем поведении и ее основой является равновесие Неша, то собственный оптимум является залогом «стабильности» выбранной ситуации. «Ценой» привлекательности равновесий Неша являются серьезные проблемы, которые связаны с их существованием, сложностью нахождения, проблемой выбора единственного равновесия [3].

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

Пусть Q = {N(k)} некоторое разбиение множества игроков на коалиции N(k) N, k K ;

kK N(i) N( j) =, i j ;

N(k) = N. Тогда в соответствии со слабой аксиомой Парето ситуация x* kK называется сильным коалиционным равновесием по Нешу в игре G, если:

* * k K ¬xN(k ) XN (k ) : UN (k )(xN (k ),xN\N (k )) UN (k )(xN (k ),xN\N (k )) (4) где XN (k ) =, k K, - множества коалиционных стратегий игроков; UN (k )(x) = (ui (x))iN (k ), k K, - Xi iN (k ) векторы функций выигрыша коалиций. Будем обозначать множество этих равновесий в игре G через SKNEQ(G).

Аналогично в соответствии с сильной аксиомой Парето, определяется множество WKNEQ(G) слабых коалиционных равновесий Неша в игре G :

* * WKNEQ(G) k K, ¬xN (k ) XN (k ) : UN (k )(xN (k ),xN\N (k )) UN(k )(xN (k ),xN\N(k )).

(5) Рассмотрим предельные случаи. Если коалиция одна ( K = 1), то есть она совпадает с множеством всех игроков N, то множество коалиционных равновесий Неша будет множеством оптимальных по Парето ситуаций в игре G. Если коалиций столько, сколько игроков ( K = n ) и N(i) = {i}, i N, то множество коалиционных равновесий Неша совпадет со множеством равновесий Неша.

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

На практике, например, в Парламенте процесс распределения игроков на коалиции происходит имперически. Методом проб и ошибок создаются и разрушаются те или другие коалиции. Критерием истинности в таком процессе является стабильность парламентских соглашений. В теории, XII-th International Conference "Knowledge - Dialogue - Solution" формулируются достаточно сложные комбинаторно-игровые задачи, например [4], которые позволяют найти оптимальный в том или другом понимании состав коалиций.

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

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

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

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

Сначала введем специальное отношение доминирования, которое будем называть отношением доминирования Неша.

Будем говорить, что ситуация х игры G с вектором выигрыша UN (x) = (ui (x))iN доминирует (сильно NE доминирует) по Нешу ситуацию y с вектором выигрыша UN (y) в и будем обозначать это через x y NE ( x y ), если y получается из ситуации х изменением каким-то, но одним игроком i N, своей собственной стратегии, то есть y = (yi,xN\i ) и UN (x) UN (y), таким образом:

NE x y i N : UN(xi,xN\i ) UN (yi,xN\i ), i N : UN(xi,xN\i ) UN (yi,xN\i ) NE (( x y i N : UN(xi,xN\i ) UN (yi,xN\i ) ).

Ситуацию х* будем называть сильным индивидуально-оптимальным равновесием, а их множество будем обозначать через SIOE(G), если не существует другой ситуации, которая бы доминировала ее по Нешу, то есть NE x* SIOE(G) ¬x X : x x *.

В соответствии с отношением сильного доминирования Неша определим понятие слабого индивидуально-оптимального равновесия. Ситуацию х* будем называть слабым индивидуальнооптимальным равновесием (их множество будем обозначать через WIOE(G) ), если не существует другой ситуации, которая бы сильно доминировала ее по Нешу, то есть NE x* WIOE(G) ¬x X : x x *.

Использование индивидуально-оптимальных равновесий мотивируется следующим сценарием игры. К началу игры игроки заключают необязательное соглашение (за нарушение соглашения не предусмотрена ни одна штрафная санкция) о том, что они выберут ситуацию x* = (xi *), затем независимо один от iN другого игроки принимают решение о выборе своей стратегии. В том и только том случае, если основой соглашения будет сильное (слабое) индивидуально-оптимальное равновесие, і–му игроку, отдельно, будет невыгодно выбирать стратегию отличающуюся от xi *, поскольку выигрыш свой и других игроков, чьи интересы он учитывает, не улучшится (сильно не улучшится). Лояльность (а может надежда, что 220 Mathematical Foundations of AI другие игроки поделятся выигрышем) каждого игрока по отношению к другим, будет залогом стабильности такого соглашения.

В этой работе дальше мы будем детально исследовать слабые индивидуально-оптимальные равновесия.

Интересно рассмотреть слабые индивидуально-оптимальные равновесия в предельных случаях, а также сравнить их с оптимальными по Парето, Нешевскими и коалиционными равновесиями.

Теорема 1. Справедливы включения: PO(G) SO(G) WIOE(G) ; NE(G) WIOE(G) ;

SKNEQ(G) WKNEQ(G) WIOE(G).

Доказательство. Включение PO(G) SO(G) элементарно выводится из определений (1),(2) и является известным [2].

Докажем включение SO(G) WIOE(G). Пусть x* SO(G). Предположим противное, что * * x* WIOE(G). Тогда i N, xi Xi : UN (xi,xN\i ) UN (xi,xN\i ). Отсюда следует, что по крайней мере для y = (xi,xN\i ), UN (y) UN ( x). Получаем противоречие с (2).

Докажем включение NE(G) WIOE(G). Пусть x* NE(G). Предположим противное, что * * x* WIOE(G). Тогда i N, xi Xi : UN (xi,xN\i ) UN (xi,xN\i ). Отсюда, следует что * ui(xi,xN\i)> ui(x*). Отсюда по определению (3) x* NE(G). Получили противоречие.

Пусть Q = {N(k)} некоторая разбиение множества игроков на коалиции N(k) N, k K ;

kK N(i) N( j) =, i j ;

N(k) = N. Включение SKNEQ(G) WKNEQ(G) элементарно выводится из kK определений (4), (5) и является известным [2].

Докажем включение KNEQ(G) IOEQ(G). Пусть x* KNEQ(G). Предположим от противного, что * * x* WIOE(G). Тогда i N, xi Xi : UN (xi,xN\i ) UN (xi,xN\i ). Возьмем коалицию N(k), к * которой принадлежит і-й игрок. Обозначим через yN (k ) = (xi,xN (k )\i ). Отсюда следует, что * uj(yN (k ),xN\N (k ))> uj(x*), j N(k). По определению (5) получим x* KNEQ(G). Получили противоречие.

При достаточно слабых предположениях относительно условий игры (например, конечность множеств стратегий игроков или компактность множеств стратегий игроков и непрерывность их функций выигрыша) SO(G), поэтому WIOE(G). Из теоремы 1 также видно, что WIOE(G) NE(G) SKNEQ(G) WKNEQ(G) PO(G) SO(G).

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

Теорема 2. Пусть без ограничения общности функции выигрыша всех игроков в ситуации х* принимают положительные значения, то есть ui (x*) > 0, i N. Ситуация х* будет слабым индивидуальнооптимальным равновесием тогда и только тогда, когда существуют векторы параметров i Mi + = = (ij )jN j = 1; ij > 0, j N, i N (6) i i jN такие, что ситуация х* будет равновесием Неша в следующей параметрической игре:

G() = (Xi,minijuj (x); i N).

(7) jN XII-th International Conference "Knowledge - Dialogue - Solution" Доказательство. Докажем достаточность. Пусть х* - равновесие Неша в параметрической игре (6) при некоторых значениях параметров i Mi +, i N. Отсюда следует, что для любого игрока i N и любой стратегии xi Xi имеют место неравенства: minijuj (xi,xN\i *) ikuk (x*), k N, поэтому jN существует такой игрок j N, что u (x*) u (xi,xN\i ),xi X,i N. Следовательно j j NE ¬x = (xi,xN\i ) X : x x *. Отсюда x * будет слабым индивидуально-оптимальным равновесием.

Докажем необходимость. Для этого возьмем вектор i, i N с компонентами, которые определены по j следующим формулам: i = i uj (x*), j N; i = u (x*), i N.

Pages:     | 1 |   ...   | 48 | 49 || 51 | 52 |   ...   | 82 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.