Hardness of Approximation Between P and NP. Aviad Rubinstein
href="#fb3_img_img_3399a8ce-339b-54ab-908b-b41eb6922d11.png" alt="image"/>, and the last follows from Lemma 3.3.
Using that f is O(1)-Lipschitz together with Equation (3.5), we get that
with probability 1 − O(ϵ4).
By Lemma 3.8 we know that
Using similar arguments to those of Lemma 3.3 we can show that
with probability 1 − O(ϵ4). As in the derivation of Equation (3.5), this implies:
with probability 1 − O(ϵ4).
With probability 1 − O(ϵ2), Inequalities (3.5), (3.4), (3.9), (3.8), (3.7), (3.6) hold simultaneously. In such a case, by the triangle inequality and by applying the inequalities in the exact order above, we have
Proof
Proof of Theorem 3.1. Any communication protocol that solves the ϵ4-Nash equilibrium problem in games of size N × N for N = 2Θ(n) induces a communication protocol for the problem SIMULATION END-OF-THE-LINE: Alice constructs her utility in the above presented game using her private information of the αs, Bob constructs his utility using the βs. They implement the communication protocol to find an ϵ4-Nash equilibrium, and then both of them know
Using Corollary 3.4, we deduce that the communication complexity of ϵ4-Nash equilibrium in games of size 2Θ(n) × 2Θ(n) is at least 2Ω(n).
■
3.5.5 n-player Game
Theorem 3.4
Theorem 3.2, restated. There exists a constant ϵ > 0 such that the communication complexity of (ϵ, ϵ)-weak approximate Nash equilibrium in n-player binary-action games is at least 2ϵn.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.