דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Inapproximability of Nash Equilibrium
event speaker icon
אביעד רובינשטיין (אונ' ברקלי)
event date icon
יום רביעי, 24.12.2014, 12:30
event location icon
טאוב 401
We prove that finding an epsilon-approximate Nash equilibrium is PPAD-complete for constant epsilon and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete information game with a constant number of actions, for market equilibrium in a non-monotone market, for the generalized circuit problem defined in [Chen, Deng, Teng, 2009], and for approximate competitive equilibrium from equal incomes with indivisible goods.
[בחזרה לאינדקס האירועים]