Yao's Minimax Principle

How do we know our randomized algorithm is best possible?

Review tree evaluation.

Lower Bound

Game Theory

• Zero sum games. Scissors Paper Stone. Roberta, Colin.
• Payoff Matrix $M$. Entries are (large) strategies. chess.

Optimal strategies

• row wants to maximize, column to minimze
• suppose Roberta picks $i$. Guarantees $\min_j M_{ij}$.
• (Pessimistic) $R$-optimal strategy: choose $i$ to $\max_i \min_j M_{ij}$.
• (Pessimistic) $C$-optimal strategy: choose $j$ to $\min_j \max_i M_{ij}$.

When $C$-optimal and $R$ optimal strategies match, gives equilibrium solution of game.

• if solution exists, knowing opponent's strategy useless.
• Sometimes, no solution using these pure strategies

Randomization:

• mixed strategy: distribution over pure ones
• $R$ uses dist $p$, $C$ uses dist $q$, expected payoff $p^TMq$
• Von Neumann: \[ \max_p \min_q p^T M q = \min_q \max_p p^T M q \] that is, always exists solution in mixed strategies.
• Once $p$ fixed, exists optimal pure $q$, and vice versa
• Why? Because $Mq$ is a vector with a maximum in one coordinate.
• Conclusion: equilibrium can be achieved even if only one player has a randomized strategy; other strategy can be deterministic
• (But, deterministic strategy must be unknown)

Yao's minimax derivation:

• Framing
  • In practice our algorithms make a sequence of random choices.
  • In theory, often easier to consider a randomized algorithm as a distribution over deterministic ones
• Column strategies algorithms, row strategies inputs
• payoff is running time (LV algorithm)
• randomized algorithm is mixed strategy
• optimum algorithm is optimum randomized strategy
• worst case input is corresponding optimum pure strategy
• Thus:
  • worst case expected runtime of optimum rand. algorithm
  • is payoff of game
  • instead, consider randomized inputs
  • payoff of game via optimum pure strategy
  • which is detemrinistic algorithm!

Yao's minimal principle:

• Worst-case input expected runtime of randomized algorithm equals best achievable expected running time of a deterministic algorithm for worst distribution of inputs.
• Thus, for lower bound on runtime, show an input distribution with no good deterministic algorithm

Game tree evaluation lower bound.

• Recall Yao's minimax principle.
• input distribution: each leaf loss with probability $p=\frac12(3-\sqrt{5})$, win with probability $1-p=\frac12(\sqrt{5}-1)$.
• $p$ chosen so that every node is a loss with probability $p$.
• $p = \Pr[L] = \Pr[\mbox{both children win}] = (1-p)^2$
• $p^2-3p+1=0$, so $p=(3-\sqrt{5})/2$
• lemma [Tarsi 1983]: for this distribution, any deterministic alg should finish evaluating one child of a node before doing other:
  • depth first pruning algorithm.
  • proof by induction.
• let $T(h)$ be expected number of leaves evaluated from height $h$.
• with probablity $p$, eval one (losing) child. else eval $2$.
• So \[ T(h) = pT(h-1)+2(1-p)T(h-1) = (2-p)^h = n^{0.694} \]
• Better bound:
  • build recursively from root,
  • where each winning node has (at random) one winning and one losing child.
  • shows our upper bound of $\frac14(1+\sqrt{33})^h$ is tight.

Adversary Models

Note that in discussion above, “who moves first” is important

• We assume input is provided and then we make random choices
• If we make random choices (get advice string) first, and adversary knows it, then to him we are a deterministic algorithm
• So deterministic lower bounds apply

Various adversary models

• Oblivious adversary: provides input without any dependence on our randomization
• This is the common model for randomized algorithms
• Some algorithms operate over time, with sequences of operations
  • e.g. online algorithms
  • or data structures with sequences of insert/delete
• In this setting, it is plausible for our behavior so far to “reveal” some aspects of our random choices
  • e.g., how long various data structure operations take
  • might influence what adversary requests next
  • even if they aren't adversarily chosen
  • in such settings, partially adaptive adversary can base choices on past state of algorithm but not on future.

Coupon collecting.

Practice with linearity of expectation.

• $n$ coupon types. Get a random one each round. How long to get all coupons?
• general example of waiting for combinations of events to happen.
• expected case analysis:
  • after get $k$ coupons, each sample has $1-k/n$ chance for new coupon
  • so wait for $(k+1)^{st}$ coupon has geometric distribution.
  • expected value of geo dist w/param $p$ is $1/p$
  • so get harmonic sum
  • what standard tools did we use? using conditional expectation to study on phase; used linearity of expectation to add
  • expected time for all coupons: $n \ln n + O(n)$.

Stable Matching

Problem:

• bipartite graph
• want to create matching
• complete preference lists
• stable if no two unmatched (to each other) entities prefer each other.
• traditionally framed as marriage story (heteronormative, but nonbipartite more complicated)
• real application: med school
• http://fivethirtyeight.com/features/another-34000-people-are-about-to-put-their-future-in-the-hands-of-an-algorithm/
• always exists (in bipartite case).

Proof by proposal algorithm:

• rank students arbitrarily
• lowest unmatched student proposes in order of preference
• school accepts if unmatched or prefers new proposal to current match.

Time Analysis:

• school state only improves with time
• matched schools stay matched
• only $n$ improvements per school
• while unattached student, proposals continue
• (some school available, since every school proposed to is matched now)
• must eventually all be matched

Stability of final solution

• suppose $X$ and $y$ are dissatisfied with final pairing $X$-$x$, $Y$-$y$.
• $X$ proposed to $y$ first
• $y$ prefers current $Y$ to $X$.

Optimality

• Note: resultaing matching is optimal (for certain definition) for students, pessimal for schools.
• If schools propose, optimality flips to schools
• They do it this way because it matters more to the students.
• surprisingly humane!
• much deep work on other notions of fairness to both sides

Average case analysis

• nonstandard for our course
• random preference lists
• how many proposals?
• principle of deferred decisions
  • used intuitively already
  • random choices all made in advance
  • same as random choices made when algorithm needs them.
  • “random advice string” is same as “make random choices when needed”
• use for discussing autopartition, quicksort

Proposal algorithm analysis:

• defered decision: each proposal is random among unchosen schools
• still hard
• Each proposal among all schools
• stochastic domination: $X$ s.d. $Y$ when $\Pr[X>z] \ge \Pr[Y>z]$ for all $z$.
• Result: $E[X] \ge E[Y]$.
• done when all schools get a proposal.
• at each step $1/n$ chance given school gets proposal
• This is just coupon collection: $O(n\log n)$