Семинар МЛ ТИ: "Разрешимость в позиционных стратегиях - в поисках полного описания"

Продолжение семинара прошлой недели в этот четверг, 20 января.

Семинар пройдет с 18:10 до 19:30 в аудитории M202, Покровский бульвар, 11.
Онлайн-трансляция в Zoom: https://zoom.us/j/93713061619?pwd=cXdpbk9YaEx6aGZGVURDSVE0NldqUT09

Александр Козачинский продолжит свой доклад на тему «Разрешимость в позиционных стратегиях - в поисках полного описания»

Аннотация:

В области игр на графах особый интерес вызывают выигрышные условия (и, более общо, платежные функции), разрешимые в позиционных стратегиях. Эти условия находят применения в логике (разрешимость логических теорий, модальное mu-исчисление), а также в более практических областях (верификация программ, реактивное программирование). Хотелось бы понять, как вообще могут быть устроены такие выигрышные условия и платежные функции. Классическим результатом в этой области является теорема Жимбера и Желонки (2005) - если платежная функция разрешима в позиционных стратегиях в играх с одним игроком, то и в играх с двумя игроками. Эта теорема значительно упрощает доказательства разрешимости в позиционных стратегиях для конкретных платежных функций. К сожалению, она не дает явного описания всех таких платежных функций. Кажется возможным получить явное описание для платежных функций, удовлетворяющих некоторым дополнительным условиям. Это было сделано мной для непрерывных платежных функций (CONCUR 2021). Непрерывность представляется естественным дополнительным условием, поскольку ему удовлетворяет один из классических примеров позиционной платежной функции - discounted sum payoff. Другим естественным дополнительным условиям представляется префиксная независимость (при удалении любого конечного префикса значение платежной функции не меняется). Классическими примерами с этим условием являются игры четности и циклические игры. Явного описания для этого случая пока не получено, но есть гипотеза, что все такие платежные функции можно получить как циклические игры на упорядоченных группах. В докладе будет предложено рассказать о каком-нибудь из этих результатов.

 Заказ пропуска: dchernyshova@hse.ru

Обращаем ваше внимание на то, что в соответствии с текущими правилами проведения мероприятий в Вышке наш семинар будет проводиться в формате COVID-free.