\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

Optimal strategies When $C$-optimal and $R$ optimal strategies match, gives solution of game. Randomization: Yao's minimax method:

Game tree evaluation lower bound.

Adversary Models

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

Various adversary models

Coupon collecting.

Practice with linearity of expectation.

Stable Marriage

Problem:

Proof by proposal algorithm:

Time Analysis: Stability of final solution

Average case analysis