Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ \gg \log(n)$. Players are BR and MA (BR moves first):
- BR claims an unclaimed edge from $E$, adds it to $B$
- MA claims an unclaimed edge from $E$, adds to $M$
- Repeat
MA wins if for all edges (with corresponding vertices $v$ from $V$) in $M$ fulfills $\deg_M(v) \geq (1-\epsilon)\cdot 1/3 \cdot \deg_G(v)$, for some $\epsilon > 0$.
I would like to show that there exists a winning strategy for MA.
In order to do that I would have to assume BR is playing optimally. I'm guessing I need to figure out what that strategy is before I can start proving $Pr[\exists \text{winning strategy}]>0$. Any ideas?