WWW.DISSERS.RU

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

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

Pages:     | 1 |   ...   | 49 | 50 || 52 | 53 |   ...   | 82 |

kN k Отметим, что i Mi + i N. Из того, что x * - слабое индивидуально-оптимальное равновесие NE следует, что ¬x X : x x *, то есть i N, j N : uj(x*) uj(xi,x *N\i ), а значит j j j i ui(x*) iu (xi,x *N\i ). Поскольку iuj(x*) = i = j u (x*) = const, то любого игрока i N и kN k j k для любой стратегии xi Xi имеют место неравенства: miniuj (xi,xN\i ) i uk (x), k N.

jN Поэтому х* - равновесие при Нешем параметрической игре (6).

Проблема выбора индивидуально-оптимальных равновесий Теорема 2 дает возможность конструктивно описать множества NE(G), WKNEQ(G), SO(G), WIOE(G) как решения параметрической игры следующим образом.

i j 1) x NE(G) x NE(G()) при 0; 1, j i; i N. Поскольку величина i i j j 1, 1 (1,), характеризует приоритет функции выигрыша j-го игрока в предпочтении і-го на i i множестве всех игроков, указанные условия означают, что каждого игрока интересует лишь собственный выигрыш, выигрыши других он не учитывает.

k j 2) x WKNEQ(G) x NE(G()) при 0, k N(ki ) ; 1, j N \ N(ki ); i N, где i i N(ki ) - коалиция, к которой принадлежит і -й игрок, i N. В этом случае каждого игрока интересует лишь выигрыш членов его коалиции, выигрыши других он не учитывает.

i i 3) x SO(G) x NE(G()) при =, j,k N; i N. В этом случае каждый игрок j k учитывает интересы всех других, но приоритеты всех игроков по отношению к і-му одинаковы, i N.

4) x WIOE(G) x NE(G()) при произвольных векторах параметров i Mi +, i N. В этом случае каждый игрок учитывает интересы всех других с произвольными приоритетами.

i i Особенную роль играют параметры, i N, которые характеризуют приоритет 1 (1,) i i собственной функции выигрыша игрока по отношению к функциям выигрыша других игроков.

Допустим для простоты исследования, что приоритеты функций выигрыша всех игроков, с которыми считается і для него одинаковые и множества NE(G), WKNEQ(G), SO(G), WIOE(G) непустые. Тогда при i i 0, i N, получим NE(G) = NE(G()). При большем значении = N(ki ), i N, где i i 0, а ki - номер коалиции, в состав которой входит і-й игрок, получим WKNEQ(G) = NE(G()), при i чем чем больше коалиция, тем больший весовой коэффициент и соответственно меньший приоритет i i собственного критерия игрока і. При еще большем значении = N, i N, 0, будут еще i 222 Mathematical Foundations of AI i большие весовые коэффициенты, i N и соответственно меньшие приоритеты собственных i критериев игроков, тогда мы получим SO(G) = NE(G()).

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

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

Для произвольной ситуации x X сформулируем следующую оптимизационную задачу относительно весовых коэффициентов ij; j N, в которой ситуация x X выступает как параметр:

min(x) = inf max i i (8) iN minijuj (x) minijuj (yi,xN\i ), yi Xi, i N (9) jN jN j = 1; ij 0; i, j N i (10) jN Ограничение (9) описывают по определению (3) условия существования равновесия Неша для параметрической игры G( ). Ограничения (10) обеспечивают условие i Mi +, i N. На основании теоремы 2 x WIOE(G), тогда и только тогда, когда система ограничений (9),(10) будет совместной.

Если ситуация x WIOE(G), будем считать min(x) = 1. Величина min(x) будет точной нижней границей гарантированного уровня толерантности всех игроков достаточным для того, чтобы ситуация x X была индивидуально-оптимальным равновесием, и будет оценкой уровня ее «стабильности».

Отображение min : X [0,1] будем называть критерием толерантности. Индивидуально-оптимальное равновесие x* игры G, которое обеспечивает min(G) min(x), то есть минимизирует критерий xWIOE толерантности, может быть рекомендовано игрокам как основа для стабильного соглашения.

Этот подход является особенно актуальным, когда в игре G не существует равновесий Неша. Тогда x* будет «наиболее стабильным» индивидуально-оптимальным равновесием (возможно коалиционным равновесием, возможно Парето-оптимальным).

Например, рассмотрим игру двух лиц. Первый игрок хочет продать товар второму игроку, при этом может назначить как высокую цену (ВЦ), так и низкую (НЦ). Второй игрок может купить товар (К) или нет (НК).

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

