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

В работе Альтхофера [1] показано, что для любого вектора вероятности <math>\mathbf{p}</math> существует вектор вероятности <math>\hat{p}</math> с логарифмической поддержкой, так что для фиксированной матрицы <math>C, max_j</math> <math>\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>-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий <math>n</math>). Рассмотрим биматричную игру <math>\Gamma = \langle A,B \rangle</math>. Пусть <math>(\mathbf{x, y})</math> – равновесие Нэша для <math>\Gamma</math>. Зафиксируем положительное число <math>k</math> и сформируем мультимножество <math>S_1</math>, выполнив выборку <math>k</math> раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением <math>x</math>. Сформируем подобным же образом мультимножество <math>S_2</math>, выполнив выборку <math>k</math> раз из множества чистых стратегий игрока по столбцам в соответствии с распределением <math>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 – всем остальным чистым стратегиям. Тогда x и у называются ''k''-однородными [13], и для них выполняется: