Элементы теории игр

Глава 1. Элементы теории игр § 1. Введение Одной из характерных черт всякого экономического явления является многосторонность интересов и наличие сторон, которые выражают эти интересы (например, «покупатель – продавец»). Более сложные ситуации возникают, если имеются объединения или коалиции лиц, участвующих в столкновении интересов (например, голосование в парламенте). Конфликт может проявляться не только в результате сознательных действий игроков, но и как результат тех или иных стихийных сил. Всякая математическая модель социально-экономического явления должна отражать присущие ему черты конфликта, т.е. описывать а) множество заинтересованных сторон (игроков); б) возможные действия каждой из сторон (стратегии игроков); в) интересы сторон, представленные функциями платежа для каждой из сторон. Предметом теории игр являются такие ситуации, в которых важную роль играют конфликты и совместные действия сторон. Классификация игр. Игры можно классифицировать: • по числу игроков; • по числу стратегий; • по свойствам функций платежей; • по возможности предварительных переговоров и взаимодействий между игроками в ходе игры. По числу игроков различают игры с двумя, с тремя и более участниками. По числу стратегий различают конечные и бесконечные игры. По свойствам функций платежей различают игры с нулевой суммой, игры с постоянной разностью и игры с ненулевой суммой. В игре с нулевой суммой выигрыш одного игрока равен проигрышу другого. В игре с постоянной разностью игроки и выигрывают и проигрывают одновременно, им выгодно действовать сообща. В игре с ненулевой суммой имеются и конфликты, и согласованные действия сторон. В зависимости от возможности предварительных переговоров и взаимодействий между игроками в ходе игры различают кооперативные и некооперативные игры. Игра называется кооперативной, если до начала игры игроки образуют коалиции и принимают взаимообязывающие соглашения о своих стратегиях. Игра, в которой игроки не могут координировать свои стратегии подобным образом, называется некооперативной. § 2. Матричные игры . Рассмотрим сначала игру с нулевой суммой с двумя участниками. Для описания такой игры приведем пример Пример. Бизнесмен планирует поездку в город N. Эта поездка должна состоятся ровно через месяц. Однако существуют некоторые чрезвычайные обстоятельства, которые могут возникнуть перед отъездом и привести к переносу отъезда на два дня. Бизнесмен может купить билет либо по обычному тарифу за 100$, либо по экскурсионному за 75$. В первом случае бизнесмен может без труда переносить дату отъезда, заплатив за переоформление 5$. Если он воспользуется экскурсионным тарифом и ему придется перенести отъезд, то он потеряет 75$ и заплатит еще 100$ за новый билет. Предположим, что бизнесмен выступает в роли первого игрока, а вторым игрокам является обстоятельства ( назовём его «природа»). Определим стратегии игроков. Первый игрок имеет две стратегии: δ1 = {воспользоваться обычным тарифом}; δ2 = { воспользоваться экскурсионным тарифом}. Второй игрок также имеет две стратегии: Θ1= {поездка состоится в намеченный срок}; Θ2= {дата поездки сдвинется на 2 дня}. Обозначим через aij - потери первого игрока, если он применяет стратегию δi, а второй игрок - Θj. Тогда, по условиям a11 = 100 δ1 δ2 a12 = 105 100 105 Θ1 a21 = 75 75 175 Θ2 a22 = 175 Здесь матрица А называется матрицей потерь первого игрока. Цель первого игрока – выбрать оптимальную стратегию, приводящую к наименьшим потерям. С этой целью руководствуясь общим принципом Р каждой стратегии первого игрока δi ставят в соответствие число a(δi), характеризующее потери. Существует два подхода к решению задачи выбора оптимальной стратегии: минимаксный и байесовский. В рамках минимаксного подхода первый игрок считает, что его ожидает самая неблагоприятная ситуация и самые большие потери и оптимальной считает стратегию, которая минимизирует эти большие потери. В рамках байесовского подхода первый игрок располагает некоторой дополнительной информацией, о том с какой вероятностью его оппонент использует ту или иную стратегию. Это позволяет вычислять средние потери и оптимальной для первого игрока считается та стратегия, которая минимизирует эти средние потери. Задачи к § 2 2.1. Школьник сдал выпускные экзамены в своей школе и теперь должен решить, в какое ВУЗ он будет поступать. У него на выбор есть возможности получения экономического, юридического, гуманитарного, математического и технического образования. Но, политическая ситуация в стране не стабильная, вскоре ожидается президентские выборы. Основными предентами на успех по экспертным оценкам являются кандидаты от партий консерваторов, социал-демократов, коммунистов и «зелёных». В зависимости от победы того или иного кандидата, в стране будет сделана ставка на ту или иную социально-трудовую политику. Поэтому профессия, которую получит школьник, будет по-разному цениться при разных режимах. Сформулируйте задачу как матричную игру с составлением матрицы потерь школьника. 2.2. Рассмотрим следующую игру. Каждый игрок показывает один или два пальца и одновременно пытается угадать число пальцев, показанных противником. Если один из игроков угадал правильно, то он выигрывает сумму, равную общему числу пальцев, показанных обоими игроками. Во всех остальных случаях игра заканчивается вничью. Сформулируйте задачу как матричую игру; составьте матрицу потерь для первого игрока. § 3. Простая А-игра Пусть задана прямоугольная матрица элементы которой aij являются вещественными числами. Пусть два лица, которых мы будем ниже называть первый игрок, второй игрок, играют в следующую игру. Первый игрок имеет n стратегий 1, ,n и может выбрать любую по своему усмотрению; второй игрок имеет m стратегий 1, ,m и тоже выбирает одну из них. При этом ни один из игроков не знает, какую стратегию выберет его противник. Если первый игрок выбрал стратегию i, а второй игрок – стратегию j, то потери первого игрока в этой ситуации равны числу aij. Таким образом, матрица A = (aij) является матрицей потерь первого игрока. Поскольку интересы игроков прямо противоположны, число aij можно называть также выигрышем второго игрока в результате ходов (i, j), а матрицу A – матрицей выигрышей второго игрока. Первый игрок действует так, чтобы уменьшить свои потери, второй игрок хочет увеличить свой выигрыш. Введем следующие обозначения:  = {1, , n} – набор стратегий первого игрока,  = {1, , m} – набор стратегий второго игрока. Итак, простой A-игрой называется тройка объектов {, , } Обозначим Видно, что ai есть максимальные потери, которые понесет первый игрок, если он будет следовать стратегии i; aj – минимальные потери, которые он понесет, если второй игрок выберет стратегию j. Определение 1. Число назовем верхней ценой игры. Определение 2. Число назовем нижней ценой игры. Определение 3. Если a = a, то число a = a = a ценой игры. Лемма 1. Имеет место следующее неравенство: a  a. Доказательство. Для любых i, j справедливы неравенства ai  aij  aj, поэтому ai  aj. Стало быть и лемма 1 доказана. Определение 4. Будем говорить, что точка (i0, j0) является седловой (для матрицы A), если для всех i, j выполняются неравенства Цена игры существует тогда и только тогда, когда существует седловая точка. Задачи к § 3 3.1. Первый игрок имеет $1000 для приобретения путевки на курорт. Предположим, что курс доллара к рублю – 1:28. Пусть по некоторым причинам покупка путевки переносится на месяц. В этой ситуации первый игрок должен ответить на вопрос: как поступить с деньгами? Опишите игру как простую А-игру, составьте матрицу потерь для первого игрока, найдите цену игры, если она есть. 3.2. Предприятие выпускает два вида продукции: мороженое (цена – 5 руб., себестоимость – 3 руб.) и пирожки (цена – 4 руб., себестоимость – 2,5 руб.). В холодную погоду продается 1000 штук мороженого и 6000 штук пирожков; в теплую погоду – 4000 штук мороженого и 1200 штук пирожков. Если продукцию не успели продать в день изготовления, то на следующий день ее продают по цене, в четыре раза меньшей, чем в день изготовления. Сформулируйте задачу как простую А-игру, составьте матрицу потерь для предприятия, найдите цену игры, если она существует. 3.3. Два противника сражаются на двух позициях. У первого противника – 4 полка, у второго – 3 полка. Каждый из противников может послать на позиции любое количество своих полков. Позиция считается выигрышной для участника, если он послал на нее большее количество полков, чем его оппонент, и выигрыш составляет 1+число полков противника, «плененных» на этой позиции. В случае, когда количество полков на позиции совпадает, считаем, что на этой позиции ничья, и каждый игрок получает 0 очков. Общий выигрыш каждого участника равен сумме выигрышей на каждой позиции. Опишите игру как простую А-игру, составьте матрицу потерь для первого игрока, найдите цену игры, если она есть. § 4. Расширенная A – игра Рассмотрим прямоугольную матрицу A размера n  m и отвечающую ей простую A–игру. Множества стратегий первого и второго игроков имеют вид  = {1, , n},  = {1, , m}. Назовем стратегии i чистыми стратегиями первого игрока, а j – чистыми стратегиями второго игрока. Можно теперь расширить классы ,  стратегий игроков, рассмотрев множества Вектор x = (x1, , xn) будем называть смешанной стратегией первого игрока, понимая под этим следующее: в соответствии с этой стратегией первый игрок с вероятностью xi выбирает чистую стратегию i  . Аналогично интерпретируется смешанная стратегия y = (y1, , ym) для второго игрока. Потери, которые понесет первый игрок, если он использует смешанную стратегию , а его оппонент смешанную стратегию , имеют вид где T означает транспонирование матрицы-строки y = (y1, , ym), а запись xAyT понимается как произведение трех прямоугольных матриц в соответствии с обычными правилами умножения матриц. Расширенной A–игрой мы будем называть тройку где - классы смешанных стратегий первого и второго игроков соответственно, ã = ã(x, y) – функция потерь первого игрока вида (1). Обозначим Видно, что ã(x,) – максимальные потери, которые понесет первый игрок, если он будет следовать стратегии x; ã(, y) –минимальные потери, которые он понесет, если второй игрок выберет стратегию y. Определение 1. Число назовем верхней ценой расширенной A–игры. Определение 2. Число назовем нижней ценой расширенной A–игры. Лемма 1. Имеет место следующее равенство Стратегии , удовлетворяющие неравенству называются оптимальными стратегиями, а (x, y, ã) – решением игры. Лемма 2. Пусть число ã является ценой расширенной A–игры. 1) Для того, чтобы стратегия была оптимальной, необходимо и достаточно, чтобы для выполнялось неравенство: 2) Для того, чтобы стратегия была оптимальной, необходимо и достаточно, чтобы для выполнялось неравенство: Суть леммы 2 состоит в том, что нахождение оптимальной стратегии сводится к решению системы неравенств и равенств: Лемма 3. Пусть число ã, стратегии x = (x1,, xn), y = (y1,, ym) удовлетворяют неравенствам (1), (2). Тогда они являются ценой игры и оптимальными стратегиями первого и второго игроков соответственно. Если для некоторого индекса j в (1) выполняется строгое неравенство, т.е. то соответствующий yj = 0. Если для некоторого индекса i в (2) выполняется строгое неравенство, т.е. то соответствующий xi = 0. Доказательства этих лемм можно найти в [ ]. Задачи к § 4 4.1. Рассмотреть А-игру с матрицей потерь первого игрока: а) найти а*, а* и убедиться, что в простой А-игре нет цены; б) составить систему линейных уравнений и неравенств для ã, x = (x1, x2, x3), y = (y1, y2, y3) в расширенной А-игре; в) найти решение ã, x, y в расширенной А-игре. 4.2. Для матрицы решить задачу 4.1. § 5. Доминирующие и полезные стратегии Иногда применение некоторых из чистых стратегий нецелесообразно и при определении оптимальных смешанных стратегий их не следует учитывать. Те чистые стратегии, которые входят в состав оптимальной смешанной стратегии, называются полезными стратегиями. Предположим, что для двух чистых стратегий δl и δk первого игрока имеет место следующее неравенство: В этом случае нет смысла применять стратегию δk (т.к. для первого игрока это проигрыш и стратегия с наибольшим проигрышем должна быть отброшена) и δl – доминирующая стратегия по отношению к стратегии δk.. Аналогичным образом определяется стратегия второго игрока. Пусть для двух чистых стратегий второго игрока θl и θk имеет место неравенство: Тогда θl – доминирующая стратегия второго игрока (для второго игрока это выигрыш и отбрасывается стратегия с наименьшим выигрышем). Предположим, что в рассматриваемой игре ни одна из стратегий не доминирует над другими. В этой ситуации пытаемся ответить на вопрос: все ли стратегии являются полезными, то есть входят в оптимальную смешанную стратегию? Пусть у второго игрока имеется конечное число стратегий, то исходная игра сводится к так называемой S-игре. Попытаемся вывести понятие «S-игра». Пусть имеется А = (аij), i = 1,…,n; j = 1,…,m – матрица потерь первого игрока. Каждой стратегии δi первого игрока ставим в соответствие точку сi = (ai1, ai2,…,aim) в m-мерном пространстве, где координатами являются потери. Игра, заданная множеством точек {с­1,c2,…,cn} называется S-игрой. Сначала первый игрок выбирает одну из точек сi. Независимо от первого игрока второй выбирает координату точки, например аi2, при этом говорят, что потери первого игрока составляют аi2. Если у второго игрока имеется две стратегии, то S-игра допускает наглядную интерпретацию. Предположим, что матрица игры выглядит следующим образом: S-игра: с1 = (1,0); с2 = (2,3); с3 = (-1,1); с4 = (0,-1); с5 = (1,2). Рис.1 Отмечаем точки на плоскости и соединяем их прямыми линиями для получения выпуклого множества (рис.1). S = 1c1+2c2+3c3+4c4 , где Теорема 1. Любая смешанная стратегия первого игрока может быть представлена точкой, принадлежащей выпуклой оболочке S* и наоборот. Выпуклая оболочка S* конечного множества (с1,…,сn) является выпуклым многогранником в n-мерном пространстве. Точка So, являющаяся граничной, будет принадлежать обязательно одной из его граней, вершины которой и будут соответствовать полезной стратегии первого игрока. Учитывая, что число вершин любой грани не может превышать общего числа его вершин (то есть числа n ) и не может превышать размерности пространства (то есть числа m) приходим к выводу, что число полезных стратегий первого игрока не превышает min{n,m}. Теорема 2. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш игроков остается неизменным и равным цене ã, независимо от того, какую смешанную стратегию применяет другой игрок, если только он не выходит за пределы своих полезных стратегий. Доказательства этих теорем можно найти в [ ]. § 6. А-игры порядка 2 × 2, 2 × m, n × 2 А-игра порядка 2 × 2. Рассмотрим А-игру порядка 2 × 2, котрая задается матрицей потерь первого игрока. Для решения этой игры следует сначала найти верхнюю и нижнюю цены в простой А-игре: Рассмотрим вариант, когда а*≠ a*. В этом случае, оптимальные стратегии игроков следует искать среди смешанных стратегий: x = (x1,x2), y = (y1,y2). Согласно леммам § 4 для их нахождения составим систему: a11 x1 + a21 x2 ≤ ã, a11 y1 + a12 y2 ≥ ã, a12 x1 + a22 x2 ≤ ã, a21 y1 + a22 y2 ≥ ã, x1 + x2 = 1, y1 + y2 = 1. Введем обозначение: d = a11 + a22 – a12 – a21. Лемма 1. Если а*≠ а*, то d ≠ 0 (докажите самостоятельно). Если d ≠ 0, то легко проверить (см. задачу 6.1.), что следующие векторы и число являются соответственно оптимальными стратегиями и ценой в расширенной А-игре, то есть удовлетворяют приведенным выше системам линейных равенств и неравенств. Пример 1. Пусть матрица первого игрока имеет вид Поскольку a* = 0,4; a* = –14, то в простой А-игре нет цены и, стало быть, нет чиcтых оптимальных стратегий. Вычислим константу d. d = –14 – 10,4 – 0,4 – 0,85 = –25,65 По предложенным выше формулам находим смешанные стратегии и цену игры. 2. А-игра порядка n × 2. Игру порядка n × 2 изучим на следующем примере. Пример 2. Фермер может выращивать две культуры (т.е. имеет две чистые стратегии θ1, θ2). Состояния погоды можно считать стратегиями природы: δ1 = {лето жаркое, сухое}; δ2 = {лето жаркое, влажное}; δ3 = {лето теплое, сухое}; δ4 = {лето теплое, влажное}; δ5 = {лето холодное, сухое}; δ6 = {лето холодное, влажное}. Пусть матрица доходов фермера (т.е. матрица потерь природы, которую считаем первым игроком) имеет вид: Требуется найти цену игры ã и оптимальные стратегии x = (x1, x2, x3, x4, x5, x6) и y = (y1, y2) первого и второго игроков соответственно. Сравнивая строки в матрице потерь видим, что четвертая стратегия доминирует над третьей. Третью строку вычеркиваем, а вместо x3 подставляем 0. Воспользуемся графическим способом решения, для этого составим линейные функции, которые выражают ожидаемые выигрыши фермера, соответствующие чистым стратегиям первого игрока, оставщимися после проведения процедуры доминирования: Эти линейные функции имеют вид: Рис.1 При каждом фиксированном y1 первый игрок, выбравший стратегию δi, несет потери gi (y1). Первый игрок минимизирует свои потери, поэтому мы рассматриваем ломаную (ломаная (рис.1) выделена жирной чертой). Mаксимизируя далее доходы второго игрока, находим Таким образом, мы графически построили оптимальную стратегию второго игрока y = (y1, 1–y1), где y1 есть точка пересечения функций g4(y1), g6(y1); цена игры ã есть значение функций g4, g6 в точке их пересечения. Составим уравнение для y1: 4y1 + 3(1–y1) = 3y1 + 6(1-y1). Находим: ã = g4(0,75) = g6(0,75) = 3,75. Итак, стратегия y = (3/4, 1/4) второго игрока является оптимальной. Определим оптимальную стратегию первого игрока. На рис.1 видно, что для i = 1, 2, 3, 5 выполняются строгие неравенства gi(0,75) > ã. Это значит, что в силу леммы 3 (§4) справедливо x1 = x2 = x3 = = x5 = 0. Решением будет являться вектор x = (0,0,0,x4,0,x6). Найдем x4, x6. x = (0, 0, 0, x4, 0, 1–x4) 1∙0 +2∙0 + 4∙0 +3x4 + 12∙0 + 6(1– x4) = 3,75 3x4­ + 6 – 6x4 = 3,75 x4 = 0,75 Решение: x = (0, 0, 0, 3/4, 0, 1/4), y = (3/4,1/4), ã = 3,75 Фермер может интерпретировать полученный ответ двояко: либо а среднем 3 года из 4-х сеять первую культуру, 1 год – вторую, либо в среднем 3/4 площадей отводить под первую культуру, 1/4 под вторую. 3. А-игра порядка 2 × m. Игру порядка 2 × m изучим на следующем примере. Пример 3. При выращивании картофеля фермер может вносить удобрения в почву по следующей схеме: θ1 = {количество удобрений на 1 га соответствует определенной норме}; θ2 = { количество удобрений на 1 га больше этой нормы на 30%}; θ3 = { количество удобрений на 1 га меньше нормы на 40%}. Для природы рассмотрим два вида погоды: δ1 = {лето сухое}; δ2 = {лето влажное}. Предположим, что матрица потерь первого игрока (доходов второго игрока – фермера) имеет вид: ã* = 4, ã* = 2,5, ã* ≠ ã* Рассмотрим смешанные стратегии игроков: x = (x1, x2), y = (y1, y2, y3) Составим функции: которые имеют следующий смысл: fJ(x1) – это доход фермера, если он использует чистую стратегию Θj, а природа отвечает ему смешанной стратегией x = (x1, 1–x1). Эти линейные функции имеют вид Рис.2 Максимизируя функции fj(x1), получаем функцию (см. рис. 2) которая определяет максимальный доход фермера при стратегии природы (x1, x2), где x2 = 1–x1. Поэтому цена игры такова: Как видно из рис.2 цена игры ã есть значение функций f1, f2 в точке их пересечения. Составим уравнение для x1: 2x1 + 2 = –2x1 +4 x1 = 1/2. Оптимальной стратегией первого игрока будет - x = (1/2, 1/2), а ценой игры ã = f1(1/2) = 3. Для нахождения оптимальной стратегии второго игрока воспользуемся леммой 3 §4 По второй части леммы 3 (§3): f3(1/2)<3 => y3 = 0. Следовательно, оптимальная стратегия второго игрока будет иметь вид: y = (y1, y2, 0) = (y1, 1– y1, 0). Составим уравнение 4y1 + 2(1– y1) + 3∙0 = 3, y1 = 1/2. Итак, получили решение: x = (1/2, 1/2), y = (1/2, 1/2, 0), ã = 3. Задачи к § 6 6.1. Имеется матрица , причем а* ≠ а*. Доказать, что решением игры будет: . 6.2. Рассмотрите игры 2×4 и 5×2 с матрицами потерь первого игрока соответственно , . Решите эти игры графически. § 7. A – игра порядка 3  3 Рассмотрим метод решения данной игры на следующем примере: дана матрица потерь первого игрока Поскольку a* = 2, a* = 0, то простая A–игра не имеет цены. Перейдем к отысканию цены ã и оптимальных стратегий x = (x1, x2, x3), ∑xi = 1; y = (y1, y2, y3), ∑yj = 1 в расширенной A – игре. Для этого рассмотрим три линейных функции fj(x1, x2) = a1jx1 + a2jx2 + a3j(1 – x1 – x2), j = 1, 2, 3, т.е. f1(x1, x2) = x1 + 2x2 – (1 – x1 – x2) = 2x1 + 3x2 – 1, f2(x1, x2) = 2x1 + 0x2 + (1 – x1 – x2) = x1 – x2 + 1, f3(x1, x2) = -3x1 + x2 + 2(1 – x1 – x2) = -5x1 – x2 + 2. Число fj(x1, x2) равно потерям первого игрока, если он применяет свою смешанную стратегию x = (x1, x2, 1 – x1 – x2), а второй игрок – чистую стратегию j. Попарно приравниваем эти функции: f1(x1, x2) = f2(x1, x2), f1(x1, x2) = f3(x1, x2), f2(x1, x2) = f3(x1, x2). Получаем три линейных уравнения для переменных x1, x2: l1: x1 + 4x2 = 2, l2: 7x1 + 4x2 = 3, l3: 6x1 = 1. На плоскости переменных x1, x2 построим эти прямые, предварительно определив область определения: x3 = 1 – x1 – x2  0,  x1 + x2  1; xi  0 Рис.1 Находим координаты точек, входящих в область определения и находящихся на пересечениях прямых (между собой, а также с границей), затем подставляем их в функции и находим потери. Для более наглядного представления составим таблицу, где первая колонка – это номер точки; следующие три – значения функций f1, f2, f3 в этой точке; последняя – значение максимума в этой точке, т.е. f(x1, x2) = max{ f1(x1, x2), f2(x1, x2), f3(x1, x2)} N x1 x2 x3 f1 f2 f3 f 1 1 -1 1 2 2 2 1 1 2 -3 2 3 1 5 1 2 4 3/4 1/4 1 5/4 5/4 5/4 5 1/2 1/2 1/2 1/2 3/2 3/2 6 1/6 5/6 2/3 7/6 7/6 7/6 7 3/7 4/7 -1/7 10/7 -1/7 10/7 8 2/3 1/3 4/3 4/3 -5/3 4/3 9 1/6 5/6 11/6 1/3 1/3 11/6 10 1/6 11/24 3/8 17/24 17/24 17/24 17/24 Далее находим минимум чисел, стоящих в восьмом столбце; это и будет искомая цена ã в расширенной А–игре (у нас ã = 17/24). Координаты соответствующей точки определяют оптимальную стратегию первого игрока (у нас x = (4/24, 11/24, 9/24)). Осталось найти оптимальную стратегию y = (y1, y2, y3) второго игрока. Это можно сделать с помощью лемм 2, 3 (§ 4), однако мы поступим иначе. Возьмем три линейные функции gi(y1, y2) = ai1y1 + ai2y2 + ai3(1 – y1 – y2), i = 1, 2, 3, т.е. g1(y1, y2) = y1 + 2y2 – 3(1 – y1 – y2), g2(y1, y2) = 2y1 + 0y2 + (1 – y1 – y2), g3(y1, y2) = -y1 + y2 + 2(1 – y1 – y2), и составим три линейных уравнения, приравняв их попарно: g1(y1, y2) = g2(y1, y2), g1(y1, y2) = g3(y1, y2), g2(y1, y2) = g3(y1, y2). На плоскости переменных y1, y2 построим прямые, соответствующие уравнениям l1, l2, l3, предварительно определив область определения (y3 = 1 – y1 – y2  0,  y1 + y2  1; yi  0). l1: 3y1 + 6y2 = 4, l2: 7y1 + 6y2 = 5, l3: 4y1 = 1. Рис.2 Находим координаты точек, входящих в область определения и находящихся на на пересечениях прямых (между собой, а также с границей), затем подставляем их в функции и находим потери. Заполним следующую таблицу, где g(y1, y2) = min{ g1(y1, y2), g2(y1, y2), g3(y1, y2): N y1 y2 y3 g1 g2 g3 g 1 1 -3 1 2 -3 2 1 2 1 3 1 1 2 -1 -1 4 5/7 2/7 -1/7 12/7 -1/7 -1/7 5 1/4 3/4 -8/4 5/4 5/4 -8/4 6 2/3 1/3 1/3 1/3 4/3 1/3 7 5/6 1/6 7/6 1/6 7/6 1/6 8 1/4 3/4 7/4 2/4 2/4 2/4 9 2/3 1/3 4/3 4/3 -1/3 -1/3 10 6/24 13/24 5/24 17/24 17/24 17/24 17/24 Далее находим максимум чисел, стоящих в восьмом столбце (это, очевидно, цена игры ã = 17/24; попутно получаем проверку вычислений, так как полученное число совпало с найденным ранее). Координаты точки, стоящей в этой строке, соответствуют искомой оптимальной стратегии второго игрока y = (6/24, 13/24, 5/24). Итак, мы получили ответ: ã = 17/24, x = (4/24, 11/24, 9/24), y = (6/24, 13/24, 5/24). Задачи к § 7 7.1. Найти графическим методом решения следующих А-игр: § 8. Расширенная A – игра и задача линейного программирования Для любой расширенной А–игры с матрицей А размера n  m можно построить пару двойственных задач линейного программирования, эквивалентных А – игре. Пусть даны: матрица Ā размера , вектор-строка b длины . Условимся для двух векторов a = (a1, , ak), b = (b1, , bk) длины k писать a  b, если ai  bi для i = 1, , k. Сформулируем пару задач линейного программирования и расширенную А-игру в матричной форме. Прямая задача линейного программирования Найти вектор , удовлетворяющий следующим условиям: при ограничениях: где Двойственная задача линейного программирования Найти вектор , удовлетворяющий следуюшим условиям: при ограничениях: Расширенная А – игра Найти векторы x = (x1, , xn), y = (y1, , ym) и число ã, удовлетворяющие условиям: Где ek = (1, , 1) и A – матрица размера n  m. Предположим, что матрица A расширенной A–игры имеет только положительные элементы (aij  0) и x, y – оптимальные стратегии игры с положительной ценой ã. Введем набор элементов, определяющих пару двойственных задач линейного программирования: Решением этих задач будет: Прямая задача будет выглядеть: при ограничениях: Двойственная задача: при ограничениях: Действительно ли являются решениями задач? Проверяем условия: удовлетворяют необходимым условиям. Предположим, что есть еще один, претендующий на решение, вектор , удовлетворяющий условиям: и такой, что Обозначим Очевидно, что вектор z удовлетворяет соотношениям В силу лемм (§4) строгое неравенство здесь невозможно, поэтому вектор не является решением. Аналогично доказывается и для . Таким образом доказывается, что векторы являются решением пары задач линейного программирования. Рассмотрим обратную связь. Предположим, что имеется матрица А с положительными элементами и являются решением пары задач линейного программирования. Тогда оптимальные стратегии имеют вид: где Если матрица А имеет неположительные элементы, то прибавляем к каждому элементу этой матрицы положительное число d такое, чтобы новая матрица была положительной, где Для матрицы A/ c положительными элементами можно построить пару задач линейного программирования. Для такой матрицы оптимальные стратегии x/, y/ совпадают с оптимальными стратегиями x, y, а цена игры Задачи к § 8 8.1. Составить пару задач линейного программирования, эквивалентных игре 7.1. 8.2. Рассмотрите игру, в которой два противника А и В ведут борьбу за два стратегических пункта. Под командованием А находятся два полка, под командованием В – три. Обе стороны должны распределить свои силы между двумя пунктами. Пусть n1 и n2 – количество полков, посланных со стороны А на пункты 1 и 2 соответственно. Аналогично пусть m1 и m2 – количество полков, посланных В на пункты 1 и 2. Выигрыш В подсчитывается следующим образом. Если m1 > n1, он получает на первой позиции 2n1+1 очков, если m1 < n1, он теряет на первой позиции 2m1+1 очков. Аналогично осуществляется подсчет на второй позиции. И наконец, если число полков на какой-нибудь позиции с каждой стороны одно и то же, то каждая сторона на этой позиции получает ноль очков. Сформулируйте задачу как расширенную А-игру и решите ее методом линейного программирования. § 9. Некоторые критерии принятия решений в условиях неопределенности Данные критерии применяются в случае, если неизвестны априорные вероятности. Наряду с минимаксным критерием будем применять следующие: а) Лапласа; б) Сэвиджа; в) Гурвица. Критерий Лапласа В основе этого критерия лежит так называемый принцип недостаточного обоснования. Поскольку вероятности состояний Θ­1, … ,Θn неизвестны, то информация, необходимая для вывода того, что эти вероятности различны, отсутствует, и, так как принцип недостаточного обоснования утверждает противоположное, считается, что эти вероятности равны: q1 = q2 =…= qm. Предположим, что имеется матрица потерь первого игрока и у второго игрока имеется m стратегий, и эти стратегии имеют равные вероятности: Оптимальной для первого игрока считается та стратегия, которая дает минимум средним потерям (для матрицы выигрышей максимум). Пример 1. Одно из предприятий должно определить уровень предложения услуг так, чтобы удовлетворить потребности клиентов в течении предстоящих праздников. Точное число клиентов неизвестно, но ожидается, что оно может принимать следующие значения: 200, 250, 300, 350. Для каждого из возможных случаев существует наилучший уровень предложения, который является стратегией первого игрока. Предположим, что матрица затрат предприятия имеет вид: . Верхняя цена a* = 21 (δ3 – минимаксная стратегия) Вводим qj = P(θ = θj) = 1/4. Тогда, средние потери: a(δ1) = 1/4(5 + 10 + 18 + 25) = 14,5 a(δ2) = 1/4(8 + 7 + 8 + 23) = 11,5 a(δ3) = 1/4(21 + 18 + 12 + 21) = 18 a(δ4) = 1/4(30 + 22 + 19 + 15) = 21,5 Выбираем минимальное значение, и это значение (11,5) соответствует стратегии δ2 , следовательно, она является оптимальной стратегией первого игрока по критерию Лапласа. Критерий Сэвиджа Для обоснования использования критерия Сэвиджа обычно приводят такой пример Пример 2. Пусть матрица потерь первого игрока имеет вид Цена игры a* = 10000, следовательно, δ2 – минимаксная стратегия, что является нелогичным. Предположим, что - матрица потерь или матрица выигрышей первого игрока. Вводится следующая матрица , где Матрица В интерпретируется как матрица сожаления первого игрока по поводу того, что он не выбрал наилучшей стратегии. Применительно к примеру 2 мы получим: Цена игры а* = 1000, следовательно, δ1 – оптимальная стратегия по критерию Сэвиджа, что является более логичным решением. Отметим, что независимо от того А – матрица потерь или выигрышей, В – матрица потерь и для нахождения решения игры к матрице В применяется минимаксный подход. Критерий Гурвица Этот критерий учитывает склонность лица, принимающего решение к оптимизму или пессимизму. Предположим, что - матрица потерь первого игрока. Очевидно, что для первого игрока - оптимистический выбор стратегии осуществляется по критерию:, а пессимистический выбор - по критерию:. Вводится параметр α, и составляется функция потерь где α – показатель оптимизма, и выбирается стратегия по этому критерию. Когда нет точного значения α, оно берется равным 1/2. Пример 3. Пусть в условиях примера 1 данного параграфа α = 1/2. Вычисления приведены в следующей таблице: δ1 5 25 15 δ2 7 23 15 δ3 12 21 16,5 δ4 15 30 22,5 По данным таблицы, δ1 и δ2 – оптимальные стратегии по критерию Гурвица. Задачи к § 9 9.1. Найти оптимальные стратегии игроков с помощью критериев принятия решений в условиях неопределенности. Рассмотреть матрицу А как а) матрицу потерь и б) матрицу выигрышей первого игрока. 9.2. Один из N станков должен быть выбран для изготовления партии изделий, размер которой может принимать любое значение в пределах Q1 ≤ Q ≤ Q2. Производственные затраты для i-го станка задаются следующей функцией: Найти решение используя все вышеописанные критерии. § 10. Байесовский подход в теории игр Предположим, что - матрица потерь первого игрока. Предполагается, что известны вероятности, с которыми второй игрок применяет свои стратегии: qj = P(θ = θj), j=1,2,…,m, . Для каждой стратегии δi считаются средние потери . Байесовской называется та стратегия, для которой средние потери минимальны: δ*: а(δ*) =. Пример 1. Пусть первый игрок имеет 106 руб.; он может хранить их дома (стратегия δ1) либо поместить в банк под 10% годовых (стратегия δ2). Его противник (банк) имеет тоже две стратегии: θ1 – нормальная работа банка в течении года; θ2 – в течении года банк лопнет и вкладчик потеряет свои деньги. Матрица потерь первого игрока имеет вид: Поскольку а* = а* = 0, то игра имеет цену а = 0 и оптимальная (чистая) стратегия первого игрока в этой А-игре существует. Это δ1, т.е. первый игрок, следующий минимаксной стратегии, должен хранить свои деньги дома. Рассмотрим теперь байесовскую постановку данной задачи. Пусть априорное распределение имеет вид q1 = P(θ = θ1) = 0,9999, q2 = P(θ = θ2) = 0,0001. Иначе говоря, вероятность разорения банка в течении года равна 0,0001, т.е. достаточно мала. Тогда средние (байесовские) потери первого игрока равны соответственно а(δ1) = 0q1 + 0q2 = 0, a(δ2) = q1(-105) + q2106 = -99890. Поэтому байесовская стратегия в этой задаче равна δ2. Иначе говоря, банки разоряются очень редко (в странах с нормальной банковской системой), поэтому деньги хранить выгоднее в банке, чем дома. Задачи к § 10 10.1. Рассмотрите игру с матрицей потерь первого игрока Найти: а) байесовскую стратегию первого игрока, если известно априорное распределение стратегий второго игрока; б) подобрать такое априорное распределение (q1, q2, q3), чтобы байесовская стратегия, отвечающая ему, имела вид (0,1,0). 10.2. Молодой бизнесмен М планирует посетить Объединенные Арабские Эмираты и с этой целью планирует занять в банке $5000. Если его дела пойдут успешно (стратегия θ1), он обещает через 3 месяца вернуть своему кредитору взятые деньги плюс 10%; в противном случае (стратегия θ2) он не сможет вернуть деньги. У банка есть тоже две стратегии: δ1 = {дать бизнесмену М деньги}; δ2 = {не дать бизнесмену М деньги}. а) Найти минимаксную стратегию банка; б) допустим известны qj, при каких значениях q2 байесовской стратегией банка будет δ1. § 11. Статистические игры Эти игры иначе называются играми с экспериментом. Всегда ли выгодно проводить эксперимент? Если цена игры (допустим, потери) плюс затраты на эксперимент меньше цены игры без эксперимента, то в этом случае имеет смысл перейти к статистической игре. Опишем статистическую игру на примере. Предположим, что у нас имеется матрица потерь первого игрока. Пусть δ1, δ2, δ3 – чистые стратегии первого игрока, θ1, θ2 – чистые стратегии второго игрока. Найдем a* = 3, a* = 2, a*≠ a* . Проводим эксперимент, который имеет следующие исходы: t1, t2, t3. Предположим, что известны вероятности P (ti/θj):. t1 t2 t3 θ1 0,6 0,25 0,15 θ2 0,2 0,3 0,5 Обозначим через Sijk стратегию первого игрока. Она интерпретируется так: если исходом эксперимента является t1, то первый игрок применит стратегию Si, если t2 – стратегию Sj, если t3 – Sk; i, j, k =1, 2, 3. Определенные таким образом стратегии будут чистыми стратегиями первого игрока в статистической игре. Всего таких стратегий будет где n – число стратегий первого игрока, k – число исходов в эксперименте. В нашем случае таких исходов будет 33=27. Определим потери первого игрока: L(Sijk, 1), L(Sijk, 2). Например, L(S231, 1) = 0,6*1 + 0,25*3 + 0,15*0 = 1,35, L(S231, 2) = 0,2*3 + 0,3*2 + 0,5*5 = 3,7. Мы получаем в данном случае 27 пар таких значений и получаем игру порядка 27  2 с матрицей потерь, элементами которой и являются эти значения. Составление этой матрицы предлагается читателю (см.задачу 11.1) Эту задачу можно решить обычными способами. Но мы перейдем к S-игре. На плоскости отмечаем точки Sijk(L(Sijk, 1), L(Sijk, 2)) (схематически – см.рис.1). Рис.1 Наряду с исходными чистыми стратегиями рассматриваем смешанные стратегии первого игрока. Класс всех смешанных стратегий S есть некоторое выпуклое множество: Решение в этой игре выглядит так: x = (x1, , x27). Для нахождения оптимальной стратегии можно применить два подхода: минимаксный и байесовский. Минимаксный подход Алгебраически: рассмотрим матрицу 27  2, затем процедурой доминирования приходим к матрице 7  2 и решаем задачу как игру n x 2. Графически: строим квадрат и увеличиваем стороны квадрата до касания с областью S (либо проводим биссектрису) и точка касания будет соответствовать минимаксному решению. Если первое касание происходит со стороной квадрата, то оптимальное решение находится среди чистых стратегий. Если первое касание происходит вершиной квадрата, то оптимальное решение находится среди смешанных стратегий. Если же сторона квадрата совпадает с ребром области S, то существуют альтернативные оптимальные решения. В рассмотренном примере первое касание происходит с вершиной квадрата (рис.2). Точка касания SM соответствует оптимальному решению. Рис. 2 Найдем точку SM. Как известно, SM = xS233 + (1-x)S333 или L(SM, 1) = xL(S233, 1) + (1-x)L(S333, 1) L(SM, 2) = xL(S233, 2) + (1-x)L(S333, 2) Эта точка является вершиной квадрата и значит, что её координаты равны. Т.е. приравниваем правые части уравнений и получаем, что x= 5/7. Стратегия SM выглядит следующим образом: с вероятностью 5/7 первый игрок применяет стратегию S233, а с вероятностью 2/7 – стратегию S333. Итак, оптимальная стратегия первого игрока записывается так: xM = (0,0, ..., 0, 5/7, 0, ..., 2/7). Байесовский подход Алгебраически: Пусть имеется априорная информация, т.е известны вероятности q1 = P( =1) и q2 = P( =2), q1 + q2 =1. Найдём средние потери первого игрока при стратегии S: Lср(S) = q1L(S, 1) + q2L(S, 2) Далее,среди них выберем минимальные, т.е S: minLcp(S) = Lcp(S). Графически: на плоскости строим прямую (линию уровня) q1L1 + q2L2 = d, взяв d произвольно. Затем двигаем эту линию произвольно до первого касания с S. Эта прямая будет либо касаться точкой, либо совпадать с ребром области S. Если это будет точка, то оптимальная стратегия находится среди чистых стратегий, если прямая совпадет с ребром области S, то это означает, что у первого игрока есть множество альтернативных оптимальных стратегий. Как видно, в этом подходе хотя бы одна чистая стратегия будет оптимальной. Пусть в рассматриваемом примере q1 = 1/3 и q2 = 2/3. Построим прямую 1/3L1 + 2/3L2 = d. Возьмем d = 1/3. В этом случае точка касания будет в точке S233. Найдем средние потери: Lcp(S233) = 1/3*1,8 + 2/3*2,2 = 2,06. Задачи к § 11 11.1. Привести полное решение примера, рассмотренного в § 11. 11.2. Когда мистер Смит вернулся домой, миссис Смит сообщила ему, что из коробки с бисквитами пропала дюжина бисквитов. Бисквиты мог съесть сын Джон или соседские дети, которые приходили днем в гости и были оставлены одни, когда миссис Смит на 10 минут отлучилась (она ездила на почту, чтобы отправить многочисленные поздравления с Рождеством многочисленным родственникам мужа). Мистер Смит считает, что ели сын Джон виноват, то его следует наказать. Он составил следующую матрицу потерь: Состояние природы 1 (наказать) 2 (не наказывать) 1 (виновен) 2 (невиновен) 1 4 2 Супруги Смит решают взять за основу своих действий следующий эксперимент: они наблюдают за сыном во время ужина и замечают, как он ест – охотно (t1), умеренно (t2), плохо (t3). Семейный врач предложил следующую оценку распределений вероятностей этих данных: Состояние природы t1 t2 t3 1 2 0,1 0,2 0,4 0,6 0,5 0,2 а) перечислить все чистые стратегии и найти для каждой отвечающие ей потери; б) изобразить стратегии в виде точек на плоскости; в) изобразить на плоскости класс всех смешанных стратегий и найти класс допустимых стратегий; г) на основе чистых допустимых стратегий сформулировать расширенную А-игру; Найти решение этой А-игры графически: а) используя минимаксный подход; б) используя байесовский подход при q1 = 1/3 и q2 = 2/3. § 12. Задача о линейной регрессии Предположим, что Х, Y – случайные величины, которые «связаны» какой-то зависимостью. Наша цель ­– построить такую функцию, которая бы позволяла для любого значения аргумента х «угадывать» значение случайной величины Y, соответствующее ситуации «{X = x}»: y = а + kx, (1) где а, k – функции от выборки а = a(X1Y1, ..., XnYn), k = k(X1Y1, ..., XnYn). Предположим, что у второго игрока имеется стратегия: θ = (x1y1, …, xnyn), а первый игрок в качестве стратегии δ = (a,k) может использовать любую линейную функцию δ = a + kх При рассмотрении этой задачи как задачи о наименьших квадратах, функция платежей задается так: Тогда решением задачи о наименьших квадратах будет стратегия δ* = (a*,k*), для которой потери будут наименьшими: Для нахождения экстремума составляется система: Решая эту систему, находим где – выборочное среднее Х; – выборочное среднее Y; – выборочная дисперсия Х; – выборочный центрированный смешанный момент. Таким образом искомая линейная функция имеет вид: Рассмотрим другую постановку этой задачи – как задачу о линейной регрессии. Пусть Х – неслучайная величина, а Y нормально распределенная случайная величина с параметрами Линейную функцию (1) будем искать в виде где α*, β* – какие-то оценки для параметров α, β. Поскольку оценки максимального правдоподобия обладают многими хорошими свойствами, остановимся на них. Для построения оценок максимального правдоподобия рассмотрим функцию правдоподобия: Логарифмическая функция правдоподобия: Составляется система: Решения этой системы и будут искомыми оценками: Таким образом, искомая линейная функция найдена: В данном подходе прогнозируется среднее значение случайной величины Y. Задачи к § 12 12.1. Для исследования зависимости объемов производства (Y) от основных фондов (Х) получены данные по 8 предприятиям (в млн. руб.) за год: (12, 210), (17, 220), (22, 230), (27,240), (32, 250), (37, 260), (42, 270), (47, 280). Найти уравнение линейной регрессии Y по X, отражающее зависимость объема производства от основных фондов. 12.2. Рассмотрим данные по совокупному денежному доходу населения (X) и по величине прожиточного минимума (Y) с 1992 по 1998 гг: (7,1; 1,9), (79,9; 20,6), (360,9; 86,6), (942,3; 264,1), (1374,5; 369,4), (1643,3; 411,2), (1700,4; 493,3). Найти уравнение линейной регрессии Y по X, построить линию регрессии. § 13. Принятие решений в условиях риска Как и в случае принятия решения в условиях неопределенности здесь решение принимается в условиях ограниченности или неточности информации. Степень неполноты данных выражается через функцию распределения. С точки зрения наличия исходных данных определенность и неопределенность представляет два крайних случая, а риск определяет промежуточную ситуацию. Мы будем рассматривать следующие критерии принятия решения в условиях риска: 1) критерий ожидаемого значения (прибыль или расход); 2) комбинация ожидаемого значения и дисперсии; 3) критерий известного предельного уровня; 4) критерий наиболее вероятного события в будущем. 1. Критерий ожидаемого значения Количественно этот критерий можно выразить в денежных единицах или в единицах полезности денег. Продемонстрируем это на примере. Предположим, что инвестиции $20 тыс. дают с равными вероятностями либо нулевой доход, либо $100 тыс. В денежных единицах ожидаемый доход составляет: 0,5·0 + 0,5·100 – 20 = $30 тыс. Можно принять решение о вложении денег, однако это решение не в равной степени приемлемо для всех вкладчиков. Допустим имеются два вкладчика А и В. У А средства ограничены и потеря $20 тыс. приведет его к банкротству. В имеет средства значительно превышающие $20 тыс., это бездействующий капитал и он может рисковать. Предположим, что Z – случайная величина с математическим ожиданием EZ и дисперсией DZ. Пусть имеется выборка z1, z2,…, zn объема n. Тогда выборочное среднее равно . Выборочное среднее имеет дисперсию При n → ∞ . Отсюда, можно сделать следующий вывод: использование критерия ожидаемого значения допустимо лишь в том случае, когда одно и то же решение приходится принимать достаточно большое число раз. Пример 1. Предположим, что есть необходимость профилактического ремонта оборудования. Требуется принять решение о том, когда следует проводить ремонт какого-либо станка чтобы минимизировать потери. Если весь временной отрезок разбит на равные периоды, то решение заключается в определении оптимального числа периодов между двумя периодами. Предположим, что имеется n станков, через Т интервал времени выполняется профилактический ремонт всех n станков. Определить оптимальное значение Т, при котором минимизируются затраты на ремонт вышедших из строя станков и проведение профилактического ремонта в расчете на один интервал времени. Пусть Рt – вероятность выхода из строя одного станка в момент времени Т ; nt – случайная величина, число вышедших из строя станков (имеет биномиальное распределение с параметрами n, pt, таким образом математическое ожидание Ent = npt); c1 – затраты на ремонт вышедшего из строя станка; c2 – затраты на профилактический ремонт; EC(T) – ожидаемые затраты за один интервал времени. Из условий получим Требуется найти значение Т, удовлетворяющее условиям . Покажем это на нашем примере. Пусть С1 = 100, С2 = 10, n = 50. Составим следующую таблицу: T Pt EC(T) 1 0,05 500 2 0,07 0,05 375 3 0,10 0,12 366,7 4 0,13 0,22 400 5 0,18 0,35 450 Из таблицы видно, что Т* = minT = 366,7. Т.е. ремонт следует производить через 3 периода. 2. Критерий ожидаемое значение – дисперсия Предположим, что z – случайная величина с дисперсией Dz. Выборочное среднее имеет дисперсию Если дисперсия Dz уменьшается, то дисперсия также уменьшается, и это означает, что вероятность того, что будет приближаться к Ez, увеличивается. В условиях этого критерия выбирается: max{Ez – kDz} или min{Ez + kDz}, где k – уровень не склонности к риску (постоянная величина). Пример 2. В условиях предыдущего примера посчитаем дисперсию затрат за один период времени. где nt – случайная величина, которая имеет биномиальное распределение (nt  Dnt = nPt(1-Pt)). Выбираем то значение Т, которое удовлетворяет: min{EC(T) + kDC(T)}. Пусть k = 1, С1 = 100, С2 = 10, n = 50. T Pt Pt2 EC(T)+DC(T) 1 0,05 0,0025 500 2 0,07 0,0049 0,05 0,025 6312,5 3 0,10 0,01 0,12 0,074 6622,22 4 0,13 0,0169 0,22 0,0174 6731,25 5 0,18 0,0324 0,35 0,0343 6764 Из таблицы находим Т* = minT = 500. 3. Критерий предельного уровня Этот критерий не дает оптимального решения, а соответствует определению приемлемого способа действий. Пример 3. Пусть величина спроса  на некоторый товар задается непрерывной функцией распределения F(x). Если запасы в начальный момент не велики, в дальнейшем возможен дефицит. В противном случае к концу рассматриваемого периода запасы нереализованного товара могут оказаться очень большими. Человек, который принимает решение, может установить необходимый уровень запаса таким образом, чтобы величина ожидаемого дефицита не больше А1, а величина излишков не превосходила А2. Необходимый уровень запаса I определяется следующим образом: Пример 4. Пусть Тогда Пусть A1 = 2, A2 = 4. Тогда: Ответ: I  [10; 20]. 4. Критерий наиболее вероятного исхода Этот критерий основан на преобразовании случайной ситуации в детерминированную путем замены случайной величины единственным значением, имеющим наибольшую вероятность реализации. Допустим, имеется изделие j и доход Cj. Pj – вероятность того, что доход принимает это значение Pj = P(C=Cj). Критерий говорит, что надо выбрать такое значение Cj*, чтобы Задачи к § 13 13.1. В производственном процессе партии товаров, имеющие 8%, 10%, 12% и 14% брака выпускаются с вероятностью 0,4; 0,3; 0,25; и 0,05 соответственно. Производитель связан контрактами с тремя потребителями. В них оговорено, что процент брака в партиях, направляемых потребителям А, В и С не должен превышать 8%, 12% и 14% соответственно. Если процент брака превышает обусловленного, то штраф составляет 100 долларов за 1% превышения. С другой стороны производство партии более высокого качества, чем требуемое, приводит к увеличению затрат производителя на 50 долларов за 1%. Кто из потребителей будет иметь наибольший приоритет при выполнении заказа, если партия не проверяется перед отправкой? 13.2. Спрос на некоторое изделие описывается следующей таблицей распределения: X 1 2 3 4 5 P 0,1 0,15 0,4 0,15 0,1 0,1 Определить уровень запасов, при котором вероятность полного истощения запасов не превышает 0,45. Определите также уровень запасов при условии, что среднее значение дефицита и превышения запаса не должны быть выше 1 и 2 единиц соответственно. 13.3. Автомат производит  тысяч единиц некоторого продукта ежедневно. Если  увеличивается, доля брака p возрастает. Плотность распределения случайной величины p дается следующей формулой: Каждое бракованное изделие приносит убыток в 50 долларов. Годное изделие дает прибыль 5 долларов. Определите, при каком  ожидаемая прибыль принимает максимальное значение. Примените критерий ожидаемое значение – дисперсия. Сравните оптимальные решения для значение показателя несклонности к риску k = 1, 2, 5. § 14. Игры с ненулевой суммой Пусть имеются два игрока и рассматривается матрица выигрышей каждого игрока в отдельности. Эти матрицы совмещают в одну, и полученную матрицу называют матрицей игры (а саму игру называют биматричной игрой). Пример 1. Пусть А1 – матрица выигрышей первого игрока, А2 – матрица выигрышей второго игрока. Тогда совместная матрица игры С будет выглядеть следующим образом: Игры с ненулевой суммой делятся на: • некооперативные (игроки не могут договориться); • кооперативные (игроки согласовывают свои действия перед игрой). А. Некооперативные игры В играх с ненулевой суммой два игрока могут выигрывать и проигрывать одновременно. В некооперативных (или бескоалиционных) играх игроки принимают решения независимо друг от друга. Решение некооперативных игр основывается на нахождении точек равновесия игры. Пусть - матрицы выигрышей первого и второго игрока соответственно. Матрица игры выглядит так: и пусть (x*, y*) – точка равновесия. Тогда средние выигрыши первого и второго игрока будут равны, соответственно: Определение 1. Точка (x*, y*) – точка равновесия по Нэшу, если выполняются следующие условия: Ни одному из игроков не выгодно отклоняться от стратегии точки равновесия, если второй придерживается этой стратегии. Приведем без доказательства следующую теорему. Теорема Нэша. Каждая биматричная игра имеет по крайней мере одну точку равновесия. В общем случае равновесие может быть не единственным и каждому из них могут соответствовать различные значения выигрыша каждого из игроков. Для игры 2×2 достаточными условиями для нахождения точки равновесия по Нэшу будут являться следующие неравенства: , Рассмотрим несколько примеров Пример 1 (Дилемма заключенных). Два преступника ожидают приговора суда за совершенное преступление. Адвокат конфиденциально предлагает каждому из них облегчить их участь, даже освободить, если он сознается и даст показания против сообщника, которому в этом случае грозит тюремное заключение сроком на 10 лет. Если никто не сознается, то обоим угрожает заключение в один год по обвинению в незначительном преступлении. Если сознаются оба, то, с учетом чистосердечного признания, обоим грозит срок 5 лет. Каждый игрок имеет две стратегии: δ1 = {сознаться}; θ1 = {сознаться}; δ2 = {не сознаться}; θ2 = {не сознаться}. Составим матрицу выигрышей игроков: Выделим матрицы А1, А2 – матрицы выигрышей первого и второго игроков соответственно. ; . Найдём точку равновесия. Пусть x = (x1, 1-x1); y = (y1, 1-y1). Вычислим Для точки равновесия имеет место , отсюда . Находим решение системы геометрически (4 системы). Нужно найти такую точку, чтобы координаты удовлетворяли неравенствам: . Эта точка (Проверьте самостоятельно). Тогда, пара стратегий по Нэшу выглядит так . Б. Кооперативные игры Напомним еще раз, что кооперативной игрой называется игра с ненулевой суммой, в которой игрокам разрешается перед игрой обсуждать свои стратегии и договариваться о совместных действиях. Основная цель в этой игре – дележ общего выигрыша между членами коалиции. Рассмотрим сначала кооперативную игру двух лиц на примере. Пример 2. Пусть дана матрица кооперативной игры . Отметим на координатной плоскости (рис.1) точки,, соответствующие каждому элементу матрицы C ( их 4). Рис.1 Отмечаем также точку Т = (T1,T2) – точку угрозы, где T1, T2 – выигрыши игроков без вступления в коалицию. В нашем примере Т = (1, 1). Северо-восточная граница области называется Парето-оптимальным множеством. Та часть Парето-оптимального множества, которая находится выше и правее точки угрозы называется переговорным множеством. В данном случае Парето-оптимальное множество совпадает с переговорным множеством (АВ). Вообще говоря, при решении кооперативной игры достаточно ограничиться нахождением переговорного множества. Однако, здесь мы также можем указать точку равновесия по Нэшу. Для этого обозначим ƒ(L1,L2) = (L1 - T1)( L2 – T2) Точка равновесия по Нэшу удовлетворяет условию: Найдем наибольшее значение функции на АВ. Из уравнения прямой АВ - L1 + L2 = 5 выразим L2 = 5 – L1 и подставим в: f(L1) = (L1 – 1)(5 – L1 – 1) = , и найдем наибольшее значение функции одной переменной на отрезке: . Отсюда, = 2,5; = 2,5. Это те значения, которые максимизируют функцию ƒ(L1,L2) в переговорном множестве. На рис.1 точка N = (2,5; 2,5) – точка равновесия по Нэшу. Затронем теперь общие вопросы кооперативных игр. Предположим, что имеется множество игроков N = {1, , n}. K – некоторое подмножество K  N, состоящее из r  n игроков. - число возможных коалиций игроков, договаривающихся о совместных действиях. Определение 1. Функция V , ставящая в соответствии каждой коалиции K наибольший выигрыш, называется характеристической функцией игры. Определение 2. Характеристическая функция V(K) называется простой, если она принимает два значения: 0 и 1. Определение 3. Если характеристическая функция V простая, то коалиции K, для которых V(K) = 1 называются выигрывающими, а для которых V(K) = 0 – проигрывающими. Свойства характеристической функции. 1) персональность (коалиция, не содержащая ни одного игрока, ничего не выигрывает). V() = 0. 2) супераддитивность V(KL)  V(K) +V(L), K,L N, KL = . 3) дополнительность V(K) + V(N \K) = V(N). Обозначим через Xi выигрыш i-го игрока. И рассмотрим следующие два условия: 1) индивидуальная рациональность Xi  V(i), iN. 2) коллективная рациональность Определение 4. Вектор выигрышей X = (X1, , Xn), удовлетворяющий условиям 1 и 2, называется дележом в условиях характеристической функции V. Определение 5. Множество {N, V}, удовлетворяющее условиям 1 и 2, называется классической кооперативной игрой. Теорема 1. Для того, чтобы X = (X1, , Xn) был дележом в классической кооперативной игре, необходимо и достаточно, чтобы Определение 6. Кооперативные игры называются существенными, если для любых коалиций K и L выполняется неравенство: V(K) +V(L) < V(KL). Если выполняется неравенство V(K) + V(L) = V(KL), то такая игра называется несущественной. Рассмотрим следующие свойства: 1) для того, чтобы характеристическая функция V была аддитивной (кооперативная игра несущественной), необходимо и достаточно выполнения следующего равенства: 2) в несущественной игре имеется только один дележ: {V(1), V(2), , V(n)}. 3) в существенной игре более, чем одному игроку множество дележей бесконечно: Определение 7. Пусть имеется два дележа X = (X1, , Xn), Y = (Y1, , Yn), {N, V} и некоторая коалиция K. Тогда дележ X доминирует Y по коалиции K, если выполняются два условия: 1) - эффективность доминирующего дележа, 2) Xi > Yi, i K – свойство предпочтительности. Соотношение доминирования возможно не по всякой коалиции. Например, невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков. В любой несущественной игре имеется только один дележ, поэтому здесь доминирования нет. Поскольку вариантов дележа много, необходимо выделить дележи, которые не доминируются никакими другими дележами. Такие дележи называются вполне устойчивыми, а множество таких дележей называется С-ядром. Теорема 2. Для того, чтобы дележ X принадлежал С-ядру игры {N, V}, необходимо и достаточно, чтобы для любой коалиции K выполнялось неравенство Замечания: 1) в несущественной игре С-ядро существует и состоит из единственного дележа этой игры; 2) во всякой существенной игре с постоянной суммой С-ядро пусто. Дж.фон Нейман и О.Моргенштерн предложили следующее решение кооперативной игры. Определение 8. Решением по Нейману-Моргенштерну кооперативной игры R называется множество дележей, удовлетворяющее условиям: 1) внутренняя устойчивость (дележи из решения нельзя противопоставить друг другу); 2) внешняя устойчивость (имеется возможность каждому отклонению от решения противопоставить некоторый дележ, принадлежащий решению). Теорема 3. Если в кооперативной игре существует С-ядро С и решение R, то С < R. Решение по Нейману-Моргенштерну обладает следующим свойством: решение кооперативной игры не может состоять только из одного дележа, так как в этом случае характеристическая функция игры – несущественная. Решение по Нейману-Моргенштерну имеет ряд недостатков, которые сводятся к следующему: принцип оптимальности, приводящий к решению по Нейману, не является полным. Это означает, что он не в состоянии указать игрокам единственную систему норм распределения дележа. Еще одним подходом к поиску решения кооперативной игры является подход Шепли, основанный на аксиомах, отражающих справедливость дележей игры. Определение 9. Носителем игры с характеристической функцией V {N, V} называется такая коалиция T, что для любой другой коалиции S выполняется следующее равенство: V(S) = V(ST). Т.е. любой игрок, не принадлежащий коалиции T, является нейтральным. Он не может ничего внести в коалицию и ему ничего не следует выделять из общих средств. Предположим, что П - любая перестановка игроков множества N. Через ПV = U обозначим характеристическую функцию такой игры, что для коалиции S = {i1, , iS} имеет место следующее: U(П(i1), , П(iS)) = V(S). Аксиомы Шепли. 1) Эффективность. Если S – любой носитель игры {N, V}, то При разделении общего выигрыша носителя игры ничего не выделять на долю посторонних. 2) Симметрия. Для любой перестановки П и i N, выполняется следующее: Игроки, одинаково входящие в игру, должны получать одинаковые выигрыши. 3) Агрегация. Если есть две игры с характеристическими функциями V/ и V//, то При участии игроков в двух играх, их выигрыши в отдельных играх должны складываться. Определение 10. Вектором цен (вектором Шепли) игры с характеристической функцией {N, V} называется n-мерный вектор удовлетворяющий аксиомам Шепли. Терема 4. (Шепли) Существует единственная функция , определенная для всех игр, и удовлетворяющая аксиомам Шепли. Определение 11. Характеристическая функция WS(T), определенная для любой коалиции S называется простейшей, если Пусть i(V) – компоненты вектора Шепли, t – число элементов множества T. Тогда Вектор Шепли интерпретируется следующим образом: предельная величина, которую вносит i-ый игрок в коалицию T, выражается V(T) – V(T\{i}), и считается выигрышем i-го игрока. Если обозначим через i(T) вероятность того, что i-ый игрок вступит в коалицию, то выигрыш i-го игрока составит: Суммирование ведется по всем выигрывающим коалициям T, при условии, что коалиция T\{i} не является выигрывающей. Пример. Рассмотрим корпорацию из четырех акционеров, имеющих акции в следущих количествах: а1=10; а2=20; а3=30; а4=40. Предположим, что любое решение утверждается акционерами, имеющими в сумме большинство акций, и это решение считается выигрышем, равным 1. Данную ситуацию можем рассмотреть как игру четырёх участников, в которой выигрывающими будут следующие коалиции: . Определим компоненты вектора Шепли. При нахождении учтем, что имеется только одна коалиция T={1; 2; 3}, которая выигрывает, а коалиция T\{1} = {2; 3} не выигрывает. В этой коалиции имеется три игрока, т.е. t = 3, поэтому Теперь определим все выигрывающие коалиции, но не выигрывающие без второго игрока. Таких коалиций три: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому . Аналогично получаем, что . Таким образом, вектор Шепли выглядит так: . Замечание. Если считать, что вес голоса акционера пропорционален количеству имеющихся у него акций, то получим вектор голосования (0,1; 0,2; 0,3; 0,4), который, как видно, отличается от вектора Шепли. Задачи к § 14 14.1. Пусть студент предполагает сдать зачет преподавателю. Чтобы получить зачет студент должен правильно ответить хотя бы на два из трех предложенных вопросов. Сформулируйте задачу как игру с ненулевой суммой, найдите решение. 14.2. На просмотр фильма в кинотеатре школьникам выдали билеты. Количество билетов ограничено. На два класса администрация выделила 60 билетов, но впереди контрольная по математике, и администрация решила учесть результаты контрольной. Если один из классов пишет троек, то он получает 60 билетов. Если два класса не получают тройки, то каждый получит по 30 билетов. Если ни один из классов не пишет без тоек, то они получают по 15 билетов. Сформулируйте задачу как игру с ненулевой суммой, найдите решение. 14.3. Пяти предпринимателям предложили проинвестировать проект, стоимость которого составляет $1100 . У предпринимателей имеются $200, $300, $500, $600 и $800, соответственно. Проект отдадут тем предпринимателям, у которых будет необходимая сумма для его финансирования. Найти вектор Шепли. 14.4. Инвесторы решают вопрос о направлении средств в те или иные отрасли страны N. После дискуссий основная масса инвесторов решила из множества вариантов вложений выбрать три наиболее привлекательных и обсудить их отдельно. Одновременно с этим обсуждением правительство на своем заседании рассматривает несколько альтернативных стратетий развития экономики на ближайшие несколько лет. Инвесторы стоят перед выбором между инвестициями в нефтедобывающую, лесоперерабатывающую, автомобилестроительную отрасли. В одно и то же время с их закрытым совещанием происходит закрытое заседание правительства, на котором оно должно сделать выбор между преимущественным развитием нефтедобычи, железных дорог, электроэнергетики или жилищного комплекса. Сформулируйте задачу как игру с ненулевой суммой, составлением матрицы игры. 14.5. У торговой фирмы есть две грузовые машины, которые возвращаются из разных городов. Фирме требуется срочно отправить груз в город N. Если водители приедут точно по графику или раньше, и отправяться в срочную командировку, то у каждого из них будет простой в два дня. Если оба водителя опоздают, то у них будет по одному дню простоя. Если один из них приедет вовремя или раньше и отправиться в город N, то у него не будет простоя, а у другого будет простой в пять дня. Сформулируйте задачу как игру с ненулевой суммой, найдите решение. § 15. Многоэтапный процесс принятия решений Рассмотрим игру, в которой игроки принимают решения поочередно, зная о том, какую стратегию в предыдущем шаге применил противник. Такие игры также называют позиционными играми. Анализ такой игры проведем на примере. Пример. Фирма (первый игрок) может принять решение о строительстве крупного или небольшого предприятия. Небольшое предприятие впоследствии можно расширить. Решение определяется будущим спросом. Если спрос на продукцию большой, то строится крупное предприятие. Условие задачи представлено в виде так называемого «дерева решений»: где - решающие вершины, т.е те вершины, где первый игрок принимает решение, - случайные вершины. Определим действия предприятия на 10 лет. Сначала определим, какое решение примет первый игрок в решающей вершине 4, а затем в вершине 1. Для этого вычислим средние величины прибыли (обозначим через X) в вершине 4 при расширении и без расширения. При расширении: ; без расширения: Поскольку, ожидаемая чистая прибыль без расширения больше, то в вершине 4 выгоднее не проводить расширения. Считая, что за последние восемь лет при этом мы получим чистую прибыль, равную $1,9 млн. мы переходим к вершине 1. При строительстве крупного предприятия чистая прибыль составит: а при строительстве небольшого предприятия: Сравнив полученные значения прибыли, мы приходим к выводу, что оптимальным решением в вершине 1 является решение о строительстве крупного предприятия. Задачи к § 15 15.1. Изменим условия примера, рассмотренного в § 15 следующим образом. Имеется три вида спроса: высокий (с вероятностью 0,6), средний (0,3) и низкий (0,1). При переходе предприятия из состояния «3» в состояние «4» при высоком спросе ежегодный доход составляет $300 тыс. Годовые доходы составляют: состояние «2» - высокий спрос – $1млн., • средний спрос – $400 тыс., • низкий спрос – $200 тыс., состояние «5» – высокий спрос – $900 тыс., • средний спрос – $400 тыс., • низкий спрос – $200 тыс., состояние «6» – высокий спрос – $300 тыс., • средний спрос – $250 тыс., • низкий спрос – $200 тыс., состояние «3» – средний спрос – $250 тыс., - низкий спрос – $200 тыс. Требуется составить дерево решений и определить действия предприятия. 15.2. В рамках задачи 15.1 допустим вероятности высокого и низкого спроса неизвестны. Какова должна быть вероятность высокого спроса, чтобы фирме было выгодно строить небольшое предприятие. 15.3. В рамках задачи 15.2 подобрать вероятности низкого и среднего спроса, чтобы выгодно было строить крупное предприятие.