Игры наилучшего выбора с несколькими участниками

• Автор: Фалько, Анна Антоновна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Петрозаводск
• Количество страниц: 108 с. : ил.

Оглавление
Введение

1 Игра 7П лиц наилучшего выбора с ранговым критерием

1.1 Схема с арбитражной процедурой

1.2 Схема с голосованием

1.2.1 Задача с тремя игроками и голосованием

1.2.2 Задача голосования для т игроков

1.3 Общий случай арбитражной процедуры для трех игроков

1.4 Результаты

2 Максимизация ожидаемого выигрыша в игре т лиц наилучшего выбора с полной информацией

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

предложения
2.1.1 Модель без перераспределения вероятностей
2.1.2 Модель с перераспределением вероятностей
2.2 Теоретико-игровая задача выбора двух объектов с полной информацией
2.2.1 Игра двух лиц с доминирующим игроком
2.2.2 Игра 771 лиц с возможностью отказа от предложения
2.3 Результаты

3 Модели наилучшего взаимного выбора
3.1 Решение задачи наилучшего взаимного выбора
3.2 Задача наилучшего взаимного выбора с пополнением популяции
3.3 Трехмерная задача наилучшего выбора
3.4 Результаты
4 Максимизация вероятности наилучшего выбора двух объектов
4.1 Задача с отсутствием информации
4.2 Задача с полной информацией
4.3 Игра двух лиц с доминирующим игроком
4.4 Результаты
Заключение
Литература

Введение
Актуальность темы. Задачи наилучшего выбора составляют важный класс задач, изучаемых теорией игр и теорией оптимальной остановки. Они отражают существенные особенности реальных процессов выбора, имеют простую содержательную постановку и легко интерпретируемые решения, что делает их применимыми в таких науках, как экономика, социология и психология.
Постановка классической задачи наилучшего выбора выглядит следующим образом [1, 29].
Дано N упорядоченных по качеству объектов, из которых требуется выбрать всего один. Ознакомление с объектами происходит в случайном порядке. На каждом шаге очередной объект можно сравнить со всеми предыдущими. Основываясь на данных о ранее просмотренных объектах, необходимо принять решение: остановиться на текущем объекте или отвергнуть его и продолжить процесс выбора, потеряв возможность возвращения к этому объекту в дальнейшем. Требуется найти стратегию, максимизирующую вероятность найти наилучший объект.
Классическая задача наилучшего выбора имеет различные названия: „задача о разборчивой невесте“, „задача о секретаре“и т.д. Также задача наилуч-шего выбора известна под названием „задача Googol“— выбор наибольшего из неизвестного набора чисел. Макквин и Миллер в 1960 году предложили вариант задачи наилучшего выбора под названием „задача о парковке“(„задача о

"лг ( N
ДГ-1
_Т_ V У
т-к1х (р-1)'
±1 Г)ГП
рт- 1(р+ !)
ЛГ-1-

Приравняем ее к нулю, и при к = ат + г и а > | получим уравнение
—+Д§Т(Ч0
(1—а)т
'гг
/ XI
О ~ 1)”

(ГУ - 1)а
(р+1)с(1)
1а — Т 1е

. 2 т

(ЛГ-1)в
= 0.
[|]“т (дг - 1 - [|])(1-а)т [£]г (ТУ - 1 - [Я])-£ . 2- 3 (ТУ - 1 )тс(ДГ - 1)
При а = ~ с(£) — 2 ["И, при а > | с(/) = 1.
Следовательно, для больших т левая часть равенства стремится к 0 при нечетном N только при одном значении а = а при четном N — при трех значе-
ниях а — Д а%

2(ТУ-1)
-11!
1п(ЛГ-1)-1п(ЛГ-2) лг
"1м Л' 1пХ.У-2) * причем, для N > 4 минимум
достигается в точке
1.3 Общий случай арбитражной процедуры для трех игроков
Для т — 3 рассмотрим более общий случай, в котором, если игроки приняли различные решения, например, два игрока согласны принять (отвергают) претендента, а один его отвергает (принимает), то конфликтная ситуация разрешается с помощью арбитражной процедуры: претендент принимается (отвергается) с вероятностью р и отвергается (принимается) с вероятностью р — 1 —р. Обозначим Хг, У-, Д относительные ранги Ого претендента для игроков 1, 2 и 3 соответственно. Тогда последовательность относительных рангов имеет следующее распределение вероятностей: Р{Хг = х, Д = у, Д = г} = для х = 1