Главная > Математика > Введение в теорию игр
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

ГЛАВА XIII. ПРИМЕНЕНИЯ ТЕОРИИ ИГР К СТАТИСТИКЕ

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

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

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

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

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

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

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

Пример 13.1. Известно, что в урне находятся два шара, каждый из которых либо черный, либо белый. Статистик S должен определить, сколько там черных шаров. Если его предположение правильно, ему должно быть уплачено а; если его ответ отличается от правильного ответа на 1 (например, он указывает 1, когда в действительности 2 черных шара, или указывает 2, когда в действительности 1 шар, и т. д.), то ему должно быть уплачено ; если его ответ отличается от правильного ответа на 2 (указывает 0, когда в действительности 2 шара, или наоборот), ему должно быть уплачено .

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

У S имеется восемь возможных способов составить предположение о количестве черных шаров (то есть у него восемь чистых стратегий):

I. Не делать испытаний и предположить, что оба шара черные.

И. Не делать испытаний и предположить, что один шар черный и один белый.

III. Не делать испытаний и предположить, что оба шара белые.

IV. Проверить один шар и предположить, что другой шар такого же цвета, что и проверенный.

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

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

VII. Проверить один шар и предположить, что другой шар противоположного цвета.

VIII. Проверить оба шара и объявить правильное число черных шаров (которое, конечно, теперь известно).

Мы не перечислили способов, хотя и логически возможных, но нелепых, например, мы не рассматриваем возможность того, что S проверит один шар и затем, если даже проверенный шар — белый, предположит, что оба шара черные.

Далее, у природы имеются три возможности: нет ни одного черного шара, один шар черный и оба шара черные. Мы обозначаем эти стратегии номерами 0, 1 и 2.

Рассмотрим платеж статистику S при различных сочетаниях этих стратегий.

Если S применяет стратегию I, а природа применяет стратегию 0, то это значит, что S предполагает, что два шара черные, а в действительности нет ни одного черного шара.

Таким образом, S ошибается на два, и ему уплачивается . Аналогичные простые рассуждения позволяют нам учесть все случаи, когда S применяет стратегии I, II, III или VIII, и случаи, когда природа применяет стратегию 0 или стратегию 2.

Чтобы понять, как вычисляется платеж в других случаях, допустим, например, что S применяет стратегию V, а природа — стратегию 1. Тогда, если S делает одно испытание, вероятность того, что испытываемый шар будет черным (как и вероятность того, что он будет белым), равна . Если он черный, то, поскольку S применяет стратегию V, он предполагает, что оба шара черные, и, следовательно, ошибается на 1; итак, платеж в этом случае, с учетом стоимости проведения испытания, будет равен . Если же испытываемый шар оказывается белым, то S предполагает, что один шар белый, то есть указывает правильно, и, следовательно, он получит . Итак, математическое ожидание выигрыша для S равно

Продолжая рассуждать так же, мы получаем матрицу 1.

Матрица 1

Конечно, если бы S знал вероятность применения природой ее стратегий, то стоящая перед ним задача достижения максимума была бы проста — ему нужно было бы выбрать строку, которая для данных частот столбцов дала бы ему максимальное математическое ожидание выигрыша. Мы предполагаем, что S не знает, как будет себя вести природа, но и в этом случае он имеет возможность вычислить минимальную величину, которую он может надеяться получить при наиболее неблагоприятном возможном сочетании вероятностей, выбранных природой. Задача решается, если рассматривать матрицу 1 как платежную матрицу игры двух лиц с нулевой суммой. Если у S нет оснований ожидать, что природа поступит так, а не иначе, то он вполне может считать, что всего разумнее для него конечно, всего надежнее) выбрать стратегию так, как если бы он играл не против другого игрока, а против природы.

Цена игры для S и оптимальные стратегии игры зависят от относительных значений и .

Так, если мы возьмем , то мы получим матрицу 2.

Матрица 2

У этой матрицы нет седловой точки. Легко убедиться, что цена игры для S равна 98, оптимальная стратегия для S — вектор оптимальная стратегия для природы — .

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

Легко убедиться, что цена игры для S равна 0, оптимальная стратегия для S равна , а оптимальная стратегия для природы — . Итак, для статистика всего лучше всегда предполагать (не производя никаких испытаний), что один шар черный и один белый.

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

