enter search term and/or author name
The Computational Complexity of Nash Equilibria in Concisely Represented Games
Grant R. Schoenebeck, Salil Vadhan
Article No.: 4
Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly...
We propose an extension of the framework for discussing the computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that can be represented only through approximation. The key idea is to...
Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
Paolo Penna, Carmine Ventre
Article No.: 6
A truthful mechanism consists of an algorithm augmented with a suitable payment function that guarantees that the players cannot improve their utilities by cheating. Mechanism design approaches are particularly appealing for designing...