Случайные величины как найти медиану. Медиана и мода непрерывной случайной величины. В21. Способы отбора

Рассмотрим конечную бескоалиционную игру с двумя участниками. Игрок А имеет m стратегий, игрок В – n стратегий. Выбор игроком А стратегии с номером I , а игроком В стратегии с номером j – определяет исход игры. Ни один из игроков не знает выбора противника. Игрок А получает в качестве выигрыша сумму а ij , а игрок В – сумму b ij . Такая игра называется игрой двух лиц в нормальной форме .

Игра двух лиц с матрицами выигрыша а ij и b ij называется антагонистической (или игрой с нулевой суммой), если а ij + b ij = 0 при любой стратегии I игрока А и любой стратегии j игрока В. Антагонистическая игра описывается одной матрицей (платежной или выигрышей).

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

В теоретико-множественной форме антагонистическая матричная игра записывается в виде

Н = { A, B, H(m,n)}, (1)

где A = {a 1 ,a 2 ,…a m } - множество стратегий игрока А;

В = {b 1 ,b 2 ,…b n } - множество стратегий игрока B;

H(m,n) – платежная матрица или матрица выигрышей, размерностью m х n.

Любой элемент матрицы Н – (a ij) – численно показывает величину выигрыша игрока А, если он примет стратегию i, и соответственно, величину проигрыша игрока В, если он примет стратегию j.

Решить игру (1) означает вычислить пару стратегий (a i ,b j) , которая наилучшим образом удовлетворяла бы интересы обоих игроков.

Наиболее простым случаем матричной антагонистической игры является. вполне определенная игра(ига с седловой точкой).

Вполне определенной игрой или иг­рой с седловой точкой называется игра, у которой совпадают нижняя и верхняя цены игры, то есть выполняется равенство:

a = max min а ij = min max a ij = b .

i j j i

При этом величина V = a = b называется ценой игры , элемент а ij соответствующий равенству, называют седловой точкой.

Простота решения игры с седловой точкой заключается в том, что оптимальные стратегии (в этом случае их называют чистыми стратегиями ) обоих игроков получаются сразу. Для примера 1 α = β = 6 , т.е цена игры V = 6 у.е., а элемент матрицы Н, находящийся на пересечении строки 2 (стратегия А 2) и столбца 2 (стратегия В 2) – седловая точка игры.

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

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

Седловых точек к матрице может быть несколько. Между тем значение цены игры всегда единственное.

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

Решением игры в примере 1 является выбор стратегии А 2 игроком А и В 2 игроком В, при этом цена игры V = 6.

Каждый игрок должен стремиться не вообще к ситуации, в которой значение функции выигрыша максимально или минимально, а прежде всего к такой ситуации, которая может сложиться в процессе игры. Чтобы ситуация могла быть осуществимой, в ней одновременно должны достигаться приемлемые результаты как для игрока I, так и для игрока II. Ситуации, обладающие этим свойством, называются ситуациями равновесия . Именно они могут складываться в результате разумного выбора игроками своих стратегий. При выявлении ситуации равновесия необходимо прежде всего проанализировать последовательно каждую стратегию игрока I с точки зрения наиболее неблагоприятного для него исхода при выборе игроком II одной из своих стратегий. Для этого в - строке матрицы отыскивается минимальное значение выигрыша. Обозначим его , где знаком ( минимум по ) обозначена операция отыскания минимального из значений функции выигрыша при всех возможных .

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

Величина называется нижним значением игры или максимином , а соответствующая ей стратегия игрока I – максиминной стратегией .

максиминной стратегии игрок I обеспечивает себе (независимо от поведения противника) гарантированный выигрыш не менее .

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

,

где знаком ( максимум по ) обозначено максимальное значение функции выигрыша при всех возможных .

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

Величина называется верхним значением игры или минимаксом , а соответствующая ей стратегия игрока II – минимаксной стратегией .

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

Следовательно, если оба игрока ведут себя разумно, то выигрыш игрока I должен быть не меньше, чем максимин , и не больше, чем минимакс , то есть:

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

Следовательно, для игрока I лучше всего выбирать стратегию , а для игрока II - . Согласно этому стратегии и называются оптимальными, а гарантированный выигрыш игрока I – значением игры , которое обозначают через .

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

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

Рассмотрим матрицу игры.

Так, матрица имеет седловую точку , так как цифра 7 является минимумом второй строки и максимумом первого столбца. Следовательно, оптимальной стратегией игрока I является максиминная , а игрока II – минимаксная . Значение игры .

Выбрав свою оптимальную стратегию, игрок I может быть уверен, что он получит по меньшей мере 7, а игрок II, выбрав свою оптимальную стратегию, не допустит, чтобы игрок I получил больше 7. Эти стратегии и составляют решение игры с седловой точкой.

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

Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица . Отсюда, кстати, происходит еще одно их название - матричные игры . Каждый элемент платежной матрицы а ij содержит числовое значение выигрыша игрока I (проигрыша игрока II), если первый применяет стратегию i , а второй - стратегию j . Термины выигрыш ипроигрыш следует понимать в широком смысле, т. к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи прежде всего заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.

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

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

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

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

Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица А =║a ij ║ m xn . При выборе игроком I стратегии i его гарантированный доход независимо от действий игрока II составит min a i,j . Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т. е. обеспечивал получение max (min a i,j ). Такой принцип выбора стратегии получил название «принцип максимина ». С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит max a i,j , и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить min (max a i,j ). в этом суть принципа минимакса.

Можно доказать справедливость следующего соотношения:

Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии

В этом случае говорят, что игра имеет седловую точку . Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии i* и j *, образующие седловую точку, называются оптимальными , а значение v = a i*j* называют ценой игры . Тройка (i* , j* , v ) считается решением матричной игры с седловой точкой.

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

В данной матрице минимальные (гарантированные) выигрыши первого игрока по строкам равны 1, 5 и (-3). Следовательно, его максиминному выбору будет отвечать стратегия 2, гарантирующая выигрыш 5. Для второго игрока максимальные проигрыши по столбцам матрицы составят 8, 10, 5, 17, поэтому имеет смысл остановиться на стратегии 3, при которой он проиграет только 5. Таким образом, вторая стратегия первого игрока и третья стратегия второго образуют седловую точку со значением 5, т. е. для игры с матрицей (6.5) имеет решение (2; 3; 5).