Computation Theory (TOCT)


Search Issue
enter search term and/or author name


ACM Transactions on Computation Theory (TOCT), Volume 4 Issue 2, May 2012

The Computational Complexity of Nash Equilibria in Concisely Represented Games
Grant R. Schoenebeck, Salil Vadhan
Article No.: 4
DOI: 10.1145/2189778.2189779

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...

Complexity Theory for Operators in Analysis
Akitoshi Kawamura, Stephen Cook
Article No.: 5
DOI: 10.1145/2189778.2189780

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
DOI: 10.1145/2189778.2189781

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...