\documentclass{article} \usepackage{wide} \parindent0pt

### 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.
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 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.
Yao's minimax method:
• 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.

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

• 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
• 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.
Time Analysis:
• 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
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$.

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)$