Приближенные решения для биматричного равновесия Нэша: различия между версиями

В работе Альтхофера [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], и для них выполняется: