Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
Newsletter: @DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - November 18
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - November 18
Event date: Friday, November 18, 2011, at 11:10 AM
Location: BA1240
SPEAKER: Per Austrin
Department of Computer Science
University of Toronto
TITLE: Inapproximability of NP-Complete variants of Nash equilibrium
ABSTRACT:
In recent work of Hazan and Krauthgamer it was shown that finding an epsilon-approximate Nash equilibrium with near-optimal value is as hard as finding a planted clique of size O(log n) in the random graph G(n,1/2). This raises the question of whether a similar intractability holds for finding an arbitrary approximate equilibrium. We give evidence that adding constraints such as near-optimal value makes the problem distinctly harder. This evidence comes in two forms:
1. We show that maximum value Nash is only one of several NP-hard problems related to Nash equilibrium which have approximate variants which are as hard as planted clique.
2. We show that, unlike for arbitrary Nash, we cannot improve upon a simple 1/2-equilibrium algorithm for these problems (again assuming hardness of planted clique).
This is joint work with Mark Braverman and Eden Chlamtac.