Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Algorithmic Game Theory:
TR08-077 | 23rd May 2008
Felix Brandt, Felix Fischer, Markus Holzer

On Iterated Dominance, Matrix Elimination, and Matched Paths

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

TR15-156 | 21st September 2015
Tim Roughgarden

Communication Complexity (for Algorithm Designers)

This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at
Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

ISSN 1433-8092 | Imprint