Реферат: Теория принятий решений

Tаким образом,  приемлемые ситуации для первого игрока - это максимальные элементы встолбцах матрицы А, а для второго игрока - максимальные (тоже!) элементы в строках матрицы В.

Ситуация i*j* в биматричной игре называется равновесной, если она приемлема для обоих игроков, то есть если любое отклонение от нее как для первого игрока, так и для второго только лишь уменьшает их выигрыш:

аi*j*   ³   аij*

bi*j*   ³   bi*j

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

Пример.

                   G1={(1,1),(1,3),(3,2),(3,3)}

                   G2={(1,1),(2,1),(2,3),(3,2)}        G = {(1,1),(3,2)}

                   I  v(1,1)= 3            II  v(1,1)= 3

                       v(3,2)= 3                v(3,2)= 2

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

Из примера  хорошо  видно,  что  хотя (1,1) и (3,2) - ситуации равновесия,  ситуации (1,2) и (3,1) таковыми не являются, в отличие от матричных игр.

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

Так, в рассматриваемом примере второй игрок заинтересован в том, чтобы первый выбрал i=1, так как при этом v(II)= 3. Первому же игроку с точки зрения выгоды безразлично какую стратегию  выбрать  -  первую или третью - в любом случае его выигрыш составляет 3.  Если первый игрок доброжелательно настроен по отношению к противнику,  то  он  выберет  первую стратегию,  чтобы и второй игрок получил максимальный выигрыш.  В противном случае первый потребует за выбор более выгодной для второго стратегии дополнительную плату,  и если эта плата будет меньше единицы,  то очевидно, что второй игрок согласится на эту сделку.Такая игра называется игрой с побочными платежами.

Если в биматричной игре ситуаций равновесия нет, но игроки имеют возможность договориться между собой,  то обычно применяют такой искусственный прием: находится i*j* такая,что:

                              max ( aij + bij  ) = ( ai*j* + bi*j* )

и делится между игроками по заранее оговоренному правилу.

Пример.

Ситуаций равновесия нет. Находим максимальный элемент в матрице А+В

max = 5, ( i, j ) = (3,2). Эта сумма должна быть разделена между первым и вторым игроками.

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

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

Задание по биматричным играм

Придумать условие биматричной игры n*m, n = m > 3 и найти ее решения в чистых стратегиях ("игра с побочными платежами")

Глава . Нестратегические игры

1. Основные понятия и определения.

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

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

Коалицией в кооперативное игре называется всякое (любое) подмножество множества игроков.

Пример.  Пусть I = {1,2,...i...n} - некоторое множество игроков. Коалициями будут: k1 = {1,2,5,i};

k2 = {i} = i;

k3 = { } = Æ ;

k4  = { 1,2,...n} = I.

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

Характеристической функцией v(k)  называется наибольший выигрыш, уверенно получаемый коалицией k.

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

Задать характеристическую функцию этой игры.

I = { M, p1, p2 } - множество игроков игры. Тогда

v(Æ) = v(p1, p2) = v (p1) = v (p2)= v (M) = 0,

v (M, p1, p2) = v( M,p1) = v( M, p2) = C.

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

Свойства характеристической функции:

1. Персональность  vГ (Æ) = 0;

2. Супераддитивность vГ (КÈL) ³ vГ (К) + vГ (L),  где K,LÎI, KÇL = Æ;

3. Дополнительность vГ (К) + vГ (I\K) = vГ (I) = C,

 где С - постоянная сумма выигрыша.

2. Дележи в кооперативных играх.

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

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

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

Прежде всего, каждый игрок вступает в коалицию только в том случае, если это, по крайней мере, не уменьшает его выигрыш, то есть если

xi ³ v(i)                                                              Эгалитарный подход

                 å xi = v (I)                                                         Утилитарный подход

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

Дележом в условиях характеристической функции v называется вектор х = ( х1, х2, ... хn), удовлетворяющий условиям индивидуальной и коллективной рациональности.

Классической кооперативной игрой называется система < I, v >, включающая множество игроков I  и характеристическую функцию v над этим множеством, а так же множество Х дележей в условиях этой характеристической функции.

Теорема. Для того, чтобы вектор   х = ( х1, х2, ... хn)   был дележом в кооперативной игре < I, v >, необходимо и достаточно, чтобы

                хi = v (i) + ai,     ai ³ 0,         i Î I;

                å ai = v(I) - å v(i)

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

                åxi = å v (i) + v(I) - å v(i) = v(I) также выполняется.

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

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

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

Существующая классификация делит все кооперативные игры, прежде всего, на существенные и несущественные.

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

v (КÈL) =  v (К) + v (L),  где K,LÎI,  KÇL = Æ;

Существенными называются остальные игры.        

Любая кооперативная игра с аддитивной (а не супераддитивной) характеристической функцией является несущественной, ее участники не заинтересованы в образовании коалиций, так как это не увеличивает их выигрыш (долю).

Признак аддитивности характеристической функции задается теоремой:

Теорема. Для того, чтобы характеристическая функция была аддитивной, необходимо и достаточно, чтобы выполнялось равенство    å v(i) = v(I).

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

Теорема. В несущественной игре существуе только один дележ

                ( v(1), v(2),... v(n) ).

Во всякой существенной игре множество дележей бесконечно.

Это обьясняется тем, что в существенной игре обязательно существует

                D = v(I) - å v(i) > 0,

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

Игроки так же делятся на существенных и несущественных (болванов), а множества игроков - на носителей игры и множества болванов.

Существенным называется игрок i, если существует такая коалиция К, что

                v(K) + v(i) < v(KÈi).

