Wiki - Факультет компьютерных наук - Вклад [ru]

Равновесия Нэша в чистых стратегиях (проект)

2016-10-10T14:03:39Z

Gurvich: Новая страница, с помощью формы Новый_проект

{{Карточка_проекта
|name=Равновесия Нэша в чистых стратегиях
|mentor=Владимир Гурвич
|mentor_login={{URLENCODE:Gurvich|WIKI}}
|semester=Осень 2016
|course=2
|summer=on
|number_of_students=2
|categorize=yes
}}

=== Что это за проект? ===
Равновесия по Нэшу (РН) в чистых стационарных стратегиях для позиционных и стохастических игр с полной информацией хорошо изучено в двух случаях:
(а) игры двух лиц с нулевой суммой;
(б) ациклические игры многих лиц, т.е,. ориентированный граф, моделирующий игру, не имеет ориентированных циклов.
В обоих случаях имеются "мощные" теоремы существования, гарантирующие наличие РН в чистых стационарных и равномерно оптимальных (или эргодических, т.е., не зависящих от начальной позиции) стратегиях.
Однако, в остальных случаях (игры двух лиц с ненулевой суммой или более чем двух лиц) вопрос слабо изучен. Проект рассчитан на решение некоторых открытых проблем в этой области.

=== Чему вы научитесь? ===
Элементам теории бескоалиционных кооперативных игр многих лиц, а также стохастических, позиционных игр; методам доказательства (и опровержения) существования РН в чистых стратегиях.

=== Какие начальные требования? ===
Свободное владение С или С++ и опыт работы на этом языке.

=== Какие будут использоваться технологии? ===
Компьютерные эксперименты в теории позиционных и стохастических игр.

=== Темы вводных занятий ===
Матричные игры; махимин, минимах и седловая точка.
Игры многих лиц в нормалльной форме; равновесия по Нэшу (РН) в смешанных и чистых стратегиях.
Теорема Брауэра (1911) и фон Неймана (1928), Какутани (1941) и Нэша (1950).
Позиционные и стохастические игры; стационарные и исторически-зависимые стратегии;
предельный средний и тотальный эффективные платежи.
Обратная индукция и принцип Белмана.

=== Направления развития ===
Цель - получение полной теории РН в чистых стационарных стратегиях во всех классах некооперативных игр двух и более игроков. Эта область развивается в 1950 года и постепенно "белых пятен" (открытых вопросов) в ней становится меньше.

=== Критерии оценки ===
4-5 Успешное изучение теории плюс создание работающей тестовой программы;
6-9 Успешное изучение теории и создание эффективной тестовой тестовой программы, позволяющей исследовать примеры достаточно большого размера;
10 Получение любых новых результатов, положительных или отрицательных.

=== Ориентировочное расписание занятий ===
Контакты по скайпу и электронной почте в любое время; встречи в ВШЭ - по договорённости.

Двойственные графы на поверхностях (проект)

2016-10-09T13:50:29Z

Gurvich: Добавлены критерии оценки работы.

{{Карточка_проекта
|name=Двойственные графы на поверхностях
|mentor=Владимир Гурвич
|mentor_login={{URLENCODE:Gurvich|WIKI}}
|semester=Осень 2016
|course=2
|summer=on
|number_of_students=2
|categorize=yes
}}

=== Что это за проект? ===
Охарактеризовать пары двойственных графов на поверхностях. Этот вопрос из топологии был недавно решён в чисто комбинаторных терминах. Однако, остался открытым вопрос, какие векторы валентностей могут иметь такие графы. Вопрос этот имеет важные приложения в топологии и в физике. Предлагается написать компьютерный код, перечисляющий все пары двойственных графов небольшого размера и выяснить, какие пары векторов валентностей возможны, какие нет. Результат может привести к решению важдой открытой проблемы.

=== Чему вы научитесь? ===
Применять программирование для постановки экспериментов в математических исследованиях

=== Какие начальные требования? ===
Свободное владение одним из языков программирования и опыт работы на нём. Желательно умение писать программы, работающие не только правильно, но и быстро.

=== Какие будут использоваться технологии? ===
Программирование на персональном компьютере. Прогонка программы на мощном компьютере.

=== Темы вводных занятий ===
Двойственные графы на поверхности и биматрицы.
Комбинаторные условия на биматрицу, необходимые и достаточные для того,
чтобы она соответствовала паре двойственных графов.
Векторы валентностей двойственных графов.

=== Направления развития ===
Если задача будет успешно решена, она позволит получать новые результаты в топологии и в физике.

=== Критерии оценки ===
Успешное написание программы в разумные сроки (4-5 недель), правильность её работы и быстродействие.
Сложность входных данных определяется количеством рёбер m в парах двойственных графов.
Оценка будет вычисляться по простой формуле m + 2, то есть, если программа будет эффективно работать
при m = 2,3 - оценка 4-5;
при m = 4,5 - оценка 6-7;
при m = 6,7,8+ - оценка 8-10.

=== Ориентировочное расписание занятий ===
Общение по скайпу и электронной почте возможно в любое время. Встречи в ВШЭ по договорённости.

Двойственные графы на поверхностях (проект)

2016-10-07T15:57:24Z

Gurvich: Новая страница, с помощью формы Новый_проект

{{Карточка_проекта
|name=Двойственные графы на поверхностях
|mentor=Владимир Гурвич
|mentor_login={{URLENCODE:Gurvich|WIKI}}
|semester=Осень 2016
|course=2
|summer=on
|number_of_students=2
|categorize=yes
}}

=== Что это за проект? ===
Охарактеризовать пары двойственных графов на поверхностях. Этот вопрос из топологии был недавно решён в чисто комбинаторных терминах. Однако, остался открытым вопрос, какие векторы валентностей могут иметь такие графы. Вопрос этот имеет важные приложения в топологии и в физике. Предлагается написать компьютерный код, перечисляющий все пары двойственных графов небольшого размера и выяснить, какие пары векторов валентностей возможны, какие нет. Результат может привести к решению важдой открытой проблемы.

=== Чему вы научитесь? ===
Применять программирование для постановки экспериментов в математических исследованиях

=== Какие начальные требования? ===
Свободное владение одним из языков программирования и опыт работы на нём. Желательно умение писать программы, работающие не только правильно, но и быстро.

=== Какие будут использоваться технологии? ===
Программирование на персональном компьютере. Прогонка программы на мощном компьютере.

=== Темы вводных занятий ===
Двойственные графы на поверхности и биматрицы.
Комбинаторные условия на биматрицу, необходимые и достаточные для того,
чтобы она соответствовала паре двойственных графов.
Векторы валентностей двойственных графов.

=== Направления развития ===
Если задача будет успешно решена, она позволит получать новые результаты в топологии и в физике

=== Критерии оценки ===
Успешное написание программы в разумные сроки (4-5 недель), правильность её работы и быстродействие.

=== Ориентировочное расписание занятий ===
Общение по скайпу и электронной почте возможно в любое время. Встречи в ВШЭ по договорённости.