Две противодействующие стороны (игроки) ведут друг против друга игру, состоящую из достаточно длинной последовательности действий ($% n $% шагов, $% n \to \infty $%). Для этого каждый из них обладает определенным ресурсом (энергией), равным $% nX, nY $% соответственно, где $% X, Y $% – среднее количество ресурса, приходящееся на один шаг. На каждом i-м шаге игроки могут использовать (выделять) произвольное количество своего ресурса $% x_i, y_i $% (конечно, в рамках ограничения $% \sum_{j=1}^i x_j \le nX, \sum_{j=1}^i y_j \le nY $%), при этом игрок выигрывает (зарабатывает 1 очко), если выделенный им ресурс превышает, ресурс, выделенный противником, и проигрывает (теряет 1 очко), если выделенный им ресурс меньше ресурса, выделенного противником. Требуется найти асимптотически оптимальные стратегии игроков (при $% n \to \infty $%), гарантирующие максимум матожидания выигрыша (минимум проигрыша) в игровой последовательности, и определить значение игры.

Примечания: 1. Полагается, что значения $% X, Y $% игрокам заведомо известны. Также игрокам известны действия противника, реализованные на предыдущих шагах игры. 2. Этот вырожденный и модифицированный вариант одной прикладной задачи мне показалось полезным привести в качестве примера динамической игры с необозримым горизонтом. 3. Задача корректно формализуется в игру непосредственно на бесконечном интервале, так что параметр $% n $%, «асимптотическая оптимальность» и «наблюдение за противником» здесь введены лишь для удобства интерпретаций. В частности, это дает пищу для размышлений относительно сходимости оптимальных стратегий, построенных для конечных значений $% n $%, а также различных вариантов адаптивных стратегий к асимптотически оптимальным. стратегиям.

Yog Urt

В связи с поступившим вопросом falcao добавляю пояснения по теоретико-игровм задачам (в комментарий не помещаются)

  1. В случае совпадения ресурсов (ничейный исход) каждый игрок ничего не теряет и не выигрывает.
  2. Антагонистическая игра $%G$% двух игроков задается тройкой $% G = (U,V,Q),$% где $% U,V $% – множества стратегий игроков, а $% Q: U \times V \to E$% – функция, определяющая выигрыш первого игрока (проигрыш второго) при выборе игроками стратегий $% u \in U, v \in V. $%
  3. Игра $% G $% имеет значение, если $%inf \; sup \; Q(u,v)= sup \; inf \; Q(u,v), $% где $% sup $% вычисляется по $% u \in U$% , а $% inf $% – по $% v \in V. $% Если при этом достигаются $% min \; sup Q(u,v^o) $% и $% max \; inf Q(u^o,v) $% (естественно они будут равны), то говорят, что $% u^o, v^o $% составляют равновесную ситуацию $% (u^o, v^o) \in U \times V $% игры $% G $% и являются оптимальными в теоретико-игровом смысле - их не выгодно менять ни одному из игроков. Если при этом указанные min и max не достигаются, то при любых $% \epsilon > 0 $% существуют $%\epsilon$%-оптимальные стратегии (тоже неплохо).
  4. Отсутствие значения игры зачастую свидетельствует о некорректности модели взаимодействия игроков, в частности, неполноте рассматриваемых множеств стратегий. Стандартным способом расширения множеств стратегий является переход к так называемым смешанным (случайным, псевдослучайным) стратегиям, которые задаются вероятностными мерами $% P_u(u), P_v(v) $% (распределениями вероятностей) на исходных множествах стратегий. В отличие от смешанных стратегий исходные стратегии называются чистыми. При смешанном расширении игры выигрыш игроков определяется матожиданием $% M[Q], $% определенным по распределениям $% P_u(u), P_v(v). $%
  5. В нашем случае при $% n=1 $% (например, последний шаг игры) в игре $% G $% имеются оптимальные чистые стратегии – выложить весь ресурс. Эти стратегии составляют равновесную ситуацию. Однако уже при $% n=2, $% вообще говоря, необходим переход к смешанным стратегиям: $% P_{u2}(u), P_{v2}(v). $% При этом можно найти такую пару стратегий $% P^o_{u2}(u), P^o_{v2}(v). $% каждую из которых можно сообщить противнику и тем не менее ему будет не выгодно менять свою оптимальную (равновесную) стратегию.
  6. Для случая $% n \to \infty $% в задаче можно найти простые оптимальные смешанные стратегии игроков $% P^o_u(u), P^o_v(v). $%.

задан 15 Мар '13 14:30

изменен 15 Мар '13 21:12

Несколько уточняющих вопросов. 1) Правильно ли я понимаю, что ничейные исходы игнорируется, то есть их вероятность можно считать равной нулю? 2) Каково определение оптимальной стратегии? Допустим для простоты, что $%n=2$%. Тогда стратегией каждого можно считать точку отрезка. Если мне известна стратегия противника, то я легко могу подобрать под неё что-то оптимальное. Но если она не известна, то всё может зависеть от стратегии выбора стратегий другим игроком. Этот момент, наверное, каким-то стандартным образом объясняется, но хотелось бы понять, как именно.

(15 Мар '13 18:11) falcao

Пояснения приложил к формулировке задачи

(15 Мар '13 20:21) Urt

В добавлении набрано все аккуратно, при просмотре ошибок нет, но в выложенном тексте - сплошные несуразицы, поправить не удается

(15 Мар '13 20:39) Urt

@Urt: я только что увидел Ваши дополнительные пояснения, но пока ещё не успел их прочесть. Причина искажения текста в том, что в нём использованы "звёздочки". Они играют здесь какую-то отдельную роль типа выделений в тексте. Причём в момент написания ничего не заметно: там всё работает как в обычном $%\TeX$%'е. Замените их, пожалуйста, на какие-то другие значки, или на команду \ast.

(15 Мар '13 20:47) falcao

Спасибо, уже поправил. Как будто, без искажений

(15 Мар '13 20:49) Urt

@Urt: Условие задачи теперь в основе своей понятно; постараюсь подумать. Тут вот сейчас был ещё один вопрос теоретико-игрового характера, но там задача была полностью дискретной, поэтому удалось разобраться до конца.

(16 Мар '13 3:48) falcao

@Falcao. Действительно, задача "про самую оптимальную стратегию" и ее решение весьма интересны. Однако она не является в полном смысле игровой (если не говорить о любой оптимизационной задаче, как частном случае игровой). Стратегия компьютера в ней заведомо определена - ее выбор не зависит от стратегии "игрока".

(17 Мар '13 21:02) Urt

@Urt: да, я согласен, что та задача не относится к теории игр. Просто здесь так совпало, что почти подряд прозвучало два вопроса о стратегиях в игре, хотя и в разном смысле слова. Что касается Вашей задачи, то я над ней время от времени думаю. На данный момент у меня возникло предположение, что там средний выигрыш зависит от отношения $%X$% и $%Y$% в сравнении с отношениями чисел Фибоначчи. Пока это всё, правда, только в виде идеи, но если что-то "дозреет", то я здесь напишу.

(17 Мар '13 21:14) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×77

задан
15 Мар '13 14:30

показан
1189 раз

обновлен
17 Мар '13 21:14

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru