автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Кооперативные игры с интервальной характеристической функцией

• ГГ) , • о 3 ФЕВ

На правах рукописи

ЛАРИНА Ольга Викторовна

КООПЕРАТИВНЫЕ ИГРЫ С ИНТЕРВАЛЬНОЙ ХАРАКТЕРИСТИЧЕСКОЙ ФУНКЦИЕЙ

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1997

Работа выполнена в Московском педагогическом государственном университете имени В.И. Ленина на кафедре информатики и дискретной математики.

Научный руководитель:

академик Международной Академии информатизации, доктор физико-математических наук, профессор ГОРЕЛИК В А.

Официальные оппоненты:

доктор физико-математических наук, профессор ЖУКОВСКИЙ В.И.

кандидат физико-математических наук

Ведущая организация: Московский Государственный Университет имени МБ. Ломоносова.

на заседании Диссертационного Совета К 053.01.16 в Московском педагогическом государственном университете имени В.И. Ленина по адресу: 107140, Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ имени В.И. Ленина, ауд. 301.

Сдиссертацией можно ознакомиться в библиотеке МПГУ имени В .И. Ленина по адресу: 119435, Москва, Малая Пироговская уд, д. 1.

Автореферат разослан «.. года.

МОХОНЬКО Е.З.

£часов

Ученый секретарь Диссертационного Совета КУЗНЕЦОВ Э.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Практическое значение теории игр было обосновано еще е середине XX века в монографии Джона фон Неймана и Оскарг Моргенштерна и развито в работах их последователей. Большое внимание в этих работах уделено кооперативным играм п лиц.

Классически принято рассматривать кооперативную игру п лиц е форме характеристической функции. Пусть имеется множество игрокоЕ N=(1,2,... ,п). Игроки могут образовывать всевозможные коалиции 3, выбирать совместно стратегии, составлять взаимообязывающие соглашения и даже выплачивать побочные платежи в виде компенсаций за участие в коалициях. При этом каждой коалиции 5 из множества всех коалиций ставится в соответсвие тот максимальный выигрыш 1>{Б), который могут гарантировать себе в сумме все члены коалиции г? независимо от действий остальных игроков.

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

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

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

упрощенности и ограниченности математических моделей реальных конфликтов.

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

Интервальная суша выигрыша имеет смысл при наличии чеопрвдоленных факторов, неполноте информации и т.д.

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

неопределенные факторы, появляющиеся из-за недостаточной зученности каких-либо процессов или величин; ) неопределенные факторы, отражающие нечеткость знания цели перации или критерия эффективности;

) технические информационные неопределенные факторы: еопределенности, возникающие в процессе сбора, переработки и эредачи информации.

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

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

Объектом исследования является теория кооперативных игр п

лиц.

Предмет исследования- кооперативные игры п лиц с интервальной характеристической функцией.

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

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

Для реализации поставленной цели и проверки сформулированной выше гипотезы потребовалось решить следующие задачи:

- ввести понятие интервальной характеристической функции в кооперативной игре п лиц;

- определить понятие допустимого дележа, как исходного в разумном распределении выигрыша,

