Файл: Чесноков, Н. И. Оптимизация решений при разработке урановых месторождений.pdf

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

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

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

2 0 6

Пусть первый игрок имеет т стратегии, а второй — п:

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

к помощи теории игр). Однако выбор оптимальной про­ изводительности рудника без теории игр затруднен, так как не известны действительные запасы руды.

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

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

Пусть стратегия первого игрока і0, а второго /0. При этом выигрыш первого игрока равен ш0/0, а выигрыш второго составляет —вцңо- Если первый игрок выберет

207

стратегию /о, а второй отступит от стратегии /0, выигрыш первого игрока может только увеличиться. Второй игрок,

ему, что первый игрок получит выигрыш не больше о,0/„ • Стратегии игроков і0 и /о называются оптимальными чистыми стратегиями. Пара чисел (/0; /о), отвечающая оптимальным стратегиям игроков, называется седловой точкой платежной матрицы, а число а,о;о— ценой игры. Матрица выигрышей может иметь несколько седловых

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

Доказано, что шахматы (а в принципе все игры с полной информацией) имеют решение в чистых страте­ гиях. Однако далеко не все игры обладают таким свой­ ством.

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

2 0 8

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

Вектор U = (u\, ui, «з, • • Um), каждая компонента которого обозначает относительную частость (вероят­ ность), с которой соответствующая чистая стратегия используется в игре, называется смешанной стратегией

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

т

е, = (0, 0, . . . ГГ, 0, 0, ... , Ö),

І

п

е/ = (О? 0, 0, . . . ,1, 0, . . ., 0).

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

Всякое изменение информации приводит к повоіі игре, для которой оптимальная линия поведения будет иной.

Если первый игрок с вероятностью іц выбирает і-ю чистую стратегию, а второй с вероятностью wj — свою чистую /-іо стратегию, то средний выигрыш первого иг­ рока будет равен

M(U, W) называется платежной функцией. Естественное расширение понятия решения игры па

случаи смешанных стратегий приводит к следующему определению: игра имеет решение в смешанных страте­ гиях, если существуют такие стратегии U* и W* и чис­ ло V, что при любых смешанных стратегиях U и W вы­ полняются соотношения

Здесь число V — цена игры.

Для доказательства существования решения доста­ точно проверить выполнение неравенства (4.14) для всех

Понятие седловой точки, таким образом, распростра­ няется и на случай смешанных стратегий. Обычно гово­ рят, что игра имеет седловую точку (U*; W*), если пла-

210