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, Charles.
- Payoff Matrix $M$. Entries are (large) strategies. chess.
- 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}$.
- if solution exists, knowing opponent's strategy useless.
- Sometimes, no solution using these pure strategies
- 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.
- 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
- 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!
- Worst case expected runtime of randomized algorithm for any input equals best case 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
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 Marriage
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 men arbitrarily
- lowest unmarried man proposes in order of preference
- woman accepts if unmarried or prefers new proposal to current mate.
- woman's state only improves with time
- only $n$ improvements per woman
- while unattached man, proposals continue
- (some woman available, since every woman he proposed to is married now)
- must eventually all be attached
- suppose $X$ and $y$ are dissatisfied with final pairing $X$-$x$, $Y$-$y$.
- $X$ proposed to $y$ first
- $y$ prefers current $Y$ to $X$.
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.
- use for discussing autopartition, quicksort
- Proposal algorithm:
- defered decision: each proposal is random among unchosen women
- still hard
- Each proposal among all women
- 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 women get a proposal.
- at each step $1/n$ chance women gets proposal
- This is just coupon collection: $O(n\log n)$