Болваном называется игрок i, если для любой коалиции KÌI cправедливо

                v(K) + v(i) = v( KÈi).

Допустим, L - множество болванов (несущественных игроков) и LÌK, тогда

                v(K) = v(K\ L) + å v(i), а если K = L, то v(K) = å v(i).

Существенные игроки образуют множество носителей игры, NÌI. Признаком этого для коалиции К является:

                v(K) = v(KÇN) + å v(i) i ÎK\N.

3. Аффинно-эквивалентные игры.

Существенные и несущественные игры тоже делятся на классы.

Кооперативная игра с множеством игроков I  и характеристической функцией v называется аффинно-эквивалентной игре с тем же множеством игроков и характеристической функцией v’, если найдутся такое положительное число k и произвольные вещественные ci ( i Î I ), что для любой коалиции KÌ L имеет место равенство:

v’(K) = k v(K) + å ci , iÎK.

При афинной эквивалентности v ~ v’  дележ x соответствует дележу х’ так, что: xi ’ = k xi + ci.

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

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

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

Рассмотрим с позиций стратегической эквивалентности несущественные игры.

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

Теорема. Всякая существенная игра аффинно эквивалентна нулевой игре.

Следствие. Все несущественные игры с одним и тем же множеством игроков аффинно эквивалентны друг другу.

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

Для изучения существенных игр наиболее удобна a-b редуцированная форма, то есть такая, в которой v(i) = a, v(I) = b. Обычно используются варианты a=0, b=1 и a=1, b=0.

Теорема. Всякая существенная игра аффинно эквивалентна одно и только одной игре в 0-1 редуцированной форме.

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

v’(K) = ( v(K) - å iÎK v(i))/ ( v(I) - å iÎI v(i))                                 (3.1.)

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

Все дележи в 0-1 редуцированной форме должны отвечать условиям: xi ³0, так как v(i) = 0, но есть еще D, так как игра существенная å xi  = v(I) = 1.

Пример. Дана кооперативная игра, I = {1,2,3,4}. Задана характеристическая функция:  v(1) = -1;  v(2) = v(3) = -2;  v(1,2,4) = v(1,3,4) = 2;  v(2,3,4) =1;

v(4)=  v(1,2)= v(1,3) = v(1,4) = v(2,3)= v(2,4) = v(3,4) =  v(1,2,3) = v(1,2,3,4) = 0;

Найти характеристическую функцию 0-1 редуцированной формы.

Воспользуемся формулой 3.1. В знаменателе выражения стоит постоянная величина   v(I) - å iÎI v(i) = 0 - (-1-2-2) = 5. Остальные вычисления занесем в таблицу:

4. Доминирование дележей.

Рассмотрим кооперативную игру   Г = < I, v >  и два дележа в этой игре:       х = ( х1, х2, ... хn)  и y = ( y1, y2, ... yn). Допустим, K Ì I - некоторая коалиция в игре.

Дележ х доминирует дележ у по коалиции К, если выполняются неравенства å iÎK  хi  £  v(К) и хi  > yi , iÎ К. Доминирование дележа по коалиции К обозначается  хñК у,   х dom К y,   или x Rк y.

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

Для коалиции К доминирующий дележ полезнее, чем доминируемый. Эта коалиция будет его отстаивать. Иной случай, когда с этим дележом не согласятся остальные игроки (входящие в множество I\K). Но коалиция К может сама обеспечить себе такой дележ, так как  å iÎK  хi  £  v(К).

Следует отметить, что доминирование возможно по любой  коалиции, кроме коалиции из одного игрока и из всех игроков. В первом случае К = {i} из определения следует, что хi  £  v(i), что противоречит свойству индивидуальной рациональности дележа  х ( х ³ v(i)). 

В случае К = I  из  хi  > yi  следует , что åхi  > åyi = v(I), то есть дележ  х  должен давать в сумме больше, чем гарантированный выигрыш для всех игроков.

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

Теорема. Если v  и  v’  - аффинно-эквивалентные характеристические функции, причем дележам  х  и  у в  v соответствуют дележи  x’  и  y’  в  v’, то из    х ñК  у   следует  х’ ñК  у’.

Отношение доминирования выполняется для всех кооперативных аффинно эквивалентных игр и является свойством не одной игры, а всего класса эквивалентных игр. Поскольку, например, в несущественной игре всего один дележ, то для них понятие доминирования не имеет смысла. Существенные игры исследовать на доминирование можно используя 0-1 редуцированную форму.

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

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

 Например,в игровой модели Шепли-Шубик, 1969 года (кооперация производства с обменом продуктами) или просто модели обменов, вопрос о том, как кооперировать, может быть заменен вопросом: какое понятие оптимальности следует  применять для дележа прибыли?

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

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

Рассмотрим в качестве принципов оптимизации устойчивость коалиционной структуры и принцип справедливости.

Эксцессом дележа  х для коалиции К в условиях характеристической функции v называется разность

ev(x,K) = v(K) -  å iÎK  хi , колторая показывает, насколько может коалиция К увеличить свой выигрыш по сравнению с суммой, предлагаемой по дележу. Если эксцесс положителен, то соответственный дележ реализуем для данной коалиции, в этом случае дележ называется эффективным.

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

Дележ называется абсолютно неэффективным, если он не эффективен ни для какой коалиции.

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

Пример. Рассмотрим существенную игру трех лиц с постоянной суммой. С позиций доминирования в этой игре можно рассматривать только коалиции {1,2}, {1,3}, {2,3}. Пусть х = ( х1, х2, ... хn)  и y = ( y1, y2, ... yn) - дележи и х dom 1,2 y . Из определения доминирования следует, что должно выполняться 

Страницы: 1, 2, 3, 4