4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 36: | Строка 36: | ||
В работе Альтхофера [1] показано, что для ''любого'' вектора вероятности <math>p \, </math> существует вектор вероятности <math>\hat{p}</math> с логарифмической поддержкой, так что для фиксированной матрицы C выполняется <math>max_j \left | \mathbf{p}^TC \mathbf{e_j} - \mathbf{\hat{p}}^TC \mathbf{e_j} \right | \le \epsilon \, </math> для любого константного <math>\epsilon \, </math> > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любого ''константного'' <math>\epsilon \, </math> > 0 существует <math>\epsilon \, </math>-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру <math>\Gamma = \langle A,B \rangle</math>. Пусть <math>(\mathbf{x, y})</math> – равновесие Нэша для <math>\Gamma</math>. Зафиксируем положительное число k и сформируем мультимножество <math>S_1 \, </math>, выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением <math>\mathbf{x}</math>. Сформируем подобным же образом мультимножество <math>S_2 \, </math>, выполнив выборку k раз из множества чистых стратегий игрока по столбцам в соответствии с распределением <math>\mathbf{y}</math>. Пусть <math>\mathbf{\hat{x}}</math> – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/k каждому члену <math>S_1 \, </math> и 0 – всем остальным чистым стратегиям, а <math>\mathbf{\hat{y}}</math> – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/k каждому члену <math>S_2 \, </math> и 0 – всем остальным чистым стратегиям. Тогда <math>\mathbf{x}</math> и <math>\mathbf{y}</math> называются k-однородными [13], и для них выполняется: | В работе Альтхофера [1] показано, что для ''любого'' вектора вероятности <math>p \, </math> существует вектор вероятности <math>\hat{p}</math> с логарифмической поддержкой, так что для фиксированной матрицы C выполняется <math>max_j \left | \mathbf{p}^TC \mathbf{e_j} - \mathbf{\hat{p}}^TC \mathbf{e_j} \right | \le \epsilon \, </math> для любого константного <math>\epsilon \, </math> > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любого ''константного'' <math>\epsilon \, </math> > 0 существует <math>\epsilon \, </math>-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру <math>\Gamma = \langle A,B \rangle</math>. Пусть <math>(\mathbf{x, y})</math> – равновесие Нэша для <math>\Gamma</math>. Зафиксируем положительное число k и сформируем мультимножество <math>S_1 \, </math>, выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением <math>\mathbf{x}</math>. Сформируем подобным же образом мультимножество <math>S_2 \, </math>, выполнив выборку k раз из множества чистых стратегий игрока по столбцам в соответствии с распределением <math>\mathbf{y}</math>. Пусть <math>\mathbf{\hat{x}}</math> – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/k каждому члену <math>S_1 \, </math> и 0 – всем остальным чистым стратегиям, а <math>\mathbf{\hat{y}}</math> – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/k каждому члену <math>S_2 \, </math> и 0 – всем остальным чистым стратегиям. Тогда <math>\mathbf{x}</math> и <math>\mathbf{y}</math> называются k-однородными [13], и для них выполняется: | ||
[13] | '''Теорема 1''' ([13]) | ||
В результате этого получаем квазиполиномиальный алгоритм | '''Для любого равновесия Нэша <math>(\mathbf{x, y})</math> биматричной игры с матрицами <math>n \times n</math> и для любого <math>\epsilon > 0 \, </math> существует, для каждого <math>k \ge(12 ln n)/ \epsilon \, </math><sup>2</sup>, пара k-однородных стратегий <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> , таких, что ( <math>\mathbf{\hat{x}}, \mathbf{\hat{y}}</math> ) представляет собой <math>\epsilon \, </math>-равновесие Нэша. | ||
''' | |||
В результате этого получаем квазиполиномиальный алгоритм (<big>n<sup>O(ln n)</sup></big>) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4. | |||
===Теорема 2 === | ===Теорема 2 === |
правок