New answers tagged gt.game-theory
2
votes
Trying to understand the intuition behind Yao's Minimax Principle
It seems worth it to write up the "game" answer.
You are playing a game where you choose an algorithm $A$ and your opponent chooses an input $I$. You want to minimize $C(I,A)$.
First suppose ...
5
votes
Accepted
Trying to understand the intuition behind Yao's Minimax Principle
$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$Let $ {\mathcal I } $ be the collection of possible inputs, endowed with a $\...
Top 50 recent answers are included
Related Tags
gt.game-theory × 107cc.complexity-theory × 19
combinatorial-game-theory × 15
ds.algorithms × 13
reference-request × 11
board-games × 6
graph-theory × 5
complexity-classes × 5
mechanism-design × 5
graph-algorithms × 4
co.combinatorics × 4
machine-learning × 4
cr.crypto-security × 4
nash-equilibrium × 4
np-hardness × 3
lower-bounds × 3
pr.probability × 3
linear-programming × 3
it.information-theory × 3
quantum-information × 3
ai.artificial-intel × 3
interactive-proofs × 3
social-sciences × 3
evolutionary-game-theory × 3
lo.logic × 2