Оптимальности Нэша не хватает

luherstag

Допустим есть такая игра. Первый игрок выбирает строку. Второй - столбец. Выигрыш первого игрока - первый элемент соответствующей пары, второго - второй. Выборы осуществляются независимо. Никакого другого взаимодействия между игроками нет.
(2,2) (0,0)
(0,0) (1,1)
Вопрос. Если каждый игрок стремится к максимизации своего выигрыша в худшем случае и является разумным (в т.ч. знает о разумности другого какие стратегии могут быть выбраны?
Критерий оптимальности по Парето (upd не по Парто, а по Нэшу) даёт два варианта: (1,1) и (2,2).
Здравый смысл подсказывает, что только (первая строка, первый столбец).
Существует ли способ записать на формальном языке (например, с помощью кванторов по индексам и неравенств) это очевидное ощущение?

gr_nik

Можно сказать, что Парето-оптимальная точка - та, что не существует такой, что никакому из участников не станет хуже, а кому-то станет лучше. Тогда, очевидно, точка (2,2) лучше точки (1,1).
Вроде, точка (1,1) - это равновесие по Нэшу, а не Парето-оптимальная.

luherstag

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

gr_nik

Если тебя ответ на вопрос интересует, то решение - это смешанная стратегия - с вероятностью 1/3 выбирать первый вариант, и с вероятностью 2/3 выбирать 1 вариант, тогда ты в любом случае получаешь доход 2/3 (при любой смешанной стратегии другого игрока и это максимум по всем стратегиям другого игрока.

luherstag

Здесь не используется предположение о разумности второго игрока. Его цель - не завалить первого, а максимизировать свой выигрыш (можно считать, что моральное удовлетворение от опускания первого и тому подобные факторы уже включены в функцию выигрыша).
Если бы тебе предложили сыграть в такую игру - ты бы выбрал (1/3,2/3) ?!

shpanenoc

Ты определись сначала, чего ты хочешь? Какую задачу решаешь?
Существует ли способ записать на формальном языке (например, с помощью кванторов по индексам и неравенств) это очевидное ощущение?
Способ, естественно, существует. Как мне кажется, (2,2) - это и есть единственное оптимальное по Парето решение игры. Но достижение Парето-оптимума подразумевает предварительную договоренность между игроками (опять же ИМХО).

shpanenoc

А, я понял, что тебя смущает.
Если бы я, к примеру, играл в такую игру и МНЕ СКАЗАЛИ БЫ: "Второй игрок тоже стремится к максимальному выигрышу и притом обладает мозгом", то я бы выбирал всегда 1-й вариант. Если же я о втором игроке не знаю ничего вообще (вот как раз случай "полной некооперации" то буду выбирать (1/3, 2/3). На самом деле, может, против меня котенок играет?

gr_nik

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

То есть надо максимизировать прибыль даже в случае, если противник - совсем идиот и играет наобум.
На этой картинке нарисованы возможные твои выплаты, если ты играешь стратегией q, то есть выбираешь второй ответ с вероятностью q, а первый - с вероятностью 1-q. Тогда красным отмечено то, что ты получаешь в случае, если противник играет первую стратегию, синим - если вторую. Соответсвенно, жёлтым нарисованы всевозможные выигрыши при различных его смешанных стратегиях. Синим я обозначил минимум выплат при твоей стратегии q и взевозможных стратегиях противника. Видно, что максимум этого минимума достигается в q=2/3.

Твоя задача следующая:
$$\max_{s_1 \in S_1}\min_{s_2 \in S_2}\pi_1(s_1,s_2)$$
где S_1 - множество стратегий первого игрока, S_2 - множество стратегий второго игрока, ну а \pi_1(s_1,s_2) - выплата первого в случае, если игроки играют стратегии s_1 и s_2, соответственно.
Просто Парето-оптимальность, и даже равновесие Нэша тут не причём, это максимин, надо только внимательно условие задачи прочитать. "Худший случай" - это как раз синяя линия на моём рисунке.
Хотя получившиеся стратегии действительно являются равновесием Нэша, но это не всегда так.

Suebaby

надо только внимательно условие задачи прочитать. "Худший случай" - это как раз
к сожалению, в условии упоминается и разумность противника. Имхо условие глючное

luherstag

Я об этом в условии и написал. Считай, что тебе СКАЗАЛИ. А кооперации всё равно никакой нет.

luherstag

По-моему условие абсолютно нормальное. Ну да, в худшем случае, НО ПРИ УСЛОВИИ, что противник разумен (т.е. например если бы у него было два одинаково разумных варианта, надо было бы ожидать худшего для себя).

shpanenoc

Тут рассуждения кажутся логичными, т.к. Парето-оптимальная точка одна. Но допущение "противник разумен" не является формальным. Разумный противник не только ищет себе оптимум, он еще и знает, что и его противник разумен, и делает выводы из этого. И т.п.
Короче, либо мы задаем четкий АЛГОРИТМ действий противника (тогда это уже не игра, если мы его знаем либо мы допускаем его ПРОИЗВОЛЬНОЕ поведение, с некоторыми ограничениями. Например, такими: если в столбце X все мои выигрышы попарно меньше, чем мои выигрыше в столбце Y, то я столбец X не выберу.

gr_nik

Ты вместо того, чтобы минусы ставить, лучше бы подумал немного.
Кооперации никакой нет, если бы кооперация была, то как раз ты и получил бы свою Парето-оптимальную точку.
Если ты знаешь, что твой противник играет стратегию (1/3, 2/3 то лучший твой ответ - это любая смешанная стратегия, и это согласуется с рациональностью агента, поскольку его прибыль в этом случае максимальна.
Если ты знаешь, что твой противник будет максимизировать свою полезность в случае, когда он не знает, как ты действуешь, то есть предполагая, что ты будешь отвечать случайно, то он выберет именно (1/3, 2/3 а лучший твой ответ, как рационального агента на это - это тоже (1/3, 2/3).
Если ты этого не понимаешь, то твои проблемы. Можешь считать, что ответ на твою задачу - это единственное в этой задаче Парето-оптимальное равновесие Нэша (1-ая стратегия, 1-ая стратегия дающая выигрыш (2,2 то так и считай, не надо тогда с остальными спорить, по крайней мере.
Если тебе что-то другое надо, то поясни понятнее, что тебе надо, иначе дискуссия ни о чём будет.

luherstag

> либо мы задаем четкий АЛГОРИТМ действий противника (тогда это уже не игра, если мы его знаем)
Было бы очень хорошо его задать (кстати, заодно мы получим алгоритм и для себя). А называть это игрой или нет - какая разница... Главное что станет ясно, как себя вести в таких ситуациях.
Да, и вообще-то в случае антагонистических игр так же можно было бы сказать, что противник не произволен, а предельно разумен. И ответ там получился бы такой же (минимакс или минимакс по смешанным стратегиям потому что повезло - действовать против разумного противника надо так же, как против произвольного.
> допущение "противник разумен" не является формальным. Разумный противник не только ищет себе оптимум, он еще и знает, что и егопротивник разумен, и делает выводы из этого. И т.п.
Оно не является формальным, но не факт, что его нельзя формализовать. Можно например представить этот алгоритм как машину с оракулом (отвечающим за "разумность" оппонента после чего попытаться somehow
задать неподвижную точку такой конструкции. Правда, у меня это не получается, точнее, в моих попытках неподвижных точек оказывается две и я не понимаю, как отбросить лишнюю ("если предположить, что противник выберет вторую строчку, то надо выбирать второй столбец. С другой стороны, противник рассуждает примерно так же. Всё сходится...")
>либо мы допускаем его ПРОИЗВОЛЬНОЕ поведение, с некоторыми ограничениями
Да, только скорее произвольное поведение с НЕКОТОРЫМИ ОГРАНИЧЕНИЯМИ. Если бы удалось задать эти ограничения таким образом, чтобы всё, что им удовлетворяет, не противоречило здравому смыслу...
------
Да, на самом деле ещё стоит запретить пользоваться симметричностью (например, задать матрицу
(2,3) (0,0)
(0,0) (1,1)
потому что иначе катит такое псевдо-рассуждение: "Т.к. я разумен, и противник разумен, он выберет то же самое что и я (если конечно будет не пофиг, что выбирать - а тогда и мне пофиг). Поэтому выбор стоит между (1,1) и (2,2). Понятно что надо делать."

luherstag

А я и не ставил минусов.
> Если ты знаешь, что твой противник играет стратегию (1/3, 2/3 толучший твой ответ - это любая смешанная стратегия, и это согласуется срациональностью агента, поскольку его прибыль в этом случае максимальна.
>Еслиты знаешь, что твой противник будет максимизировать свою полезность вслучае, когда он не знает, как ты действуешь, то есть предполагая, чтоты будешь отвечать случайно, то он выберет именно (1/3, 2/3 а лучшийтвой ответ, как рационального агента на это - это тоже (1/3, 2/3).
Всё это так, но не имеет отношения к задаче. По условию я знаю, что противник разумен и обладает полной информацией (не знает только собственно моего хода и соответственно знает, что я разумен.
> твои проблемы
Мне не нравится твой тон. Если бы все нормальные люди играли в такую игру, это твои проблемы были бы, что ты выигрывал бы в среднем 2/3 там, где остальные 2 (если конечно их не угораздит наткнуться на тебя).
[кстати, такая гипотетическая ситуация отдалённо напоминает iterated prisoners dilemma, про которую я вчитал у Докинза, но подозреваю к делу не относится]
> поясни понятнее, что тебе надо
Вроде я это уже сделал. Конечно, неформально — но в этом по сути и состоит вопрос: как формализовать?

gr_nik

Всё это так, но не имеет отношения к задаче. По условию я знаю, что противник разумен и обладает полной информацией (не знает только собственно моего хода и соответственно знает, что я разумен.
Противник разумен, но предполагается, что он не знает, как ты действуешь или знает, что ты максимизируешь прибыль в "худшем" случае, то есть, (1/3, 2/3). В этом случае он рационален, ведь предполагается, что он не знает, что против него играет рациональный агент. Точно так же и ты, не будучи уверенным, что противник рационален, отвечаешь ему (1/3, 2/3).
Если вы оба знаете, что вы оба не будете играть нерационально, то, конечно, выберете оба первую стратегию.
Если бы все нормальные люди играли в такую игру, это твои проблемы были бы, что ты выигрывал бы в среднем 2/3 там, где остальные 2 (если конечно их не угораздит наткнуться на тебя).
В том-то и дело, что тут предполагается, что про противника ничего не известно. Можно считать, что там робот сидит и рандомом произвольную стратегию выдаёт. В этом случае, если мы будем играть 1-ую стратегию, то, если он будет, например, выдавать с вероятностью 1 2-ую стратегию, то мы будем получать. А в таком случае против любого робота мы в среднем не получим менее 2/3.
Конечно, неформально — но в этом по сути и состоит вопрос: как формализовать?
Есть несколько возможностей формализовать эту задачу:
1) То, как я уже писал, то есть максимин, то есть все знают матрицы игры, но не уверены, какую стратегию выберет соперник, тем не менее, рациональны.
2) Парето-оптимум, то есть каждый игроу максимизирует свою полезность при условии, что все остальные максимизируют свою полезность (тоже в предположении, что все их соперники максимизируют полезность). В этом случае получится одна из Парето-оптимальных точек, если мы выберем последовательность, в которой игроки будут максимизировать свою полезность. Если есть общая Парето-оптимальная точка (как в нашей игре то такая задача будет иметь решение (в нашем случае оба выбирают первую стратегию). Однако при такой постановке задача может и не иметь решения (например, в случае антагонистических игр, т.к. там если одному лучше, то другому хуже).
3) Какое-то из равновесий Нэша. Это можно формализовать так, что каждый думает, что остальные будут играть определённые стратегии, и при данном наборе стратегий других игроков максимизирует свою полезность. Если для каждого игрока его стратегия является одним из наилучших ответов на набор стратегий других игроков, то это будет равновесием Нэша.
4) Если считать, что игроки могут заранее договориться, как играть, тогда получится одна из Парето-оптимальных точек, в зависимости от переговорной силы игроков. В нашем случае, не зависимо от их переговорной силы, они выберут оба первую стратегию, поскольку это единственная Парето-оптимальная точка.
Я всё-таки настойчиво утверждаю, что то, что спрашивается в задаче - это первый вариант.
Тем не менее, если ты считаешь, что это не так, то, возможно, тебе больше понравится второй вариант.
Третий вариант действительно немного скользкий, т.к. на самом деле механизм осуществления равновесия Нэша немного неясен в произвольном случае, зато по теореме Нэша известно, что такое равновесие есть для любой игры.
Ну и в четвёртом подразумевается возможность договориться, что в нашем случае не верно.
Поясню, что имеется в виду во втором варианте: в нашем случае игроков можно упорядочить двумя способами - (1,2) и (2,1). Если вначале максимизирует полезность первый участник, то он выберет стратегию так, что если остальные, наблюдая его выбор, будут максимизировать свою прибыль, то его прибыль будет наибольшей. Тогда он выберет первую стратегию, а второму игроку не остаётся ничего, как выбрать наилучший ответ на эту стратегию, то есть тоже первую стратегию. Если вначале будет выбирать второй, а потом первый, то мы получим такой же ответ. Поскольку ответы совпадают, нам повезло, и есть точка, которая устраивает всех, то есть где оба выбирают первую стратегию с вероятностью 1, и получают выигрыш 2.
Кстати, точки, которые получаются в результате описанной мной процедуры, называются точками Вебера.
Однако я всё же думаю, что тебе нужны не они, поскольку спрашивается про "худший" случай. Если бы нужно было это решение, я думаю, что слово "худший" можно было бы опустить.
Ну так как, такая формализация подойдёт?
P.S. Прошу прощения, если тон в предыдущем посте был не подобающим.

luherstag

Для начала уточняю условие задачи. Имеется такая игра с определённой матрицей. Перед началом партии первый игрок делает public announcement: "Я знаю матрицу игры. Я разумен. Я стремлюсь к максимизации выигрыша в худшем случае". Потом то же самое делает второй игрок. После этого всякий обмен информацией и взаимодействие (кроме самой игры) прекращаются. В результате этого у них устанавливается цепочка знаний, что оппонент разумен и знает, что его оппонент разумен, и знает, что его оппонент разумен и т.д.
"Разумен" означает примет одно из оптимальных (исходя из всей имеющейся информации) решений.
"Максимизация выигрыша в худшем случае" означает, что если у противника будет несколько оптимальных решений, надо закладываться на худшее (но только среди оптимальных). Я это условие ввёл, надеясь избежать смешанных стратегий (в случае антагонистических игр это помогает - смешанные возникают только при стремлении к максимизации матожидания выигрыша). Оно не слишком принципиально, и может на практике лучше рассматривать максимизацию именно матожидания, но в любом случае что-то тут надо специфицировать. Похоже, эти слова и породили основное непонимание.
Задача. Надо формализовать то что написано, причём достаточно полным образом. Я понимаю, что в некоторых случаях решения игры в "моём" смысле может и не быть, но в то же время чувствую, что в каких-то оно всё же есть. Формализация в идеале должна приводить к решению во всех таких ситуациях (к слову, к ним относятся и антагонистические игры, будучи частным случаем неантагонистических и имея оптимальные (минимаксные) стратегии).
Теперь о предложенных вариантах. Из них "почти" подходящим мне кажется только второй.
1) на самом деле есть уверенность, что противник выберет одну из оптимальных стратегий, сомнения могут быть только в том, какую
3) точек равновесия Нэша в данном случае две, а оптимальное "по мне" решение одно. И вдобавок действительно непонятен механизм осуществления равновесия Нэша.
4) Договориться не могут, т.к. нет никаких взаимодействий. Если бы быларазрешена только коммуникация, то тоже не получилось бы. Т.е. могли бы пообсуждать то сё, но в конечном счёте каждый всё равно поступит по-своему. А новой информации в результате обсуждения возникнуть не может, т.к. и так каждый знает ситуацию и то, как мыслит другой. Тут правда возникает другой вопрос, никак не связанный с этой задачей. Что нужно вводить мистическую "переговорную силу", я понимаю (например,
(0,0) (2,1)
(1,2) (0,0. И мне очень интересно, существует ли какое-либо внятное её описание. Я знаю только одно, для случая бесконечной переговорной силы - это ситуация шантажа (игра Г_2 из книжки Васина Морозова, стр. 115).
2)недостаток в том, что этот вариант имеет характер рецепта ("предполагай, что противник ходит первым и думает, что ты увидишь его ход, и на основе этого выбирай свою стратегию"). Нет обоснования, что это приведёт к оптимальному результату, т.к. модель противника не соответствует условию задачи. Я прикинул, вроде это даже работает для антагонистических игр, но полной уверенности нет. Если бы была такая "теорема", что если все точки Вебера совпадают, то это именно то решение, которое кажется мне правильным, а если не получается, то никакое решение не кажется мне правильным - было бы просто прекрасно. Но чтобы эту теорему сформулировать, нужна именно та формализация, которой мне не хватает, так что похоже мне остаётся только тыкать разные матрицы и смотреть, правдоподобно ли выходит.
Кстати, есть ли теорема, что все точки Вебера совпадают для матричной игры в смешанных стратегиях?

gr_nik

Нет, такой теоремы нет, потому что это не всегда так, обычно точек Вебера много, их выпуклая оболочка образует ядро игры.
Можешь ещё почитать про вектор Шепли (это среднее всех точек Вебера) например, тут, во многих случаях решение по вектору Шепли является "самым справедливым", однако это не совсем наш случай (там речь идёт про кооперативные игры).
Просто для каждой игры в таком понимании вообще не понятно, что от нас требуется. Например, в приведённом тобой примере "битвы полов":
(0,0) (2,1)
(1,2) (0,0)
Что здесь предполагается, что мы хотим выбрать? Если понимать с точки зрения максиминов, то понятно, как надо действовать. А если они каждый будут стараться учесть интересы друг друга, то тогда не совсем понятно. Во втором варианте именно в том и есть проблема, что если разные последовательности дают разные ответы, то, видимо, задача в такой постановке не имеет решения, потому что тогда не понятен алгоритм, по которому выбирается решение из нескольких равноправных.
Можно, конечно, сказать, что если Парето-оптимальная точка одна, то мы выбираем её, а если нет, то точку из первого варианта, однако совсем не понятно, почему другой рациональный агент будет делать именно так.
В общем случае будет решение по второму методу только если есть точка, в которой выплаты всех игроков максимальны (то есть Парето-оптимальная точка единственна). Однако если это не так, то тогда вообще не понятно, как себя ведёт рациональный агент (скорее всего, максимизирует математическое ожидание выигрыша в "худшем" случае, то есть при любых ответах других игроков).

shpanenoc

Кстати, вот такой тебе вопрос. Если у меня есть автомобиль, то нужно ли мне его страховать? (забьем на ОСАГО, пусть его нет).
В случае аварии автомобиль ломается, мой убыток составляет -10.
Если я заплачу 1 за страховку, то мне возмещают стоимость авто в случае аварии, т.е. мой убыток всегда -1, была авария или нет.
Если хотя бы один из участников движения оказывается на дороге пьяным, то все автомобили попадают в аварию и ломаются.
Получается следующая игра многих лиц. Я нарисую для 2 лиц, т.к. дальше надо N-мерную таблицу рисовать, а я не умею. Но смысл не меняется.
Возможные стратегии:
1) не страхуюсь, езжу пьяным
2) не страхуюсь, не езжу пьяным
3) страхуюсь, езжу пьяным
4) страхуюсь, не езжу пьяным.
Игра:
 
(-10,-10) (-10,-10) (-10,-1) (-10,-1)
(-10,-10) (0, 0) (-10, -1) (0, -1)
(-1,-10) (-1,-10) (-1,-1) (-1,-1)
(-1,-10) (-1,0) (-1,-1) (-1,-1)

Единственный Парето-оптимум - точка (2,2 где все не страхуются, но и не пьянствуют. Однако ЛИЧНО Я бы в таком случае застраховался :) Вот тебе и некооперация.

gr_nik

Ну да, хочется застраховаться, но только потому, что ты боишься, что остальные агенты нерациональны.
На самом деле, можно предположить, что они с маленькой вероятностью оказываются нерациональны (то есть будут пьяными гонять и если эта вероятность совсем маленькая, то всё равно можно не страховаться. Но если эта возможность становится вероятной, то всё зависит от твоего отношения к риску. Если у тебя отвращение к риску, то ты уже при маленьких вероятностях нерациональности страховаться будешь. Если тебе всё равно, то, начиная где-то с 0.1 (хотя надо точно считать если ты склонен к риску, то ты и при больших вероятностях предпочтёшь не страховаться (будешь надеяться, что пронесёт).
Однако если каждый агент рационален и уверен, что остальные агенты рациональны, то надо всё-таки выбирать (2,2). А если никто про рациональность других не знает (не уверен то страховаться начнут.

luherstag

Согласен, ответил бы примерно так же.

luherstag

> Однако если это не так, то тогда вообще не понятно, как себя ведётрациональный агент (скорее всего, максимизирует математическое ожиданиевыигрыша в "худшем" случае, то есть при любых ответах других игроков).
А почему бы ему не просчитать на один ход хотя бы, т.е. предположить, что остальные агенты рациональны именно в этом смысле, и выбирать вариант исходя из этого? Проблема в том, что он не знает, будут ли они просчитывать на один ход, или на десять, а результаты могут быть разными. Но тогда может можно так попробовать:
Определение. Игрок рационален, если он 0-рационален, или 1-рационален, и т.д.
0-рацонален это как ты описал.
1-рационален это если предполагает, что другие 0-рациональны.
2-рационален, если предполагает, что другие 0-рациональны или 1-рациональны...
Конечно, может так получится, что вся эта иерархия схлопнется к предположению, что оппонент может повести себя как угодно. А может быть и нет (например, будут отсечены заведомо тупые ходы, на которые так пришлось бы закладываться)...
Ещё насколько я понял, ты пишешь что задача не может быть решена существующими методами, потому что формулировка не даёт их применить (недостаточно строгая, или просто не соответствует...) Да, наверное так оно и есть: пост я писал потому что столкнулся с тем, что задача не может быть решена _известными_мне_ методами, и надеялся, что может есть ещё какие-то, которые прольют на это свет.
Такое возможно, вот пример из антагонистических игр. Если рассматривать минимаксную стратегию, то не у всех игр будет решение. И если начать думать об этом в рамках чистых стратегий, то только укрепишься в выводе, что всё плохо. Но это означает лишь, что модель недостаточно полная, нужны новые идеи. И здесь смешанные стратегии противоречие снимают, потому что в них решение всегда существует.
Похоже может быть с "битвой плов". Кажется, что решения нет. А если правильным образом ввести мистическую переговорную силу, решение может появится.
За ссылку спасибо, я читал про окрестр, но давно и особо не вникая.
Оставить комментарий
Имя или ник:
Комментарий: