| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9657779 | Theoretical Computer Science | 2005 | 25 Pages |
Abstract
Considering pure Nash equilibria, we provide a PTAS to approximate the best social cost, we give an upper bound on the worst social cost and we show that it is NP-hard to approximate the worst social cost within a multiplicative factor better than 2-2/(m+1).
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
M. Gairing, T. Lücking, M. Mavronicolas, B. Monien, P. Spirakis,