Последовательные стратегические взаимодействия

Последовательные стратегические взаимодействия Примеры. • шахматы; • шашки; • большинство карточных игр; • ... Формализация. Пример. Суд над Иешуа Га-Ноцри. Понтий Пилат принимает решение о том, вынести ли Иешуа Га-Ноцри смертный приговор за слова, направленные против власти императора, или оправдать его. Если он оправдает опасного преступника, то его не поймут. С другой стороны, Иешуа Га-Ноцри во время допроса завоевал расположение прокуратора и даже вылечил Понтия Пилата от мучившей его головной боли, поэтому Понтию Пилату не хотелось бы, чтобы Га-Ноцри умер. Понтий Пилат знает, что если он вынесет смертный приговор, то будет еще один шанс: Синедрион имеет право отпустить одного преступника в честь праздника пасхи. Однако выбор, кого из преступников освободить, принадлежит первосвященнику Каифе. Его предпочтения очевидны: лучше отпустить убийцу, чем подстрекателя к смене веры. Понтий Пилат даже пробует угрожать Каифе, чтобы изменить решение первосвященника. Формализация. Пример. ри (−5, −3) вд а р оп ц Но Гаать осу ди ть ри оц П.П. ГаНо цр а-Н ьГ ит т с у и п от Каифа от пус ти ть (5, −5) ать ож угр е н Ва р -ра П.П. вв ан а угр ож ать (−3, 5) и цр ть ти пус Ка иф е от Каифа от пус ти ть Но Га- (5, −4) Ва р-р ав ва (−2, 4) на Игры в развернутой форме. Дерево игры отражает последовательность ходов игроков: • каждой вершине приписан игрок, которому в этом состоянии игры принадлежит ход; • ребра дерева обозначают возможные действия, которые есть у игрока в вершине, из которой эти ребра выходят; • вершины, из которых не выходит ни одного ребра, называются терминальными. В терминальной вершине игра заканчивается, и каждой терминальной вершине приписаны платежи, которые получают игроки. Игры в развернутой форме. Стратегии. Стратегией игрока в игре в развернутой форме называется набор действий игрока в каждой вершине, в которой ему принадлежит ход. Важно! Разным вершинам соответствуют разные состояния игры! Даже если доступные игроку действия в этих вершинах совпадают. В рассмотренном нами примере у Понтия Пилата есть ровно четыре стратегии: оправдать Га-Ноцри, не угрожать Каифе (Оправ Ну); оправдать Га-Ноцри, угрожать Каифе (Оправ У); осудить Га-Ноцри, не угрожать Каифе (Осуд Ну); осудить Га-Ноцри, угрожать Каифе (Осуд У). В рассмотренном нами примере у Каифы есть ровно четыре стратегии: отпустить Вар-раввана, отпустить Вар-раввана (В В); отпустить Вар-раввана, отпустить Га-Ноцри (В Г); отпустить Га-Ноцри, отпустить Вар-раввана (Г В); отпустить Га-Ноцри, отпустить Га-Ноцри (Г Г). Игры в развернутой форме. NE. Напомним, что равновесие Нэша — это такой профиль стратегий, в котором каждый игрок играет оптимальную стратегию при фиксированных стратегиях остальных игроков. Чтобы найти NE в игре в развернутой форме удобнее всего перейти к игре в нормальной форме и уже в ней искать NE. В рассмотренном примере два игрока, у каждого из игроков есть ровно 4 стратегии, поэтому для формализации игры в нормальной форме понадобится матрица 4 × 4. Игры в развернутой форме. NE. П.П. Оправ Ну Оправ У Осуд Ну Осуд У ВВ −5; −3 −5; −3 −3; 5 −2; 4 Каифа ВГ ГВ −5; −3 −5; −3 −5; −3 −5; −3 −3; 5 5; −5 5; −4 5; −5 ГГ −5; −3 −5; −3 5; −5 5; −5 Наилучшие ответы П.П. Оправ Ну Оправ У Осуд Ну Осуд У NE: (Осуд У ; В В). ВВ −5; −3∗ −5; −3∗ −3; 5∗ −2∗ ; 4∗ Каифа ВГ ГВ ∗ −5; −3 −5; −3∗ ∗ −5; −3 −5; −3∗ −3; 5∗ 5∗ ; −5 ∗ 5 ; −4 5∗ ; −5 ГГ −5; −3∗ −5; −3∗ 5∗ ; −5 5∗ ; −5 Игры в развернутой форме. Подыгры. Подыгра игры в развернутой форме — это поддерево дерева игры (выбираем некоторую вершину и рассматриваем игру с началом в этой вершине). ри вд а р оп ц Но Гаать (−5, −3) ри оц П.П. а-Н ьГ ит т с у осу ди ть ГаН оц р и п от Каифа от пус ти (5, −5) ать ож (−3, 5) ть Ва р-р угр не ав ва П.П. на угр ож ать и цр ть ти пус Ка иф е Но Га- (5, −4) от Каифа от пус ти ть Ва р -ра (−2, 4) вв ан а Равновесие Нэша, совершенное на подыграх (SPNE). Равновесием Нэша, совершенным на подыграх (обозначение SPNE) называется такой профиль стратегий, ограничение которого на каждую подыгру является равновесием Нэша. Другими словами, какую бы подыгру мы ни взяли, в SPNE каждый игрок на данной подыгре играет оптимально при фиксированных стратегиях остальных игроков. То есть SPNE — это пример того, что можно искать не все NE, а только те, которые удовлетворяют некоторому (некоторым) дополнительному (-ым) требованию (-ям). Игры в развернутой форме. Решение. Игры в развернутой форме удобно анализировать с конца. ри (−5, −3) вд а р оп ц Но Гаать осу ди ть ри оц П.П. ГаНо цр а-Н ьГ ит т с у и п от Каифа от пус ти ть (5, −5) ать ож угр е н Ва р -ра П.П. вв ан а угр ож ать (−3, 5) и цр ть ти пус Ка иф е от Каифа от пус ти ть Но Га- (5, −4) Ва р-р ав ва (−2, 4) на Алгоритм Цермело-Куна Алгоритм Цермело-Куна — решение игры в развернутой форме с конца (начиная с вершины, в которой ход принадлежит «последнему» игроку и заканчивая начальной вершиной дерева игры). Полученный в итоге профиль стратегий (или профили стратегий) являются SPNE. Теорема Цермело. В любой игре в развернутой форме с конечным числом действий в любой вершине и конечной длиной любого пути от начальной вершины к терминальной существует равновесие Нэша, совершенное на подыграх. Несколько различных SPNE может быть только в игре, в которой по крайней мере в двух терминальных вершинах платежи по крайней мере одного из игроков повторяются. Теорема Цермело. Шашки. Теорема Цермело. В любой игре в развернутой форме с конечным числом действий в любой вершине и конечной длиной любого пути от начальной вершины к терминальной существует равновесие Нэша, совершенное на подыграх. Шашки на доске 8 × 8 удовлетворяют условиям теоремы. Хотя при игре в шашки существует около 5 · 1020 возможных позиций, однако десятки компьютеров, работавшие почти непрерывно с 1989 года, довели алгоритм Цермело-Куна в шашках до конца, и теперь известно, что при правильной игре обеих сторон в шашках будет зафиксирована ничья (см. статью Jonathan Schaeffer, Neil Burch, Yngvi Bjornsson, Akihiro Kishimoto, Martin Muller, Robert Lake, Paul Lu and Steve Sutphen. Checkers is Solved. Science. 2007. Vol. 317, no. 5844. Pp. 1518–1522). Теория игр Сысоева Любовь Николаевна, Сахарова Нина Евгеньевна НИУ ВШЭ Москва, 2021 Формализация игры в развернутой форме. • Перечислить всех игроков; • Перечислить все стратегии (самое сложное); • Нарисовать дерево игры, в котором отметить платежи игроков в терминальных вершинах. Дерево игры отражает последовательность ходов игроков: • каждой вершине приписан игрок, которому в этом состоянии игры принадлежит ход; • ребра дерева обозначают возможные действия, которые есть у игрока в вершине, из которой эти ребра выходят; • вершины, из которых не выходит ни одного ребра, называются терминальными. В терминальной вершине игра заканчивается, и каждой терминальной вершине приписаны платежи, которые получают игроки. Игры в развернутой форме. Стратегии. Стратегией игрока в игре в развернутой форме называется набор действий игрока в каждой вершине, в которой ему принадлежит ход. Важно! Разным вершинам соответствуют разные состояния игры! Даже если доступные игроку действия в этих вершинах совпадают. Игры в развернутой форме. NE. Напомним, что равновесие Нэша — это такой профиль стратегий, в котором каждый игрок играет оптимальную стратегию при фиксированных стратегиях остальных игроков. Чтобы найти NE в игре в развернутой форме удобнее всего перейти к игре в нормальной форме и уже в ней искать NE. Игры в развернутой форме. Подыгры. Подыгра игры в развернутой форме — это поддерево дерева игры (выбираем некоторую вершину и рассматриваем игру с началом в этой вершине). Равновесие Нэша, совершенное на подыграх (SPNE). Равновесием Нэша, совершенным на подыграх (обозначение SPNE) называется такой профиль стратегий, ограничение которого на каждую подыгру является равновесием Нэша. Другими словами, какую бы подыгру мы ни взяли, в SPNE каждый игрок на данной подыгре играет оптимально при фиксированных стратегиях остальных игроков. То есть SPNE — это пример того, что можно искать не все NE, а только те, которые удовлетворяют некоторому (некоторым) дополнительному (-ым) требованию (-ям). Игры в развернутой форме. Решение. Игры в развернутой форме удобно анализировать с конца. Алгоритм Цермело-Куна Алгоритм Цермело-Куна — решение игры в развернутой форме с конца (начиная с вершины, в которой ход принадлежит «последнему» игроку и заканчивая начальной вершиной дерева игры). Полученный в итоге профиль стратегий (или профили стратегий) являются SPNE. Теорема Цермело. В любой игре в развернутой форме с конечным числом действий в любой вершине и конечной длиной любого пути от начальной вершины к терминальной существует равновесие Нэша, совершенное на подыграх. Несколько различных SPNE может быть только в игре, в которой по крайней мере в двух терминальных вершинах платежи по крайней мере одного из игроков повторяются. Теорема Цермело. Шашки. Теорема Цермело. В любой игре в развернутой форме с конечным числом действий в любой вершине и конечной длиной любого пути от начальной вершины к терминальной существует равновесие Нэша, совершенное на подыграх. Шашки на доске 8 × 8 удовлетворяют условиям теоремы. Хотя при игре в шашки существует около 5 · 1020 возможных позиций, однако десятки компьютеров, работавшие почти непрерывно с 1989 года, довели алгоритм Цермело-Куна в шашках до конца, и теперь известно, что при правильной игре обеих сторон в шашках будет зафиксирована ничья (см. статью Jonathan Schaeffer, Neil Burch, Yngvi Bjornsson, Akihiro Kishimoto, Martin Muller, Robert Lake, Paul Lu and Steve Sutphen. Checkers is Solved. Science. 2007. Vol. 317, no. 5844. Pp. 1518–1522). Последовательные стратегические взаимодействия с несовершенной информацией Игры, в которых по крайней мере один игрок по крайней мере в одном состоянии игры не знает достоверно, в какой из нескольких вершин дерева игры он находится, называются играми в развернутой форме с несовершенной информацией. Множество вершин M дерева игры называется информационным множеством игрока i, если игрок i не может отличить друг от друга ни одну из вершин множества M, но может отличить вершины множества M от любой другой вершины, не входящей в множество M. Если любое информационное множество игрока состоит из одной вершины, то такие игры назваются играми с совершенной информацией. До этого мы рассматривали именно игры в развернутой форме с совершенной информацией. Стратегии В играх с несовершенной информацией игрок выбирает свое действие в каждом информационном множестве, в котором ему принадлежит ход (а не в каждой вершине!). Стратегией игрока в игре в развернутой форме с несовершенной информацией называется набор его действий в каждом информационном множестве, в котором ему принадлежит ход. Важно! В одном информационном множестве действия, доступные игроку, одинаковы! Формализация одновременного взаимодействия. Пример. Битва полов. т (4, 5) ле ба Жена т ле фу тб ба ол (0, 0) Муж ут б т (1, 1) ле ф ба ол Жена фу тб ол (5, 4) Пример. В июне 1815 года Наполеон, одержав победу над прусской армией, послал маршала Груши с 35 тысячами догнать и окончательно разгромить пруссаков, сам же с остальными 73 тысячами двинулся навстречу англичанам. Практически сразу после начала сражения при Ватерлоо стало понятно, что сил Наполеона недостаточно. Наполеон решает, посылать Груши записку с приказом вернуться или нет, однако письмо бы опоздало к началу сражения Груши при Вавре, из которого тот не смог бы выйти, чтобы прийти на помощь Наполеону. Груши мог бы и сам, без записки, решить вступать в сражение при Вавре или возвращаться к Наполеону. В случае написания записки Наполеон мог ждать прибытия Груши или же отступать. Если Наполеон проигрывает битву, то война заканчивается полным поражением, что плохо и Наполеону и Груши. Если Груши дает бой при Вавре, то одерживает победу над прусской армией, что позитивно для Наполеона и Груши, если Наполеон не проигрывает битву. Если силы Наполеона и Груши объединяются, то у них появляются большие шансы победить англичан. Формализация. Пример. у верн бой ть са пи при Вавр (−5, −5) е (0, 0) Груши не ться Наполеон пи ь я тьс ну за вер пи ск у бо жда Наполеон са т ь упит отст йп р иВ ав ть Г руши ь упит отст (−5, −5) (5, 5) (0, 0) ре жда ть Г руши (−10, −10) Игры в развернутой форме. Стратегии. Стратегией игрока в игре в развернутой форме с несовершенной информацией называется набор его действий в каждом информационном множестве, в котором ему принадлежит ход. В рассмотренном нами примере у Наполеона есть ровно четыре стратегии: не писать, отступить (Нет Отст); не писать, ждать (Нет Ждать); написать записку Груши, отступить (Записка Отст); написать записку Груши, ждать (Записка Ждать). В рассмотренном нами примере у Груши есть ровно две стратегии: вернуться к Наполеону (вернуться); дать бой при Вавре (бой); Формализация. Пример. у верн бой ть са пи при Вавр (−5, −5) е (0, 0) Груши не ться Наполеон пи ь я тьс ну за вер пи ск у бо жда Наполеон са т ь упит отст йп р иВ ав ть Г руши ь упит отст (−5, −5) (5, 5) (0, 0) ре жда ть Г руши (−10, −10) Игры в развернутой форме. NE. Груши вернуться бой Нет записки Отступать Наполеон Нет записки Ждать Записка Отступать Записка Ждать Наилучшие ответы Груши вернуться бой Нет записки Отступать −5; −5 0∗ ; 0∗ Наполеон Нет записки Ждать −5; −5 0∗ ; 0∗ Записка Отступать −5; −5 0∗ ; 0∗ ∗ ∗ Записка Ждать 5 ;5 −10; −10 NE: (Нет записки Отступать ; бой), (Нет записки Ждать ; бой), (Записка Отступать ; бой), (Записка Ждать ; вернуться). Игры в развернутой форме. Подыгры. Подыгра игры в развернутой форме с несовершенной иформацией — это поддерево дерева игры, такое, что любое информационное множество, или полностью лежит в нем, или с ним не пересекается. ться (−5, −5) у верн бой ть са пи Наполеон Вавр е (0, 0) ат ь я тьс ну за п ис ь упит отст вер Наполеон пи с при Груши не ку бо йп р иВ ав жда ть Г руши ь упит отст (−5, −5) (5, 5) (0, 0) ре жда ть Г руши (−10, −10) Равновесие Нэша, совершенное на подыграх (SPNE). Равновесием Нэша, совершенным на подыграх (обозначение SPNE) называется такой профиль стратегий, ограничение которого на каждую подыгру является равновесием Нэша. Другими словами, какую бы подыгру мы ни взяли, в SPNE каждый игрок на данной подыгре играет оптимально при фиксированных стратегиях остальных игроков. То есть SPNE — это пример того, что можно искать не все NE, а только те, которые удовлетворяют некоторому (некоторым) дополнительному (-ым) требованию (-ям). Немного теории вероятностей Вероятность события A (обозначение P(A)) — количество исходов, благоприятствующих событию, деленное на общее число возможных исходов. Пример. Вероятность выпадения 3 на игральной кости равна 16 . Вероятность события A при условии события B (обозначение P(A|B)) — количество исходов, благоприятствующих обоим событиям A и B, деленное на число исходов, благоприятствующих событию B. Пример. Вероятность выпадения 3 на игральной кости при условии, что выпало нечетное число, равна 31 . Пример. Вероятность выпадения 3 на игральной кости при условии, что выпало четное число, равна 03 = 0. Немного теории вероятностей Пусть нам предлагается поучаствовать в лотерее правила которой таковы: • стоимость билета равна 100 рублей • каждый 20 билет — выигрышный • половина выигрышных билетов приносит 200 рублей, а половина — 1000 рублей Стоит ли участвовать в такой лотерее? Посчитаем матожидание выигрыша: E= 1 1 38 · (200 − 100) + · (1000 − 100) + · (−100) = 40 40 40 = −2800 −280 100 900 −3800 + + = = = −70. 40 40 40 40 4 То есть если купить много лотерейных билетов, то каждый из них принесет купившему (в среднем) убыток в 70 рублей. В некоторых играх для расчета платежа игрока приходится считать «ожидаемый платеж». Это происходит, если платеж игрока зависит от некоторых вероятностных факторов. Например, при игре в покер игрок, когда принимает решение поднимать ли ставку, не знает наверняка, какие карты у соперника. Далее мы рассмотрим один из видов неполной информации в игре — Байесовы игры. Байесовы игры Идея: у некоторых (или всех) игроков есть типы и остальные игроки не знают наверняка, какого типа другие акторы, но, зная свой собственный тип, могут оценить вероятность того, что другой игрок принадлежит какому-то конкретному типу. Чтобы задать Байесову игру нужно указать: • Множество игроков • Множество типов каждого из игроков • “Веры” игроков в вероятность типов других игроков при условии информации о своем типе • Действия каждого из игроков в каждом типе • Платежи каждого из игроков в каждом профиле стратегий в зависимости от типов игроков Байесовы игры. «Битва полов» Пример. Рассмотрим игру «Битва полов», но добавим, что у жены может быть два настроения — хорошее или плохое. Если у жены хорошее настроение, то игра выглядит привычным образом. Если же у нее плохое настроение, то ее платежи увеличиваются на 4, если она пошла куда-либо одна (а не вместе с мужем). Будем считать, что у мужа всегда хорошее настроение, его платежи не зависят от платежей жены и он оценивает вероятность хорошего настроения жены в 50%. Байесовы игры. «Битва полов» Формализуем Байесову игру: • { Муж, Жена } — Множество игроков • TМуж = {+} ; TЖена = {+, −} — Множество типов каждого из игроков • PМуж (Жена + |Муж+) = 21 ; PМуж (Жена − |Муж+) = 12 ; PЖена (Муж + |Жена+) = 1 ; PЖена (Муж + |Жена−) = 1 “Веры” игроков в вероятность типов других игроков при условии информации о своем типе • SМуж = {Ф, Б} ; SЖена+ = {Ф, Б} ; SЖена- = {Ф, Б} — Действия каждого из игроков в каждом типе • Платежи каждого из игроков в каждом профиле стратегий в зависимости от типов игроков (см. матрицы ниже) Важно отметить разницу между действием игрока и его стратегией! Действия игрока — набор вариантов поведения игрока (могут отличаться для разных типов игрока). Стратегия игрока — набор действий игрока в каждом из типов игрока. В рассматриваемом примере действия Жены — пойти на футбол или пойти на балет (2 действия). В рассматриваемом примере стратегии Жены — (пойти на футбол в хорошем настроении и пойти на футбол в плохом настроении) или (пойти на футбол в хорошем настроении и пойти на балет в плохом настроении) или (пойти на балет в хорошем настроении и пойти на футбол в плохом настроении) или (пойти на балет в хорошем настроении и пойти на балет в плохом настроении) (4 стратегии). Сколько стратегий в данной игре у каждого игрока? Сколько профилей стратегий в данной игре? Байесовы игры. «Битва полов» Хорошее настроение Жены Плохое настроение Жены Жена Жена Ф Б Ф Б Ф 5; 4 1; 1 Ф 5; 0 1; 5 Муж Муж Б 0; 0 4; 5 Б 0; 4 4; 1 Так игра выглядит с точки зрения жены, поскольку она понимает, какое у нее сегодня настроение, и, соответственно, знает свой платеж. Муж должен оценивать различные возможные действия жены в каждом из ее типов (настроений). Поэтому с точки зрения мужа игра выглядит следующим образом. Муж Ф Б Ф(+) Ф(−) 0.5 · 5 + 0.5 · 5; _ 0.5 · 0 + 0.5 · 0; _ Жена Ф(+) Б(−) Б(+) Ф(−) 0.5 · 5 + 0.5 · 1; _ 0.5 · 1 + 0.5 · 5; _ 0.5 · 0 + 0.5 · 4; _ 0.5 · 4 + 0.5 · 0; _ Б(+) Б(−) 0.5 · 1 + 0.5 · 1; _ 0.5 · 4 + 0.5 · 4; _ Байесовы игры. «Битва полов» С точки зрения Жены: Хорошее настроение Жены Жена Ф Б Ф 5; 4 1; 1 Муж Б 0; 0 4; 5 Плохое настроение Жены Жена Ф Б Ф 5; 0 1; 5 Муж Б 0; 4 4; 1 С точки зрения Мужа: Муж Ф Б Ф(+) Ф(−) 5; _ 0; _ Жена Ф(+) Б(−) Б(+) Ф(−) 3; _ 3; _ 2; _ 2; _ Б(+) Б(−) 1; _ 4; _ Байесовы игры. «Битва полов» Раньше обсуждали. Равновесие Нэша (обозначение NE) — профиль стратегий, состоящий из наилучших ответов игроков на стратегии друг друга. Равновесие Байеса-Нэша (обозначение BNE) — профиль стратегий, состоящий из наилучших ответов игроков на стратегии друг друга (для любого типа любого игрока). Напомним, что стратегия в Байесовой игре — это набор действий игрока в каждом из типов игрока. Байесовы игры. «Битва полов». Наилучшие ответы. С точки зрения Жены: Хорошее настроение Жены Жена Ф Б Ф 5; 4∗ 1; 1 Муж Б 0; 0 4; 5∗ Плохое настроение Жены Жена Ф Б Ф 5; 0 1; 5∗ Муж Б 0; 4∗ 4; 1 С точки зрения Мужа: Муж Ф Б Ф(+) Ф(−) 5∗ ; _ 0; _ Жена Ф(+) Б(−) Б(+) Ф(−) 3∗ ; _ 3∗ ; _ 2; _ 2; _ Б(+) Б(−) 1; _ 4∗ ; _ Байесовы игры. «Битва полов». Наилучшие ответы. С точки зрения Жены: Хорошее настроение Жены Жена Ф Б Ф 5; 4∗ 1; 1 Муж Б 0; 0 4; 5∗ Плохое настроение Жены Жена Ф Б Ф 5; 0 1; 5∗ Муж Б 0; 4∗ 4; 1 С точки зрения Мужа: Муж Ф Б Ф(+) Ф(−) 5∗ ; _ 0; _ BNE: (Ф, Ф+ Б− ). Жена Ф(+) Б(−) Б(+) Ф(−) 3∗ ; _ 3∗ ; _ 2; _ 2; _ Б(+) Б(−) 1; _ 4∗ ; _ Байесовы игры. Пример. «Лыжня» В деревне живет 11 лыжников, некоторые из которых имеют добродушный нрав, а некоторые — злобный. Всем жителям известно, что добродушных лыжников в деревне 8 человек, а остальные лыжники злобные. 1 января ближе к вечеру один из лыжников решил прокатиться по единственной в округе лыжне. При подъезде к очередному глубокому оврагу он заметил на противоположной стороне другого лыжника, однако из-за расстояния не смог его узнать. Каждый спортсмен независимо от другого решает, съезжать ли ему в овраг или пропустить другого лыжника. Байесовы игры. «Лыжня» Если оба решат съехать, то произойдет столкновение и каждый получит платеж −4. Добродушный лыжник получает моральное удовлетворение от пропуска другого лыжника в размере 1, если другой воспользовался преимуществом, и ничего не получает, если другой преимуществом не воспользовался. Если же пропустили его и он этим воспользовался, то он испытывает угрызения совести в размере −1. Злобный лыжник испытывает неудовольствие от пропуска другого лыжника в размере −1, если другой воспользовался преимуществом, и ничего не получает, если другой преимуществом не воспользовался. Если же пропустили его и он этим воспользовался, то он испытывает удовольствие в размере 1. Формализуйте данное взаимодействие в виде Байесовой игры. Найдите все BNE. Формализуем Байесову игру: • { Лыжник №1, Лыжник №2 } — Множество игроков • TЛыжник №1 = {д, з} ; TЛыжник №2 = {д, з} — Множество типов каждого из игроков 7 • PЛыжник №1 (Лыжник №2 д|Лыжник №1 д) = 10 ; 3 PЛыжник №1 (Лыжник №2 з|Лыжник №1 д) = 10 ; 8 ; PЛыжник №1 (Лыжник №2 д|Лыжник №1 з) = 10 2 PЛыжник №1 (Лыжник №2 з|Лыжник №1 з) = 10 — “Веры” игроков в вероятность типов других игроков при условии информации о своем типе • SЛыжник №1 = {Пропустить, Не пропускать} ; SЛыжник №2 = {Пропустить, Не пропускать} — Действия каждого из игроков (в разных типах доступные действия игрока одинаковы) • Платежи каждого из игроков в каждом профиле стратегий в зависимости от типов игроков (см. матрицы ниже) Сколько стратегий в данной игре у каждого игрока? Сколько профилей стратегий в данной игре? Байесовы игры. «Лыжня» Лыжник №1 добрый. Лыжник №1 Пропустить Не пропускать Лыжник №2 Пропустить Не пропускать 0; _ 1; _ −1; _ −4; _ Лыжник №1 злобный. Лыжник №1 Пропустить Не пропускать Лыжник №2 Пропустить Не пропускать 0; _ −1; _ 1; _ −4; _ Ситуация симметрична (от смены лыжников местами ничего не изменится). Вывод: доброму лыжнику всегда выгоднее пропускать другого. Байесовы игры. «Лыжня» Как выглядит игра с точки зрения Лыжника №1. Лыжник №1 добрый Пр Не пр Прд Прз 0.7 · 0 + 0.3 · 0; _ 0.7 · (−1) + 0.3 · (−1); _ Лыжник №2 Прд Не прз Не прд Прз 0.7 · 0 + 0.3 · 1; _ 0.7 · 1 + 0.3 · 0; _ 0.7 · (−1) + 0.3 · (−4); _ 0.7 · (−4) + 0.3 · (−1); _ Не прд Не прз 0.7 0.7 · 1 + 0.3 · 1; _ · (−4) + 0.3 · (−4); _ Лыжник №1 злобный Пр Не пр 0.8 0.8 Прд Прз · 0 + 0.2 · 0; _ · 1 + 0.2 · 1; _ 0.8 0.8 Прд Не прз · 0 + 0.2 · (−1); _ · 1 + 0.2 · (−4); _ Лыжник №2 Не прд Прз 0.8 · (−1) + 0.2 · 0; _ 0.8 · (−4) + 0.2 · 1; _ 0.8 0.8 Не прд Не прз · (−1) + 0.2 · (−1); _ · (−4) + 0.2 · (−4); _ Байесовы игры. «Лыжня». Лучшие ответы. Как выглядит игра с точки зрения Лыжника №1. Лыжник №1 добрый Пр Не пр Прд Прз 0; _ −1; _ Лыжник №2 Прд Не прз Не прд Прз 0.3; _ 0.7; _ −1.9; _ −3.1; _ Не прд Не прз 1; _ −4; _ Лыжник №2 Прд Не прз Не прд Прз −0.2; _ −0.8; _ 0; _ −3; _ Не прд Не прз −1; _ −4; _ Лыжник №1 злобный Пр Не пр Прд Прз 0; _ 1; _ BNE: (Пропуститьд Не пропускатьз ; Пропуститьд Не пропускатьз ). Пример печальный. • В последние несколько лет поступление в высшие учебные заведения проходило в две волны: 80 % бюджетных мест заполнялось в первую; те абитуриенты, кто не попал в вуз мечты, еще успевали подать документы в другой, не первого выбора, с меньшим конкурсом. Такая процедура позволяла абитуриентам рассчитать свой потенциал, а вузам — заполнить бюджетные места. • Осенью 2020 года Министерство образования и науки утвердило новый порядок приема: вторую волну поступления отменили, однако у вузов осталось право объявлять дополнительный набор, если бюджетные места остались незаполненными по окончании приема. Это, однако, было не единственным изменением. • Если прежде абитуриенты могли подавать заявления в пять вузов на три направления в каждом, то в 2021 году число направлений увеличилось до 10– то есть каждый абитуриент мог участвовать не в 15 конкурсах, как раньше, а в 50. • Ранжированные списки абитуриентов обезличили: вместо фамилий там появились номера СНИЛС или индивидуальные номера, присвоенные вузами. В министерстве это объяснили защитой личных данных: раньше абитуриенты могли находить друг друга в соцсетях – и на это были жалобы. • Наконец, в этом году, как и в прошлом, для зачисления нужно было предоставить не оригинал аттестата, как в докарантинный период, а согласие на зачисление. По правилам, его можно подать только в одно место (иначе – отчисление). • В этом году волна была одна — все должны были онлайн подать согласие до 18:00 11 августа. При этом списка «точно поступивших» не было. Вузы предлагали абитуриентам самим оценивать свои шансы на проходные баллы прошлого года, но в этом году и баллы ЕГЭ другие, и конкурс другой. (источник https://www.fontanka.ru/2021/08/12/70075583/) • Если абитуриент видел, что согласий уже слишком много и он не проходит, можно было «переложить» свое согласие в другой вуз. Главное было — успеть до 18:00. При этом значительная часть абитуриентов сидела и караулила максимально близко к 18 часам, поэтому в последний момент можно было не успеть переложить согласие, а опередить тебя мог кто-то с высоким баллом, если ты не угадал. • Осложнялось все тем, что из-за такой нагрузки «падали» сайты вузов, и не только переложить, но и просто положить свое согласие хоть куда-то было проблематично.(источник https://www.fontanka.ru/2021/08/12/70075583/) • Такая процедура приёма привела к недовольству и абитуриентов и их родителей, и сотрудников приёмных комиссий вузов, а также к несправедливому перераспределению: в этот раз у абитуриентов не было права на ошибку, и многие выбрали вуз ниже уровнем, чем тот, на который они могли рассчитывать. Что делать? Выиграли абитуриенты с более слабыми баллами, не побоявшиеся подать согласия в более хороший вуз; абитуриенты с высокими баллами, решившие перестраховаться и подать в средний вуз, упустили возможность обучаться в более хорошем вузе. С точки зрения вузов, многие получили более сильных абитуриентов в верхушке списка, а внизу баллы абитуриентов оказались ниже, в топовых вузах сильно снизился проходной балл на многих направлениях. Подробнее: https://novayagazeta.ru/articles/2021/09/20/kursamna-smekh Алгоритм Гейла и Шепли. • Задача о стабильных браках — математическая задача из теории игр, в которой нужно найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. • В простой формулировке: нужно составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам (пары были стабильными). • Решение задачи было описано в 1962 году математиками Дэвидом Гэйлом и Ллойдом Шепли. Их алгоритм получил название алгоритма Гэйла — Шепли или «алгоритма отложенного согласия». Применение алгоритма. • Множество практических механизмов на основе алгоритма Гэйла — Шепли разработал нобелевский лауреат Элвин Рот. • Решение задачи о стабильных браках было отмечено Нобелевской премией по экономике 2012 года (Элвин Рот (Alvin Roth) и Ллойд Шепли (Lloyd Shapley)). Применение алгоритма. • Практический механизм на основе алгоритма Гэйла — Шепли был внедрен в деятельность больниц по набору врачей и интернов (национальная программа NRMP, разработанная Элвином Ротом), в правила многих американских профессиональных спортивных ассоциаций по набору спортсменов в команды. В соответствии с предложенными институциональными механизмами фирмы набирают на стажировку сотрудников, суды нанимают секретарей, родители находят подходящие школы для детей. Алгоритм. • Рассмотрим модель «свадебного рынка», которую часто называют также моделью мэтчингов. Пусть у нас есть два множества игроков: множество мужчин M = {m1 , m2 , . . . , mk } и множество женщин W = {w1 , w2 , . . . , wl }, где k, l > 1. • Задача состоит в том, чтобы разбить мужчин и женщин на пары, причем так, чтобы это разбиение не противоречило интересам игроков. • Будем считать, что у каждого мужчины есть предпочтения на множестве всех женщин, в соответствии с которыми можно сравнить любых двух женщин из множества W и выбрать из них ту, которая лучше для этого мужчины. Кроме того, любой мужчина имеет гарантированную возможность остаться одиноким, и он может сравнить эту альтернативу с каждой из возможных женитьб. • Симметрично с перестановкой полов зададим предпочтения каждой женщины. Алгоритм. • Предпочтения игрока X будем обозначать через P(X ) и записывать в виде последовательности возможных альтернатив, расположенных в порядке убывания привлекательности, обозначая при этом альтернативу «остаться в одиночку» через X , а альтернативу «быть вместе с Y » через Y . • Пример P (m1 ) w3  w2  w1  m1 P (m2 ) w1  w3  w2  m2 P (m3 ) w3  m3  w2  w1 P (w1 ) m2  m3  m1  w1 P (w2 ) m1  m3  m2  w2 P (w3 ) m1  m2  m3  w3 Рациональные предпочтения. • На более формальном языке можно сказать, что для любого мужчины m заданы его предпочтения на множестве W ∪ {m}, причем эти предпочтения являются полными (можно сравнить две любые альтернативы) и транзитивными (если a не хуже b и b не хуже c, то a не хуже c). Предпочтения, являющиеся полными и транзитивными, называются рациональными. • В примере для любого мужчины m заданы рациональные предпочтения на множестве W ∪ {m}, а для любой женщины w заданы рациональные предпочтения на множестве M ∪ {w }. • Мы будем изучать только рациональные предпочтения, поскольку предпочтения, не являющиеся рациональными, анализировать достаточно сложно, а поведение игроков с нерациональными предпочтениями может не обладать какими-либо закономерностями. Мэтчинг. • Будем называть мэтчингом µ произвольное разбиение мужчин и женщин на пары, при котором каждый мужчина либо оказывается в паре с одной из женщин, либо остается один, а каждая женщина либо оказывается в паре с одним из мужчин, либо остается одна. • Пару игрока x будем обозначать через µ(x). Формально мэтчинг µ - это взаимо-однозначное отображение из множества M ∪ W в множество M ∪ W , такое, что для любого x ∈ M выполняется соотношение µ(x) ∈ W ∪ {m}, а для любого y ∈ W выполняется соотношение µ(y ) ∈ M ∪ {w }. Найди недовольных. • Пример P (m1 ) w3  w2  w1  m1 P (m2 ) w1  w3  w2  m2 P (m3 ) w3  m3  w2  w1 P (w1 ) m2  m3  m1  w1 P (w2 ) m1  m3  m2  w2 P (w3 ) m1  m2  m3  w3 • Рассмотрим три мэтчинга. В каких найдутся недовольные игроки? m1 m2 m3 µ1 : w3 w1 w2 µ2 : µ3 : m1 m2 m3 w2 w1 w3 m1 m2 m3 . w3 w1 · w2 Стабильный мэтчинг. • Будем говорить, что мэтчинг удовлетворяет условию индивидуальной рациональности, если ни одному из игроков не выгодно бросить свою вторую половинку и остаться одному. Мэтчинг µ1 не удовлетворяет условию индивидуальной рациональности. • Будем говорить, что мэтчинг удовлетворяет условию парной рациональности, если не найдется таких одного мужчины и одной женщины, которые захотят объединиться друг с другом, и им обоим от этого станет лучше, чем в мэтчинге. Мэтчинг µ2 не удовлетворяет условию парной рациональности. • Мэтчинги, удовлетворяющие условиям индивидуальной и парной рациональности, называются стабильными. Легко проверить, что мэтчинг µ3 стабильный. • Стабильныйх мэтчингов может быть несколько. Бывает и так. • Даже в стабильных мэтчингах может получиться так, что не каждый мужчина получает самую привлекательную для него женщину, и наоборот. Это получается не потому, что кому-то навязали нежелательного партнера, а в силу непривлекательности человека для возможных партеров. Алгоритм DAA. • Утверждение: для любых предпочтений существует по крайней мере один стабильный мэтчинг. • Алгоритм отсроченного принятия предложения (Deferred Acceptance Algorithm, или DAA) для любых предпочтений позволяет построить некоторый стабильный мэтчинг. В этом алгоритме мужчины делают предложения женщинам, передвигаясь, по мере получения отказов, от наиболее предпочтительных для себя пар к менее предпочтительным, а женщины из всех имеющихся предложений выбирают самое лучшее. Шаги алгоритма DAA 1. Каждый мужчина, которого сейчас не удерживает женщина, делает предложение наилучшей из тех женщин, которые ему пока не отказывали. 2. Каждая женщина из списка полученных предложений выбирает самого лучшего мужчину, а всем остальным отказывает. Если самый лучший мужчина хуже, чем остаться одной, то она ему также отказывает. Если самый лучший из мужчин, сделавших ей предложение, лучше, чем одиночество, она удерживает его. 3. Если есть хотя бы один мужчина, который получил отказ, то возвращаемся к шагу 1. Если таких мужчин нет, то алгоритм останавливается. 4. Очевидно, что остановка однажды произойдет, поскольку мужчины могут сделать лишь конечное число предложений. 5. DAA всегда приводит к стабильному мэтчингу! Пример. P (m1 ) w3  w2  w1  m1 P (m2 ) w2  w3  w1  m2 P (m3 ) w3  w2  w1  m3 P (w1 ) m2  m3  m1  w1 P (w2 ) m3  m2  m1  w2 P (w3 ) m2  m3  m1  w3 • Как по предпочтенияи игроков определить, на какие пары может претендовать тот или иной игрок? Будем называть женщину w достижимой для мужчины m, если существует стабильный мэчинг µ, такой, что µ(m) = w . • Если w не является достижимой для m, то это может быть следствием разных причин: либо мужчина m совершенно не устраивает женщину w , либо мужчина m в принципе устраивает женщину w , но у w есть еще лучшие женихи, которые являются достижимыми, либо женщина w совершенно не устраивает мужчину m, либо женщина w в принципе устраивает мужчину m, но у него есть еще лучшие невесты, которые являются достижимыми. • Оказывается, что в мэтчинге, полученном с помощью алгоритма DAA, каждый мужчина получает наилучшую из достижимых для него альтернатив! • Если мужчина m получает в результате DAA женщину w , а b находится в списке его предпочтений выше w , женщина w то не существует никакого стабильного мэтчинга, в котором b. m стоит в паре c w Нет в мире совершенства. • Мы рассмотрели алгоритм DAA, в котором предложения делают мужчины. Чтобы это подчеркнуть, этот алгоритм также называют M-proposing DAA. • Очевидно, что можно поменять роли женщин и мужчин местами и рассмотреть W-proposing DAA - алгоритм DAA, в котором предложение делают женщины. Мэтчинг, который полуится в результате применения W-proposing DAA, будет стабильным, причем каждая женщина будет получать наилучшего из достижимых для нее мужчин. Нет в мире совершенства. • Справедливо следующее: если есть два стабильных мэтчинга µ1 и µ2 , причем для всех мужчин мэтчинг µ1 не хуже мэтчинга µ2 , то для всех женщин мэтчинг µ1 не лучше мэтчинга µ2 . • Итак, M-proposing DAA позволяет получить стабильный мэтчинг, который является наилучшим для мужчин и наихудшим для женщин, а W-proposing DAA приводит к стабильному мэтчингу, который является наилучшим для женщин и наихудшим для мужчин. Причем тут теория игр? • Обратимся снова к предпочтениям из примера выше P (m1 ) w3  w2  w1  m1 P (m2 ) w2  w3  w1  m2 P (m3 ) w3  w2  w1  m3 Здесь существуют ровно P (w1 ) m2  m3  m1  w1 P (w2 ) m3  m2  m1  w2 P (w3 ) m2  m3  m1  w3 два стабильных мэтчинга: µ1 : m1 m2 m3 w1 w2 w3 µ2 : m1 m2 m3 w1 w3 w2 Легко убедиться, что M-proposing DAA приводит к мэтчингу µ1 , а W-proposing DAA - к мэтчингу µ2 . Причем тут теория игр? • У женщины w2 есть основания быть недовольной исходом M-proposing DAA - она получает мужчину m2 , а хотела бы получить достижимого для нее мужчину m3 . Может ли женщина w2 схитрить и ввести в компьютер не свои настоящие предпочтения, а другие, чтобы компьютер выдал оптимальный для w2 результат? Еще пример. • Рассмотрим стандартный свадебный рынок, на котором присутствуют 3 мужчины и 3 женщины. Их предпочтения P (m1 ) w3 , w2 , w1 , m1 P (m2 ) w1 , w3 , w2 , m2 P (m3 ) w3 , m3 , w2 , w1 выглядят следующим образом: P (w1 ) m2 , m3 , m1 , w1 P (w2 ) m1 , m3 , m2 , w2 P (w3 ) m1 , m2 , m3 , w3 • Найдите мэтчинг µ1 , который получится в результате использования M-proposing DAA; • найдите мэтчинг µ2 , который получится в результате использования W-proposing DAA; • найдите все стабильные мэтчинги и докажите, что других стабильных мэтчингов нет.