- рассмотреть кооперативные игры п лиц с интервальной характеристической функцией в (О,^-редуцированной форме;

- получить необходимые и достаточные условия существования множества дележей для таких игр с использованием (q-Q)~ покрытий;

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

Методологическую основу работы составляют современные методы теории игр, математического программирования, теории исследования операций, некоторые теоремы о линейных неравенствах.

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

характеристической функцией; приводятся к (0,1J-редуцированной форме и используются (q-Q)-покрытия для получения условий непустоты множества допустимых дележей, что приводит к специфическим задачам линейного программирования.

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

Рассматривается исходная игра как двухкритериальная. Разумный исход такой, игры естественно искать среди парето-олтимальных точек. Ядро определяется на основе функции эксцесса, которая в свою очередь определяется как расстояние до парето-оптимадьной точки. Используются метод суммирования с весовыми коэффициентами и минимаксный метод с весовыми коэффициентами.

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

Основные положения, выносимые на защиту: - кооперативную игру можно и целесообразно задавать с помощью >трезка возможных значений характеристической функции; при этом юновной задачей остается установление возможных выигрышей [троков;

■ каждая кооперативная игра с интервальной характеристической >ункцией, удовлетворяющая некоторому условию, стратегически квивалентна одной и только одной игре в (0,1^-редуцированной орме, а у последней существует дэлэж при выполнении пределенных условий;

для кооперативной игры с интервальной характеристической ункцией определяются разные вида решений, с использованием эклассических представлений U и N-ядер.

Апробация работы. Результаты исследования были представлены з III Международной конференции женщин- математиков (Воронеж, 29

мая- 2 июня 1995 года), на III Международной конференции "Компьютерные программы учебного назначения" (Донецк, 27-29 августа 1996 года), докладывались на научно- методическом семинаре кафедры информатики и дискретной математики МИГУ им. В.И.Ленина, на аспирантском объединении.

Структура и объеи диссертации. Работа состоит из введения, четырех глав, заключения и списка литературы, содержащего 95 источников. Всего 1Щ страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе (§§1.1-1.3) дается общее описание классической кооперативной игры, обосновывается идея перехода от кооперативной игры в форме характеристической функции к кооперативной игре с интервальной характеристической функцией.

§1.1 посвящен описанию классической кооперативной игры, ее определению, проблематике, видам решений.

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

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

Если первоначально игра задана в нормальной форме и игроки применяют только чистые стратегии, то

v(S)= Ш min ?. F,(x.,...,x ) ,

(x^icS) fxjtj<iN\S} ieS 1 1 n

где F{(x1.....xn)~ функция выигрыша 1-го игрока в ситуации

(х1, ...), сложившейся в результате выборов стратегий всеми

игроками (i-Tji}.

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

Опре^елеще 1.2.1. Интервальной характеристической функцией (ИХФ) игры п лиц называется отображение v(S), ставящее в соответствие любой коалиции Se л* отрезок, из которого может тринимать значение суммарный выигрыш игроков данной коалиции

v(S): S - (v(S),v(S)l, ■\це у es;-наибольшее значение выигрыша, который могут гарантировать себе в сумме все члены коалиции S независимо от действий остальных игроков; yf.^-наименьшее значение выигрыша, соторое могут гарантированно позволять коалиции S остальные [гроки.

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

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

Определение 1.3.I. Допустимым дележом для кооперативной игры форме ИХФ назовем вектор z=(z1,...,zn), удовлетворяющий словиям:

v(S) « 2 z, < v(S) VSi2n . i€S 1

Так как в отличие от дележа в классической кооперативной гре, допустимый дележ в игре с интервальной характеристической ¡щкцией может не существовать, во второй главе (§§2.1, 2.2) эссматриваются необходимые и достаточные условия непустоты

множества допустимых дележей для кооперативной игры в форме интервальной характеристической функции.

В §2.1 вводятся основные обозначения и дана формулировка теоремы о существовании множества допустимых дележей.

Договоримся обозначать различные коалиции буквами S,R,H,l и рассмотрим три вида разбиения произвольных коалиций на подкоалиции:

1) vseff.s'.....si, 1 ¿í & ^ |S¡, такие что S= U s], s!n s\=0

ir l=1 i i j

2) yssN.sV.....s'\ такие что sJs!', s'Vsl' Ví,/=T7p ,

7 p 1=1 % 1 3

3) vscff,s'",...>s, такие что 5'= и 51", г'"^!",

7 г 1=1 ь 1

^"п VI,/=77р,

Для краткости записи введем обозначения:

Ф(к,з], 5> 2 д(з\) и Ф(к,з],Б}= Е и(Б'), где

1 1=1 1 " 1=1 1 1=1 1

Фф.а.э;1^ -¿г- Е и

®íp,a,s¡',s;= EvfS¡';, где £--US¡';

si-1

ФО.Л.я''2 v(s\" Мг-1 мю и ФГг.и.з!"^ Е иСБ'." )-(г-1Ми), где 5 Э*''.

1 {=7 4 {=1 4

Теорема 2.1.1. Для того, чтобы множество допустимых дележей было непусто необходимо и достаточно, чтобы выполнялись следующие неравенства:

Ф(Гг01 '' ,в.\,ю « Ф(г2,Вг,н['' ,н)тьг,ъ\,1), Ф(р,а,Б['« ф(г,В,н\ ' ',Е)+Ф(ъг,ъ\,1), ф(г,б,б' ''.я!,д; ^ Ф(р,а,н] ',1;

4S,R,H,L таких, что S П R=H П Ь=0 , SU R=H U L.

В §2.2 проводится доказательство теоремы 2.1.1. Примеры условий для игр 2-х и 3-х лиц показывают, что с ростом п (числа игроков) резко увеличивается количество этих условий, что затрудняет проверку их выполнения. Поэтому в следующей главе рассмотрен другой подход к этому вопросу.

Третья глава (5§3.1, 3.2) посвящена кооперативным играм п лиц с интервальной характеристической функцией в (0,1)-редуцированной 'форме. Рассматриваются необходимые и достаточные условия существования множества допустимых дележей для таких игр с использованием (д-Э,)-покрытий.

В §3.1 дается определение (0,1^-редуцированной формы кооперативной игры с интервальной характеристической функцией, доказывается, что каждую такую кооперативную игру можно свести к одной и только одной игре в (0,1^-редуцированной форме.

Определение 3.1 Л. Игра v(S) с ИХФ называется игрой в (0,1)-•редуцированной форме, если

у (d})=0 Víetf, V(N)=1.

0Ш1А§ление 3.1.2. Кооперативная игра с множеством игроков N и ИХФ v называется .¿-эквивалентной (стратегически эквивалентной) игре с тем же множеством игроков и ИХФ у*, если найдутся такие положительное й и произвольные вещественные ct (iíN), что для любой коалиции KíN имеют место равенства:

v(K)=kv*(K)+ Ее.,

v(K)=kv*(K)+ 2 с, тК 1

^-эквивалентность является отношением эквивалентности нэ множестве всех игр с ИХФ.

Теорема 3.1.1. Каждая кооперативная игра с ИХФ,

удовлетворяющая условию v(K) > £ v((t)),

i€tí

S-эквивалентна одной и только одной игре в (О,1J-редуцированной форме.

§3.2 посвящен теоретическому и практическому применению (д-8;-покрытий для получения необходимых и достаточных условий существования дележа.

Определение 3.2.1. Дележом для кооперативной игры в Г0,1)-оодуцированной форме с ИХФ назовем вектор a=(af,... ,ап).

удовлетворяющий условиям 0 < аь ^ и(С1}), 1=1,п,

2(1!) « 2 а. с 1, 1=1 1

'о(Б) « 2 а- ^ у(Б) цБ г

Обозначим через а=(Б 1,... систему таких множеств что если v(SJ)=0, то ¡3^=1, остальные 2(Эр>0. Каждому 3,€0 и N поставим в соответствие векторы Б , т и N :

п 1 1 Г если

_ 17 1 I и если ¿е5

N=(1.....1).

Определение 3.2.2. Назовем (д-6;-покрытием множества N такой набор неотрицательных вещественных чисел (X ,...что

ш - -

2 X Б =№, причем д-число Х,:>0, 9-система соответствующих им

J ~ 1

векторов в=СБ , .,.,5 | л >0, 1=77?

11 •Зг

3.2.3. Назовем Сд-в ;-покрктие (Хг...,Хт)

приведенным, если для всякого Сд-0^покрытия (Х1г...,Х ) при всех I выполняется равенство Хг=Хг.

Теорема 3.2.2. Для того чтобы у игры с ИХФ в (О,^-редуцированной форме существовал дележ, необходимо и достаточно, чтобы для любого приведенного ("д-0]-покрытия (X.,... ,Х ) выполнялась система неравенств

т

Е КЖБ ) « и

т

2 Х.Ь(Б,) » и(И). . 3=1 0 1

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

В главе 17 (§§4.1-4.3) рассмотрены различные понятия ядра в качестве решения для кооперативной игры п лиц с интервальной характеристической функцией.

В §4.1 определяются понятия а-доминирования и Са-ядер, приводятся необходимые и достаточные условия принадлежности дележа Са-ядру, устанавливается связь между Са~ядрами.

Так как решение кооперативной игры включает нахождение

выигрыша, который каждая коалиция S может себе обеспечить в игре,

и ее суммарный выигрыш принадлежит отрезку [v(S),v(S)l, то

возникает вопрос о том, ближе к какому концу отрезка он будет

располагаться. Естественно, что кавдый игрок стремится получить

наибольшее значение своей доли, т.е. на сколько это возможно

приблизиться к правому концу своего отрезка.

Выигрыш коалиции S можно представить как

va(S)=a v(S)+d-a) v(S) ,где а е [0,1].

Определение 4.I.I. Будем говорить, что дележ х а-доминирует

дележ у по коалиции S и коэффициенту а (х ь у ), ест:

3, а

I) х{ > yt VieS ,

2> S/t « va(S)-

Определеще 4.1.2. Будем считать, что х а-доминирует у

(х у у ) , если существует такая коалиция S, что х у у. a S,a

Определение 4.1.3. Множество всех а-недоминируемых дележей

назовем Са-ядром.

Будем считать игру п лиц в форме ЖФ а-супераддитивной, если

для данного а выполняется условие

Теорема 4.1.1. Для того, чтобы дележ х=(х^хг,...,х) принадлежал ядру Са необходимо и достаточно, чтобы выполнялись неравенства

V 'Г ч .. re 1 WC

л , у (/„ ( и / V О .

tes u

Если а-О, то имеет место самое большое С0-ядро, которое совпадает со множеством всех дележей и непусто всякий раз, когда существует хотя бы один дележ.

Если а=7, то 0?-ядро может либо состоять из единственного

цележа х=(х,,х.,...,х ), где x.=v((i}) , í=T~jí , либо быть

7 ¿ TI v

тустым.

Следствие 4.I.I. Gt-ядро непусто тогда и только тогда,

согда существует делезк х=(х. ,г„,... ,х } такой, что x,=v({U),

1 а П ь

\=Tji и выполняются равенства v(S)= 2 v(Ct)) для всех S.

iaS

Очевидно все Оа~ядра образуют следующую цепочку включений: .ели о^хх, , то Ga = Gai.

Если дележ х=(х1 ,... ,хп) € Са , то х будет

принадлежать и всем ядрам Gn , для которых а.< а..

j J ь

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

а - max ,

V (S .) « 2 х ,j=üm ,

а J itsj l

[ a e [0,1] , где -число всевозможных коалиций.

Эта задача всегда имеет решение, если существует хотя бы

один дележ.

В §4.2 вводятся понятия нормированного эксцесса и ff-ядра, устанавливается связь между //-ядром и непустым Оа~ядром, приводится способ вычисления JV-ядра.

Введем понятие N-ядра для кооперативной игры n-лиц в форме ИХФ. Для этого определим нормированный эксцесс.

Определение 4.2.1. Нормированным эксцессом назовем следующую меру близости дележа к v(S):

v(S)~ 2 х. tes 4

e(S,x) =- .

v(S)-v(S)

Из чего следует, что О < e(S,x) í 7.

Будем искать такой дележ х=(х1,хг,...,хп) , при котором любая коалиция S получит сушу, "по возможности близкую" к v(S). Следуя Д.Шмайдлеру, введем следующее определение. Определение 4.2.2. N-ядром назовем множество дележей, минимизирующих нормированный эксцесс в лексикографическом порядке:

V=Cxa ¡ Н ( e(S.,x),e(S„,x),...,e(S .х)) <т

gib I eZ. 2 '

iL Я J e(S1,y),e(S2,y).....e(S П,у)), ЧучХ),

2 2

где ^-множество всех дележей,

H Br -> ft означает отображение, которое упорядочивает

гп

записи Рп-мерного вектора в порядке убывания величины.

Для нахождения N-ядра решается задача математического программирования:

5 -> т1п , 2 х

да; а 2 « да;

{€5

Если (х*,е*)-оптимальное решение этой задачи единственно,

то х*-ядро; иначе пусть б* 13}

программирования:

достигается для коалиций

, тогда решаем другую задачу математического

е - тт ,

да;- 2 г. да;-да;

- - в

Я ? 3,

3=1,т.

■Д.

да; « 2 г < да; .

Через конечное число шагов мы придем к системе, имеющей в

качестве единственного решения.

Опираясь на результаты Д.Шмайдлера, можно показать, что множество " непусто для любого непустого компактного множества Хс вп, а если множество К выпукло, то N состоит из одной точки. Лемма 4.2.1. 1*-ядро принадлежит каждому непустому С -ядру. §4.3 посвящен многокритериальному подходу к определению выигрыша в кооперативной игре с интервальной характеристической функцией.

Рассмотрим следующую двухкритериальную игру. Для каждой

а

удовлетворяющее следующим

коалиции За N введем множество V" условиям:

1) V -непустое, замкнутое подмножество В2 ,

2) если (V1 , то г>4 У2.

-множество всех возможных значений векторов двухкритэриаль-анх выигрышей для коалиции

Вектор двухкритериальных выигрышей имеет вид у=Су',у2;, где у'-гарантированный выигрыш, который могут получить члены коалиции независимо от действий остальных игроков, у2-гарантированный

выигрыш, который могут позволить коалиции остальные игроки, т.е.

вектор двухкритериальных выигрышей характеризует нижний v1 и

верхний V2 концы отрезка, в котором будет содержаться возможный

выигрыш коалиции при данной ситуации.

Применяя различные стратегии, игрок или коалиция игроков

имеет возможность получать выигрыш из различных отрезков [v\v2].

Естественно будет искать разумный исход игры среди парето-

оптшальных точек, которые можно находить методами свертки

критериев в виде суммы или минимума.

Обозначим парато-оптимальную точку для коалиции S как

0S = ( v1s , v2s ).

Мы хотим найти дележ х=(х1,х2,...,х ) такой, чтобы для

каждой коалиции S сумма J х, была го-возможности дальше от

itS ь

левого конца отрезка [v1g , у| 1 и как можно ближе к правому.

Введем два эксцесса: е1(S,x)= 2 x,-vL как "меру близости" к первому значению

вектора двухкритериальных выигрышей, и

e2(S,x)~ v2- 2 х. как "меру близости" ко второму значению

3 i€S 1 вектора v„ .

■ i

Ядро N определим как множество векторов выигрышей, максимизирующих эксцесс e1(S,x) в лексикографическом порядке.

Определим ядро Н2 как множество векторов выигрышей, минимизирующих эксцесс ег(3,х) в лексикографическом порядке.

Оба ядра И1 и Н2 могут выступать в качестве решения игры, поэтому идеально положить N = N?(l N2, если пересечение непусто, а в противном случае положить N = N'u Ы2.

Мы рассмотрели случай, когда паретовская точка одна или из всего множества Парето выбрана каким-либо способом одна точка. В общем случае паретовское множество содержит более одной точки. Интересным является вопрос о построении W-ядра для всего этого множества в совокупности.

Обозначим множество парето-оптимальных точек:

Ь = = <4 >*s П v1s^v2sJ. Рассмотрим случай конечного Vg (иначе выберем в нем конечную

s-сеть и в качестве V"s будем рассматривать множество точек, являющихся узлами е-сети).

Решение задачи сводится к нахождению дележа

х=(х,,х„,...,х^) такого, что для любой коалиции S сумма 7 х, ' £ п idSj

будет принадлежать одному из отрезков [vl , , у? ? из

Ь , J^ Ь , J s

где .f-номер вектора выигрыша из множества 70 .

Определим функции эксцесса как весовые расстояния от парето-оптимальной точки до вектора выигрыша х . Способ I:

функции эксцесса определим так

EUs,x)= S w^ej (S,x) , j=7,|7S| , где e'fS.x; = 2 x -v1 ,

E2(S,x) = E (S.zJ , j=1,17g| ,

где e2.(S,x) = - % x

J s,j i

Способ II:

£'(3,x) = max ш e'(S,x) , J J J

I?(S,x) = fflin ы €j(S,x)

1 О ^

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

В работе приводятся примеры, иллюстрирующие вводимые понятия, утверждения и методы нахождения решений.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

[) Для кооперативных игр п лиц введено и обосновано понятие

штервальной характеристической функции (ИХФ).

Z) В качестве исходного понятия в разумном распределении

выигрышей мевду игроками определено множество допустимых дележей

ум игры в форме ИХФ и получены необходимые и достаточные условия

юпустоты этого множества в комбинаторной форме.

i) Исследована (0,1J-редуцированная форма кооперативной игры п

лиц с ИХФ.

4) Получены необходимые и достаточные условия существование множества допустимых дележей для игры в (0,7.}-редуцированно$ форме с использованием (q-ej-покрытий.

5) Предложены и исследованы различные понятия С и Ы-ядер i качестве решения кооперативных игр п лиц с ИХФ.

Предложенный подход к'кооперативным играм позволит строить более реальные модели рыночной корпоративной экономики в условиях неполной информированности сторон.

Основное содержание диссертации отражено в работах:

1. Горелик В.А., Ларина О.В. Кооперативные игры с интервальной характеристической функцией //Моделирование, оптимизация и декомпозиция сложных динамических процессов. М.: ВЦ РАН, 1993. С.75-91.

2. Ларина О.Б. Интервальные задачи в кооперативных играх // III Международная конференция женщин-математиков: Тезисы докладов.-Воронеж, 1995. G.I34.

3. Горелик В.А., Ларина О.В. Метод покрытий для кооперативных игр с интервальной характеристической функцией //Моделирование, оптимизация и декомпозиция сложных динамических процессов. М.: ВЦ РАН, 13Э6. С.51-60.

4. Ларина О.В. Кооперативные игры как предмет котпьютерного моделирования в обучении //Компьютерные программы учебного назначения: Тезисы докладов III Международной конференции.-Донецк: ДонГУ, 1996. С.101.

OJbf—