Game-Theoretic Techniques

Rajeev Motwani, Prabhakar RaghavanCambridge 1995 · DOI · OpenAlex

Abstract

IN this chapter we study several ideas that are basic to the design and analysis of randomized algorithms. All the topics in this chapter share a game-theoretic viewpoint, which enables us to think of a randomized algorithm as a probability distribution on deterministic algorithms. This leads to the Yao ‘s Minimax Principle, which can be used to establish a lower bound on the performance of a randomized algorithm.
BibTeX
@inproceedings{motwani1995game,
  author = {Rajeev Motwani and Prabhakar Raghavan},
  title = {{Game-Theoretic Techniques}},
  booktitle = {Cambridge},
  year = {1995},
  doi = {10.1017/cbo9780511814075.003},
}

Loading related content...

Figure