К НК 2 -ВЦ -1 1 НЦ 2 XII-th International Conference "Knowledge - Dialogue - Solution" В этой игре нет равновесий Неша, но есть две индивидуально-оптимальные ситуации (ВЦ,К) и (НЦ,К), которые оптимальны по Парето. Наиболее стабильным индивидуально-оптимальным равновесием является ситуация (НЦ,К), которая может быть рекомендована игрокам как основа соглашения. Таким образом продавцу целесообразно не гнаться за сверхприбылями и продавать товар но низкой цене, покупателю рекомендуется не отказываться от покупки.

Заключение Следует заметить, что понятие стабильности равновесий является достаточно сложным и многоаспектным (более или менее в полной мере оно исследовано в работах лауреатов Нобелевской премии по экономике за 1994 год Дж. Харшаньи и Р. Зельтеном [2]) и связано, в основном, с выбором единственного равновесия из множества равновесий Неша на основе критериев эффективности по выигрышу и эффективности по риску. Описанный выше подход предлагает новую (более широкую) модель выбора равновесий с возможностью использования наряду с критериями эффективности по выигрышу и риску критерия толерантности.

Ссылки [1] Мулен Э. Теория игр с примерами из математической экономики. –М.: Мир, 1985. [2] Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. –М.: Наука, 1982. [3] Харшаньи Дж., Зельтен Р.

Общая теория выбора равновесия в играх. –Санкт-Петербург: Экономическая школа, 2001.

[4] Бухтояров С.Е., Емеличев В.А. Конечные коалиционные игры: параметризация принципа оптимальности(«вот Парето до Неша») и устойчивость обобщенно еффективных ситуаций//Докл. НАН Беларуси.-2002.-46, N6.С.36-38.

Информация об авторе Мащенко Сергей Олегович – Киевский национальный университет имени Тараса Шевченко, Доцент;

Проспект академика Глушкова, 6, Киев – 207, Украина; e-mail: msomail@yandex.ru ФОРМАЛИЗАЦИЯ СТРУКТУРНЫХ ОГРАНИЧЕНИЙ СВЯЗЕЙ В МОДЕЛИ „СУЩНОСТЬ-СВЯЗЬ” Дмитрий Буй, Людмила Сильвейструк Резюме: Рассматриваются и формализируются в терминах теории отношений такие основные понятия модели „сущность-связь”: сущности, связи, структурные ограничения связей (показатель кардинальности, степень участия, структурные ограничения вида (min, max)). Для бинарных отношений введены два оператора min, max, в терминах которых задаются указанные структурные ограничения; приведена основная теорема о совместности значений этих операторов на исходном отношении и отношении, обратном к нему.

Ключевые слова: сущность, связь, показатель кардинальности, степень участия, структурное ограничение вида (min, max).

ACM классификация ключевых слов: E.4 Сoding and information theory – Formal models of communication 224 Mathematical Foundations of AI Введение Моделирование данных – это процесс создания логического представления структуры базы данных.

Существуют разные подходы к моделированию данных, каждый из которых имеет своих поклонников.

Одна из таких моделей – ER-модель (Entity-Relationship model, модель „сущность-связь”). Эта модель стала традиционной и наиболее популярной.

Данную модель предложил в 1976 г. Питер Чен [Chen P., 1976]. Нужно отметить, что модель постоянно расширяется и модифицируется. Кроме того, модель „сущность-связь” вошла в состав многих CASEинструментов, которые также внесли свой вклад в ее эволюцию. Последние исследования в области ERмоделирования приведены, например, в работах К. Батини, С. Кэрри и Б. Зелхема [Batini Carlo, Ceri S., Navathe S.B. and Batini Carol, 1991; Thelheim B., 2000].

На сегодняшний день не существует единственного общепринятого стандарта для ER-модели, но имеется набор общих конструкций, которые лежат в основе большинства её вариантов [Гарсиа-Молина Г., Ульман Дж., Уидом Дж., 2004, гл. 2; Дейт Дж., 1998, часть ІІІ, гл. 14; Коннолли Т., Бегг К., Страчан А., 2000, часть ІІ, гл. 5; Крёнке Д., 2003, часть ІІ, гл. 3].

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

Сущности и связи Ключевыми понятиями модели „сущность-связь” являються сущности, атрибуты и связи.

Следует отметить, что понятия модели не имеют общепринятой и четкой интерпретации; более того, существует существенный терминологический разнобой; поэтому приведем в следующей таблице все варианты, встречающиеся в литературе.