Матрица 3

Матрица 4

Легко убедиться, что цена игры для S равна 25, оптимальная стратегия для S — , а оптимальная стратегия для природы — (поскольку минимум каждой строки меньше 25, то у S нет чистой оптимальной стратегии). Итак, оптимальный способ игры для S следующий: он бросает правильную монету; если монета показывает герб, он предполагает (не делая испытаний), что один шар белый и один черный; если монета показывает решку, он проверяет один шар и предполагает, что оба шара того же цвета, что и проверенный.

Замечание 13.2. Другой способ решения подобных задач (который, однако, представляется мало обосно ванным) состоит в том, чтобы применить, так сказать «довод от незнания». Это значит, что, поскольку мы совершенно не знаем вероятностей распределения шаров, одинаково возможны следующие альтернативы: 1) оба шара черные, 2) первый шар черный, а второй белый, 3) первый белый, а второй черный, 4) оба шара белые. Поскольку случай, когда один шар черный, есть сочетание случая (2) и случая (3), эти альтернативы сводятся к предположению, что природа применяет смешанную стратегию Мы видим из матрицы 1, что если при этом предположении S применяет стратегию I, то математическое ожидание его выигрыша будет равно ; математические ожидания выигрыша при других имеющихся у него стратегиях будут:

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

Итак, S должен учитывать лишь стратегии II и VIII, то есть

Следовательно, если , то есть если , то S должен проверить оба шара; если , ему не следует проводить никаких испытаний, но просто предположить, что один шар черный и один шар белый. Этот способ для матриц 2 и 3 приводит к такому же ответу, как и теоретико-игровой подход, а в случае матрицы 4—к другому ответу. В последнем случае «довод от незнания» предписывает игроку S всегда применять стратегию II. В этом случае, если природа действительно применяет смешанную стратегию получит 50, то есть больше 25, которые он может себе гарантировать, применяя смешанную стратегию ; но следует заметить, что применяя исключительно стратегию II, S не может гарантировать себе даже 25, так как при этом, если природа будет применять стратегию , он может надеяться получить лишь 0. Итак, оказывается, что в этом случае «довод от незнания» не дает для S такой же надежной стратегии, как стратегия, основанная на теории игр.

Замечание 13.3. Хотя мы рассмотрели пример 13.1 как обычную игру двух лиц с нулевой суммой, нужно помнить, что природа на самом деле не является сознательным разумным существом. Когда игрок S применяет свою оптимальную стратегию для этой игры, он просто устанавливает нижнюю грань математического ожидания своего выигрыша; он может сознавать, что для него разумно поступать таким образом, но это не значит, что он считает природу недоброжелательным разумным существом. Его положение несколько походит на положение человека, который хочет поместить свои капиталы так, чтобы не оказаться банкротом ни от инфляции, ни от дефляции. Это не означает, что он непременно думает, что рынок будет всегда меняться наиболее неблагоприятным него образом;

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

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

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

и он не особенно стремится к тому, чтобы .

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

(где, конечно, означает теперь множество стратегий, которыми ограничена природа на основании сведений, имеющихся у ),

Обратимся теперь к примеру, поясняющему применение теории игр к контролю качества.

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

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

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

Теперь перед М встает вопрос о том, испытывать некоторые или все спицы, прежде чем принять колесо (то есть прежде чем передать его А).

У него имеются четыре возможные линии поведения (четыре стратегии):

I. Принять колесо без испытания.

II. Выбрать наудачу одну из спиц и испытать ее. Если спица удовлетворительна, принять колесо. Если она неудовлетворительна, забраковать.

III. Испытать выбранную наудачу спицу. Если она негодная, забраковать колесо. Если она удовлетворительна, выбрать наудачу одну из остальных спиц и испытать ее. Если эта спица негодная, забраковать колесо. Если она удовлетворительна, принять.

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

Далее, у природы имеются четыре возможности: может быть негодной ни одна, одна, две или три спицы. Мы обозначим эти стратегии природы номерами 0, 1, 2 и 3.

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

