New answers tagged

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 ...
user avatar
  • 7,042
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 $\...
user avatar

Top 50 recent answers are included