All reports by Author Giovanni Resta:

__
TR06-012
| 17th January 2006
__

Bruno Codenotti, Mauro Leoncini, Giovanni Resta#### Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

__
TR97-043
| 25th September 1997
__

Bruno Codenotti, Pavel Pudlak, Giovanni Resta#### Some structural properties of low rank matrices related to computational complexity

Revisions: 1
,
Comments: 1

Bruno Codenotti, Mauro Leoncini, Giovanni Resta

It is known that finding a Nash equilibrium for win-lose bimatrix

games, i.e., two-player games where the players' payoffs are zero

and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash

equilibrium for win-lose bimatrix games where the number of winning

positions ...
more >>>

Bruno Codenotti, Pavel Pudlak, Giovanni Resta

We consider the conjecture stating that a matrix with rank

$o(n)$ and ones on the main diagonal must contain nonzero

entries on a $2\times 2$ submatrix with one entry on the main

diagonal. We show that a slightly stronger conjecture implies

that ...
more >>>