Приближенные решения для биматричного равновесия Нэша
Ключевые слова и синонимы: эпсилон-равновесие Нэша; эпсилон-поддерживаемое равновесие Нэша
Постановка задачи
Джон Форбс Нэш [14] ввел понятие равновесия Нэша в некооперативных играх и доказал, что для любой игры существует по меньшей мере одно такое равновесие. Хорошо известный алгоритм вычисления равновесия Нэша для игры с двумя игроками – алгоритм Лемке-Хоусона [12] – в худшем случае имеет экспоненциальную сложность от количества доступных чистых стратегий [16]. Недавно Даскалакис и коллеги [5] показали, что задача вычисления равновесия Нэша для игры с четырьмя и более игроками является PPAD-полной; этот результат был впоследствии распространен на игры с тремя игроками [8]. В конечном счете, Чен и Денг [3] доказали, что задача является PPAD-полной также и для игр с двумя игроками.
В результате появилась задача вычисления приближенного равновесия Нэша. На настоящий момент было опубликовано несколько вариантов приближенного равновесия Нэша; здесь будут рассмотрены понятия [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша и [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемого равновесия Нэша. [math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша представляет собой профиль стратегии, такой, что ни один игрок, изменяющий решение, не может получить выигрыш больше, чем выигрыш при определенном профиле стратегии плюс [math]\displaystyle{ \epsilon \, }[/math]. Более строгим является понятие [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемых равновесий Нэша; они представляют собой профили стратегий, такие, что каждый игрок использует только чистые стратегии с приближенно лучшим ответом с ненулевой вероятностью.
Нотация
Для вектора [math]\displaystyle{ \mathbf{x} }[/math] формата [math]\displaystyle{ n \times 1 }[/math] обозначим за [math]\displaystyle{ x_1,\!...,x_n }[/math] компоненты [math]\displaystyle{ \mathbf{x} }[/math] и за [math]\displaystyle{ \mathbf{x}^T }[/math] – перестановку вектора [math]\displaystyle{ \mathbf{x} }[/math]. Обозначим за [math]\displaystyle{ \mathbf{e}_i }[/math] вектор столбца, имеющего значение 1 в i-й координате и 0 – во всех остальных. Для матрицы A размера [math]\displaystyle{ n \times m }[/math] обозначим за [math]\displaystyle{ a_{ij} \, }[/math] элемент в i-й строке и j-м столбце матрицы A. Пусть [math]\displaystyle{ \mathbb{P}^n }[/math] обозначает множество всех векторов вероятности в n измерениях: [math]\displaystyle{ \mathbb{P}^n = \left\{ \mathbf{z} \in \mathbb{R}^n_{\ge 0} : \sum_{i=1}^n z_i=1 \right\} }[/math]
Биматричные игры
Биматричные игры [18] – это специальный случай игр для двух игроков, в которых функции выигрыша могут быть описаны двумя действительными матрицами [math]\displaystyle{ n \times m }[/math] – A и B. n строк матриц A и B представляют множество действий первого игрока (игрока по строкам), m столбцов представляют множество действий второго игрока (игрока по столбцам). Если игрок по строкам выбирает действие i, а игрок по столбцам выбирает действие j, то первый получает выигрыш [math]\displaystyle{ a_{ij} \, }[/math], а второй – выигрыш [math]\displaystyle{ b_{ij} \, }[/math]. В силу этого биматричные игры обозначаются как [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math].
Стратегия для игрока представляет собой любое распределение вероятностей на его наборе действий. Таким образом, стратегия для игрока по строкам может быть выражена в виде вектора вероятности [math]\displaystyle{ \mathbf{x} \in \mathbb{P}^n }[/math], а стратегия для игрока по столбцам – в виде вектора вероятности [math]\displaystyle{ \mathbf{y} \in \mathbb{P}^m }[/math]. Каждая точка экстремума [math]\displaystyle{ \mathbf{e_i} \in \mathbb{P}_n }[/math] ([math]\displaystyle{ \mathbf{e_j} \in \mathbb{P}^m }[/math]), соответствующая стратегии, назначающей вероятность 1 i-й строке (j-му столбцу), называется чистой стратегией для игрока по строке (столбцу). Профиль стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]) представляет собой комбинацию (в общем случае смешанных) стратегий, по одной для каждого игрока. Для данного профиля стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]), игроки получают ожидаемый выигрыш [math]\displaystyle{ \mathbf{x}^T A \mathbf{y} }[/math] (игрок по строкам) и [math]\displaystyle{ \mathbf{x}^T B \mathbf{y} }[/math] (игрок по столбцам).
Если обе матрицы выигрышей принадлежат пространству [0, 1]m × n, то игра называется [0, 1]-биматричной, или положительно нормализованной, игрой. Специальный случай биматричных игр, в котором все элементы матрицы принадлежат к интервалу {0, 1}, называется {0, 1}-биматричной игрой или игрой с выигравшими и проигравшими. Биматричная игра [math]\displaystyle{ \langle A, B \rangle }[/math] называется игрой с нулевой суммой, если B = –А.
Приближенное равновесие Нэша
Определение 1 ([math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша)
Для любого [math]\displaystyle{ \epsilon \gt 0 \, }[/math] профиль стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]) является [math]\displaystyle{ \epsilon \, }[/math]-равновесием Нэша для биматричной игры [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math], если
- Для всех чистых стратегий [math]\displaystyle{ i \in \{1,\!...,n\} }[/math] игрока по строкам [math]\displaystyle{ \mathbf{e_i}^T A \mathbf{y} \le \mathbf{x}^T A \mathbf{y} }[/math] + [math]\displaystyle{ \epsilon \, }[/math];
- Для всех чистых стратегий [math]\displaystyle{ j \in \{1,\!...,m\} }[/math] игрока по столбцам [math]\displaystyle{ \mathbf{x}^T B \mathbf{e_j}\le \mathbf{x}^T B \mathbf{y} }[/math] + [math]\displaystyle{ \epsilon \, }[/math].
Определение 2 ([math]\displaystyle{ \epsilon \, }[/math]-поддерживаемое равновесие Нэша)
Для любого [math]\displaystyle{ \epsilon \, }[/math] > 0 профиль стратегии ([math]\displaystyle{ \mathbf{x}, \mathbf{y} }[/math]) является [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемым равновесием Нэша для биматричной игры [math]\displaystyle{ \Gamma= \langle A,B \rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math], если
- Для всех чистых стратегий [math]\displaystyle{ i \in \{1,\!...,n\} }[/math] игрока по строкам [math]\displaystyle{ x_i \gt 0 \Rightarrow \; \mathbf{e_i}^T A \mathbf{y} \ge \mathbf{e_k}^T A \mathbf{y} - \epsilon }[/math] [math]\displaystyle{ \forall k \in \{1,\!...,n\} }[/math]
- Для всех чистых стратегий [math]\displaystyle{ j \in \{1,\!...,m\} }[/math] игрока по столбцам [math]\displaystyle{ y_j \gt 0 \Rightarrow \; \mathbf{x}^T B \mathbf{e_j} \ge \mathbf{x}^T B \mathbf{e_k} - \epsilon }[/math] [math]\displaystyle{ \forall k \in \{1,\!...,m\} }[/math]
Заметим, что оба понятия приближенного равновесия определяются с использованием члена аддитивной ошибки [math]\displaystyle{ \epsilon \, }[/math]. Хотя (точные) равновесия Нэша, как известно, не поддаются положительному масштабированию, важно отметить, что приближенные версии масштабированию поддаются. В силу этого широко используемое в литературе предположение, относящееся к приближенным равновесиям Нэша, заключается в том, что биматричная игра является положительно нормализованной, и это предположение принято в данном изложении.
Основные результаты
В работе Альтхофера [1] показано, что для любого вектора вероятности [math]\displaystyle{ p \, }[/math] существует вектор вероятности [math]\displaystyle{ \hat{p} }[/math] с логарифмической поддержкой, так что для фиксированной матрицы C выполняется [math]\displaystyle{ max_j \left | \mathbf{p}^TC \mathbf{e_j} - \mathbf{\hat{p}}^TC \mathbf{e_j} \right | \le \epsilon \, }[/math] для любого константного [math]\displaystyle{ \epsilon \, }[/math] > 0. Используя этот факт, Липтон, Маркакис и Мета [13] показали, что для любой биматричной игры и для любого константного [math]\displaystyle{ \epsilon \, }[/math] > 0 существует [math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша с только логарифмической поддержкой (от числа доступных чистых стратегий n). Рассмотрим биматричную игру [math]\displaystyle{ \Gamma = \langle A,B \rangle }[/math]. Пусть [math]\displaystyle{ (\mathbf{x, y}) }[/math] – равновесие Нэша для [math]\displaystyle{ \Gamma }[/math]. Зафиксируем положительное число k и сформируем мультимножество [math]\displaystyle{ S_1 \, }[/math], выполнив выборку k раз из множества чистых стратегий игрока по строкам независимым случайным образом в соответствии с распределением [math]\displaystyle{ \mathbf{x} }[/math]. Сформируем подобным же образом мультимножество [math]\displaystyle{ S_2 \, }[/math], выполнив выборку k раз из множества чистых стратегий игрока по столбцам в соответствии с распределением [math]\displaystyle{ \mathbf{y} }[/math]. Пусть [math]\displaystyle{ \mathbf{\hat{x}} }[/math] – смешанная стратегия для игрока по строкам, которая назначает вероятность 1/k каждому члену [math]\displaystyle{ S_1 \, }[/math] и 0 – всем остальным чистым стратегиям, а [math]\displaystyle{ \mathbf{\hat{y}} }[/math] – смешанная стратегия для игрока по столбцам, которая назначает вероятность 1/k каждому члену [math]\displaystyle{ S_2 \, }[/math] и 0 – всем остальным чистым стратегиям. Тогда [math]\displaystyle{ \mathbf{x} }[/math] и [math]\displaystyle{ \mathbf{y} }[/math] называются k-однородными [13], и для них выполняется:
Теорема 1 ([13])
Для любого равновесия Нэша [math]\displaystyle{ (\mathbf{x, y}) }[/math] биматричной игры с матрицами [math]\displaystyle{ n \times n }[/math] и для любого [math]\displaystyle{ \epsilon \gt 0 \, }[/math] существует, для каждого [math]\displaystyle{ k \ge(12 ln n)/ \epsilon \, }[/math]2, пара k-однородных стратегий [math]\displaystyle{ \mathbf{\hat{x}}, \mathbf{\hat{y}} }[/math] , таких, что ( [math]\displaystyle{ \mathbf{\hat{x}}, \mathbf{\hat{y}} }[/math] ) представляет собой [math]\displaystyle{ \epsilon \, }[/math]-равновесие Нэша.
В результате этого получаем квазиполиномиальный алгоритм (nO(ln n)) для вычисления приближенного равновесия. Более того, как было отмечено в [1], ни один алгоритм, исследующий поддержку менее чем за время ln n, не может достичь лучшего приближения, чем 1/4.
Теорема 2 ([4])
Задача вычисления [math]\displaystyle{ 1/n^{\Theta (1)} \, }[/math]-равновесия Нэша для биматричной игры с матрицами [math]\displaystyle{ n \times n }[/math] является PPAD-полной.
Теорема 2 утверждает, что за исключением случаев, когда PPAD [math]\displaystyle{ \subseteq }[/math] P, не существует аппроксимационной схемы с полностью полиномиальным временем выполнения для вычисления равновесия в биматричных играх. Однако это не исключает существования аппроксимационной схемы с полиномиальным временем для вычисления [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша, где [math]\displaystyle{ \epsilon \, }[/math] является абсолютной константой, и даже в случае [math]\displaystyle{ \epsilon \, = \Theta \big( 1/poly(ln n) \big). }[/math]Более того, как было замечено в [4], если бы задача нахождения [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша была PPAD-полной в случае, когда [math]\displaystyle{ \epsilon \, }[/math] является абсолютной константой, то, согласно Теореме 1, все PPAD-полные задачи были бы разрешимы за квазиполиномиальное время, что едва ли соответствует истине.
Две независимых последовательных работы [6] и [10] впервые продемонстрировали прогресс в нахождении [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша и [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемого равновесия Нэша для биматричных игр и некоторого константного [math]\displaystyle{ 0 \lt \epsilon \lt 1 \, }[/math]. В частности, в работе Контогианниса, Панагопулу и Спиракиса [10] был предложен простой линейный алгоритм для вычисления 3/4-равновесия Нэша для любой биматричной игры:
Теорема 3 ([10])
Рассмотрим любую биматричную игру [math]\displaystyle{ \Gamma = \langle A, B\rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math]; пусть [math]\displaystyle{ a_{i1}, _{j1} = max_i, _j a_{ij} \, }[/math] и [math]\displaystyle{ b_{i2}, _{j2} = max_i, _j b_{ij} \, }[/math]. Тогда пара стратегий ([math]\displaystyle{ \mathbf{\hat{x}}, \mathbf{\hat{y}} }[/math] ), где [math]\displaystyle{ \mathbf{\hat{x}}_{i1} = \mathbf{\hat{x}}_{i2} = \mathbf{\hat{y}}_{j1} = \mathbf{\hat{y}}_{j2} = 1/2 }[/math], является 3/4-равновесием Нэша для игры [math]\displaystyle{ \Gamma }[/math].
Вышеприведенная техника может быть расширена таким образом, чтобы получить более строгое, параметризованное приближение:
Теорема 4 ([10])
Рассмотрим биматричную игру [math]\displaystyle{ \Gamma = \langle A, B \rangle }[/math] с матрицами [math]\displaystyle{ n \times m }[/math]. Пусть [math]\displaystyle{ \lambda_1^* ( \lambda_2^* ) }[/math] – минимальный среди всех равновесий Нэша для [math]\displaystyle{ \Gamma \, }[/math] ожидаемый выигрыш для игрока по строке (столбцу); пусть [math]\displaystyle{ \lambda = max \, }[/math] { [math]\displaystyle{ \lambda_1^*, \lambda_2^* }[/math] }. Тогда существует [math]\displaystyle{ (2 + \lambda)/4 \, }[/math]-равновесие Нэша, которое может быть вычислено за время, полиномиальное относительно n и m.
Даскалакис, Мета и Пападимитриу [6] приводят простой алгоритм для вычисления 1/2-равновесия Нэша:
Выбрать произвольную строку для игрока по строкам, к примеру, строку i. Пусть [math]\displaystyle{ j = arg\;max_{j\prime}\,b_{ij\prime} \, }[/math]. Пусть [math]\displaystyle{ k = arg\;max_{k\prime}\,a_{k\prime j} \, }[/math]. Таким образом, j – это столбец с лучшим ответом для игрока по столбцам в строке i, а k – строка с лучшим ответом для игрока по строкам в столбце j. Пусть [math]\displaystyle{ \mathbf{\hat{x}} = 1/2 \mathbf{e_i} + 1/2 \mathbf{e_k} }[/math] и [math]\displaystyle{ \mathbf{\hat{y}} = \mathbf{e_j} }[/math], т.е. игрок по строкам играет строку i или строку k с вероятностью 1/2 для каждой, тогда как игрок по столбцам играет столбец j с вероятностью 1. Тогда верна
Теорема 5 ([6])
Профиль стратегии ([math]\displaystyle{ \mathbf{\hat{x}} ,\mathbf{\hat{y}} }[/math]) является 1/2-равновесием Нэша.
В источнике [7] представлена полиномиальная конструкция (на базе линейного программирования) 0.38-равновесия Нэша.
Используя более строгий подход к приближенному вычислению поддерживаемого равновесия Нэша, Даскалакис, Мета и Пападимитриу [6] предложили алгоритм, который, при выполнении весьма интересных и правдоподобных теоретико-графовых предположений, строит 5/6-поддерживаемое равновесие Нэша за полиномиальное время. Однако статус истинности этих умозаключений до сих пор неясен. В работе [6] также было показано, как преобразовать [0, 1]-биматричную игру в {0, 1}-биматричную игру того же размера, в силу чего любое [math]\displaystyle{ \epsilon \, }[/math]-поддерживаемое равновесие Нэша получившейся игры является (1 + [math]\displaystyle{ \epsilon \, }[/math])/2-поддерживаемым равновесием Нэша исходной игры.
В работе Контогианниса и Спиракиса [11] приведен полиномиальный алгоритм вычисления 1/2-поддерживаемого равновесия Нэша для произвольных игр с выигравшими и проигравшими. В основе алгоритма лежит идея равномерного разделения величины отклонения от игры с нулевой суммой между двумя игроками и последующего решения получившейся игры с нулевой суммой за полиномиальное время, используя ее прямое сходство с алгоритмами линейного программирования. Доказано, что полученное равновесие Нэша для игры с нулевой суммой является 1/2-поддерживаемым равновесием Нэша для исходной игры с выигравшими и проигравшими. Таким образом, верна
Теорема 6 ([11])
Для любых биматричных игр с выигравшими и проигравшими возможно построить за полиномиальное время профиль, представляющий собой 1/2-поддерживаемое равновесие Нэша для этой игры.
В той же публикации Контогианнис и Спиракис [11] параметризовали вышеописанную методологию для применения ее к произвольным биматричным играм. Новая техника способствует нахождению более слабого [math]\displaystyle{ \phi }[/math]-поддерживаемого равновесия Нэша для игр с выигравшими и проигравшими, где [math]\displaystyle{ \phi = \left ( \sqrt{5} -1 \right )/2 }[/math] – величина золотого сечения. Тем не менее, эта параметризованная техника легко расширяется на произвольные биматричные игры, что гарантирует нахождение 0.658-поддерживаемого равновесия Нэша за полиномиальное время:
Теорема 7 ([11])
Для любых биматричных игр возможно построить [math]\displaystyle{ ( \sqrt{11} /2 - 1 ) }[/math]-поддерживаемое равновесие Нэша за полиномиальное время.
Два недавних результата улучшили статус приближения [math]\displaystyle{ \epsilon \, }[/math]-равновесия Нэша:
Теорема 8 ([2])
Существует алгоритм с полиномиальным временем, основанный на алгоритмах линейного программирования, который строит 0.36392-равновесие Нэша.
Следующий результат на данный момент является наилучшим:
Теорема 9 ([17])
Существует алгоритм с полиномиальным временем, основанный на нахождении неподвижных точек в естественной задаче оптимизации, который строит 0.3393-равновесие Нэша.
Каннан и Теобальд [9] исследовали иерархию биматричных игр [math]\displaystyle{ \langle A, B \rangle }[/math], получаемую из ограничения ранга матрицы А + В до фиксированного ранга, не превышающего k. Они предложили новую модель [math]\displaystyle{ \epsilon \, }[/math]-аппроксимации для игр ранга k и, используя результаты квадратичной оптимизации, показали, что приближенные равновесия Нэша для игр с константным рангом могут быть вычислены детерминированным образом за время, полиномиальное относительно 1/[math]\displaystyle{ \epsilon \, }[/math]. Кроме того, в [9] представлен рандомизированный алгоритм приближения для определенных задач квадратичной оптимизации, что позволяет создать рандомизированный алгоритм приближения для задачи нахождения равновесия Нэша. Этот рандомизированный алгоритм имеет практически ту же временную сложность, что и детерминированный, однако при условии истинности предположения позволяет найти точное решение за полиномиальное время. Наконец, эти же авторы предложили алгоритм с полиномиальным временем для относительного приближения (касающегося выигрышей при равновесии) для случая, когда матрица A + B имеет неотрицательную декомпозицию.
Применение
Теория некооперативных игр и основное понятие для их решения – равновесие Нэша – широко использовались для понимания феноменов, наблюдаемых при взаимодействии лиц, принимающих решения, и применялись во множестве различных научных областей в таких сферах, как биология, экономика, социология и искусственный интеллект. Однако, поскольку вычисление равновесия Нэша в общем случае является PPAD-полной задачей, важное значение имеет создание эффективных алгоритмов для нахождения приближенного равновесия; изложенные выше алгоритмы представляют собой первые шаги на этом пути.
См. также
Литература
1. Althofer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebr. Appl. 199, 339-355(1994)
2. Bosse, H., Byrka, J., Markakis, E.: New Algorithms for Approximate Nash Equilibria in Bimatrix Games. In: LNCS Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), San Diego, 12-14 December 2007
3. Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). Berkeley, 21-24 October 2005
4. Chen, X., Deng, X., Teng, S.-H.: Computing Nash equilibria: Approximation and smoothed complexity. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), Berkeley, 21-24 October 2006
5. Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a Nash equilibrium. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06), pp. 71-78. Seattle, 21-23 May 2006
6. Daskalakis, C., Mehta, A., Papadimitriou, C.: A note on approximate Nash equilibria. In: Proceedings of the 2nd Workshop on Internet and Network Economics (WINE'06), pp. 297-306. Patras, 15-17 December 2006
7. Daskalakis, C., Mehta, A., Papadimitriou, C: Progress in approximate Nash equilibrium. In: Proceedings of the 8th ACM Conference on Electronic Commerce (EC07), San Diego, 11-15 June 2007
8. Daskalakis, C., Papadimitriou, C.: Three-player games are hard. In: Electronic Colloquium on Computational Complexity (ECCC) (2005)
9. Kannan, R., Theobald, T.: Games of fixed rank: A hierarchy of bimatrix games. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 7-9 January 2007
10. Kontogiannis, S., Panagopoulou, P.N., Spirakis, P.G.: Polynomial algorithms for approximating Nash equilibria of bimatrix games. In: Proceedings of the 2nd Workshop on Internet and Network Economics (WINE'06), pp. 286-296. Patras, 15-17 December 2006
11. Kontogiannis, S., Spirakis, P.G.: Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07, Track A: Algorithms and Complexity), Wroclaw, 9-13 July 2007
12. Lemke, C.E., Howson, J.T.: Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12,413-423 (1964)
13. Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple startegies. In: Proceedings of the 4th ACM Conference on Electronic Commerce (EC'03), pp. 36-41. San Diego, 9-13 June 2003
14. Nash, J.: Noncooperative games. Ann. Math. 54, 289-295 (1951)
15. Papadimitriou, C.H.: On inefficient proofs of existence and complexity classes. In: Proceedings of the 4th Czechoslovakian Symposium on Combinatorics 1990, Prachatice (1991)
16. Savani, R., von Stengel, B.: Exponentially many steps for finding a nash equilibrium in a bimatrix game. In: Proceedings of the45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 258-267. Rome, 17-19 October 2004
17. Tsaknakis, H., Spirakis, P.: An Optimization Approach for Approximate Nash Equilibria. In: LNCS Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), also in the Electronic Colloquium on Computational Complexity, (ECCC),TR07-067 (Revision), San Diego, 12-14 December 2007
18. von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ (1944)