Табл. 1 – Ключевые понятия ER-модели и их названия Понятие 1 вариант 2 вариант 3 вариант 4 вариант (содержательное объяснение) Сущность (состоит из своих Множество Тип Класс экземпляров; содержит, порождает Тип сущности сущности сущности сущности свои экземпляры) Экземпляр сущности (принадлежат Экземпляр Экземпляр Экземпляр своей сущности, порождаются своей Сущность сущности сущности сущности сущностью) Атрибут Свойство Атрибут Атрибут Атрибут Связь (состоит из своих экземпляров;

содержит, порождает свои Тип связи Связь Тип связи Класс связи экземпляры) Экземпляр связи (принадлежат своей Экземпляр Экземпляр Экземпляр Связь связи, порождаются своей связью) связи связи связи [Гарсиа- [Коннолли T., [Дейт Дж., Молина Г., Бегг К., [Крёнке Д., Источник 1998, Ульман Дж., Страчан А., 2003, ч. ІІ, гл. 3] ч. ІІІ, гл. 14] Уидом Дж., 2000, ч. ІІ, 2004, гл. 2] гл. 5] Далее будем придерживаться 3-го варианта.

XII-th International Conference "Knowledge - Dialogue - Solution" Сущности. Тип сущности будем интерпретировать как множество, а сущность – как элемент этого множества.

Связи. Содержательно, связь это ассоциация между n сущностями, которые называются ее участниками.

Число участников связи называется степенью связи (relationship degree) или арностью связи. Отдельные связи формируют тип связи, причем арность всех связей одного типа связи одинаковая; таким образом, арность является характеристикой типа связи. Здесь полная аналогия с арностью логико-математических отношений и количеством компонент кортежей, из которых (кортежей) состоит отношение.

Рассмотрим бинарные связи. Бинарная связь в общем случае способна соединить любую сущность одного типа сущности с любой сущностью другого типа сущности, в частности, с любой сущностью того же типа сущности (в частности, бинарная связь может соединить сущность саму с собой; здесь полная аналогия с рефлективностью бинарных отношений; отметим также, что для таких связей иногда используется явно неудачный термин „рекурсивная связь”).

Типы связей будем уточнять в виде (конечноарных) логико-математических отношений; в частности, типы бинарных связей – в виде бинарных отношений.

Показатель кардинальности. В модели существуют стандартные ограничения, которые накладываются на типы связи. Одно из таких ограничений – показатель кардинальности. Показатель кардинальности (index cardinality), содержательно говоря, задает количество возможных связей для каждой сущности-участницы связи; если говорить более точно, то этот показатель задает количество сущностей, ассоциируемых с фиксированной сущностью. Заметим, что употребление термина „кардинальность”, учитывая финитность модели, в данном контексте явно неудачное.

Среди бинарных типов связи выделяют типы связи с показателями кардинальности „один к одному” (1:1), „многие к одному” (М:1), „один ко многим” (1:М) и „многие ко многим” (М:N).

Допустим, что R – тип связи, которая соединяет типы сущностей E и F. Для адекватной формализации показателя кардинальности типы сущностей E и F будем интерпретировать как множества E и F соответственно, а тип связи R – как бинарное отношение R, причем R EF (порядок множеств в -декартовом произведении существенен). Как обычно R F E – отношение, обратное к R.

В табл. 2 показана взаимосвязь между показателями кардинальности типа связи и свойствами функциональности бинарных отношений R, R-1.

Табл. 2 – Взаимосвязь между показателем кардинальности и функциональностью бинарных отношений, а также значениями оператора max Отношение R R функциональное R не функциональное R – „многие к одному” (М:1), которая направлена от F к E R – „один к одному” (1:1) R – „один ко многим” (1:M), R-1 функциональное которая направлена от E к F 2 max(R) -max(R) 1 max(R ) -max(R ) Отношение R-R – „многие к одному” (М:1), которая направлена от E к F R – „многие ко многим” (М:N) R – „один ко многим” (1:M), R-1 не функциональное которая направлена от F к E max(R) 1 2 max(R) 2 max(R-1) 2 max(R-1) 226 Mathematical Foundations of AI Как видно, тип связи вида „один к одному” будет, когда оба отношения R, R-1 функциональные; тип связи вида „один ко многим” (эквивалентно „многие к одному”) – когда в точности одно из этих отношений функциональное; и, наконец, тип связи вида „многие ко многим” – когда оба эти отношения не функциональны.

Таким образом, можно сделать вывод: ограничение „один ко многим” („многие к одному”) связано с функциональностью (эквивалентно: с инъективностью); „один к одному” – с одновременной функциональностью и инъективностью; наконец „многие ко многим” – с бинарными отношениями общего вида. Здесь нужно учесть очевидную логическую связь между функциональностью и инъективностью:

бинарное отношение функциональное тогда и только тогда, когда обратное отношение инъективное (см., например [Буй Д. Б., Кахута Н. Д., 2005, утверждение 1]).

Pages:     | 1 |   ...   | 49 | 50 || 52 | 53 |   ...   | 82 |



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

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