4430
правок
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
Строка 32: | Строка 32: | ||
== Основные результаты == | == Основные результаты == | ||
В работе Альтхофера [1] показано, что для любого вектора вероятности p существует вектор вероятности p с логарифмической поддержкой, так что для фиксированной матрицы C maxj |pTCej – TCej| ≤ <math>\epsilon \, </math> для любой константы <math>\epsilon \, </math> > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любой константы <math>\epsilon \, </math> > 0 существует <math>\epsilon \, </math>-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру Г = A, B. Пусть let (x, y) – равновесие Нэша для Г. Зафиксируем положительное число k и сформируем мультимножество S1, выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в | В работе Альтхофера [1] показано, что для любого вектора вероятности p существует вектор вероятности p с логарифмической поддержкой, так что для фиксированной матрицы C maxj |pTCej – TCej| ≤ <math>\epsilon \, </math> для любой константы <math>\epsilon \, </math> > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любой константы <math>\epsilon \, </math> > 0 существует <math>\epsilon \, </math>-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру Г = A, B. Пусть let (x, y) – равновесие Нэша для Г. Зафиксируем положительное число k и сформируем мультимножество S1, выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением x. Сформируем подобным же образом мультимножество S2, выполнив выборку k раз из множества чистых стратегий игрока по столбцам в соответствии с распределением y. Пусть – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/k каждому члену S1 и 0 – всем остальным чистым стратегиям, а – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/k каждому члену S2 и 0 – всем остальным чистым стратегиям. Тогда x и у называются k-однородными [13], и для них выполняется | ||
Теорема 1 ([13]) Для любого равновесия Нэша (x, y) биматричной игры с | Теорема 1 ([13]) Для любого равновесия Нэша (x, y) биматричной игры с матрицами n х n и для любого <math>\epsilon \, </math> > 0 существует, для каждого k (12 ln n)/<math>\epsilon \, </math>2, пара k-однородных стратегий , , таких, что ( , ) представляет собой <math>\epsilon \, </math>-равновесие Нэша. | ||
В результате этого получаем квазиполиномиальный алгоритм сложности (nO(ln n)) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4. | В результате этого получаем квазиполиномиальный алгоритм сложности (nO(ln n)) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4. | ||
Строка 76: | Строка 76: | ||
== Применение == | == Применение == | ||
Теория некооперативных игр и основное понятие для их решения – равновесие Нэша – широко использовались для понимания феноменов, наблюдаемых при взаимодействии лиц, принимающих решения, и применялись во множестве различных научных областей в таких сферах, как биология, экономика, социология и искусственный интеллект. Однако, поскольку вычисление | Теория некооперативных игр и основное понятие для их решения – равновесие Нэша – широко использовались для понимания феноменов, наблюдаемых при взаимодействии лиц, принимающих решения, и применялись во множестве различных научных областей в таких сферах, как биология, экономика, социология и искусственный интеллект. Однако, поскольку вычисление равновесия Нэша в общем случае является PPAD-полной задачей, важное значение имеет создание эффективных алгоритмов для нахождения приближенного равновесия; изложенные выше алгоритмы представляют собой первые шаги на этом пути. | ||
== См. также == | == См. также == |
правок