\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


Proof by proposal algorithm:

Time Analysis: Stability of final solution

Average case analysis