Если М применяет стратегию I, а природа — стратегию 0, то М не производит испытаний и нет ни одной неисправной спицы. Следовательно, А признает колесо удовлетворительным и заплатит предпринимателю . Выигрыш предпринимателя в этом случае равен .

Если М применяет стратегию II, а природа — стратегию 0, то М производит одно испытание и А признает колесо удовлетворительным. Тогда М получит от А сумму а, но ему нужно будет израсходовать на испытание . Следовательно, выигрыш предпринимателя равен .

Если М применяет стратегию III, а природа — стратегию 0, то выигрыш предпринимателя будет а если М применяет стратегию IV, а природа — стратегию О, то выигрыш предпринимателя будет .

Если М применяет стратегию I, а природа — стратегию 1, то передает колесо потребителю А, который признает его негодным.

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

Очевидно, когда М применяет стратегию I, а природа — стратегию 2 или 3, выигрыш предпринимателя также равен — .

Если природа применяет стратегию 3, то все спицы негодные. Тогда, если М производит любое испытание, он обнаружит при первом испытании, что колесо негодное и, следовательно, забракует его. Таким образом, платеж предпринимателю М равен лишь стоимости испытания одной спицы, а именно — . Это относится к тому случаю, когда природа применяет стратегию 3, а М применяет стратегию II, III или IV.

Если М применяет стратегию II, а природа — стратегию 1, то вероятность того, что М обнаружит негодную спицу, равна , а вероятность того, что он не обнаружит 2 ее, равна . Если он обнаружит негодную спицу, он получит — . Если М не обнаружит ее, он должен уплатить штраф , помимо расхода на испытание; итак, в этом случае платеж равен — . Следовательно, математическое ожидание выигрыша для М равно

Рассуждая аналогичным образом, мы видим, что если М применяет стратегию II, а природа — стратегию 2, то математическое ожидание выигрыша предпринимателя М равно

Если М применяет стратегию III, а природа — стратегию 1, то вероятность того, что М обнаружит негодную спицу при первом испытании, равна ; вероятность того, что он обнаружит ее при втором испытании, равна, 2.11 следовательно, вероятность того, что негодная спица пройдет необнаруженной, равна .

Если негодную спицу обнаруживают при первом испытании, выигрыш М равен — если ее обнаруживают при втором испытании, то выигрыш равен ; а если она остается необнаруженной, то выигрыш равен — . Следовательно, математическое ожидание выигрыша предпринимателя М равно

Продолжая рассуждать таким же образом, мы получаем матрицу 5.

Матрица 5

Цена игры для М и его оптимальные стратегии в этой игре зависят от соотношения величин и .

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

Элемент матрицы, отмеченный звездочкой, представляет седловую точку. Итак, самое худшее, что может оказаться для предпринимателя — это одна негодная спица колеса и лучше всего для М применять стратегию IV (то есть испытать все спицы колеса).

Матрица 6

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

Если же (так что производить испытание дорого), то мы получим матрицу 7.

Матрица 7

Здесь три элемента, отмеченные звездочками, суть седловые точки. Таким образом, худшее, что может сделать природа предпринимателю — это сделать негодными одну или большее число спиц (безразлично, сколько именно).

Для М всего лучше применять стратегию I (то есть совсем не производить испытаний). Итак, при увеличенной стоимости испытаний он уже может гарантировать лишь то, что его убыток будет не больше 300.

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

Матрица 8

Легко убедиться, что оптимальная стратегия для природы будет теперь , оптимальая стратегия для М — и цена игры равна — 650. Итак, самая неприятная для М стратегия природы следующая: вероятность того, что колесо хорошее, равна , а вероятность того, что у него неисправна одна спица, равна . Для М самое лучшее — бросить игральную кость и затем поступить следующим образом: если кость показывает 6, пропустить колесо без испытания; в остальных случаях испытывать все три спицы. Поскольку цена игры равна — 650, М вправе требовать первоначального платежа по меньшей мере в 650 единиц, помимо стоимости изготовления.

Библиографические замечания

О применении теории игр читатель может прочесть в следующих работах: Вальд [114], [115], [116], [117], Эрроу, Блэкуэлл и Гиршик [3] и Дворецкий, Вальд и Вольфович [36].

<< Предыдущий параграф Следующий параграф >>
Оглавление