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


1. BR claims an unclaimed edge from $E$, adds it to $B$
2. MA claims an unclaimed edge from $E$, adds to $M$
3. 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?



Graph game minimum vertex degree
I would try the following. Every time breaker plays an edge, maker chooses an endpoint of that edge at random and plays any available edge at that vertex. Since the vertex degrees are much bigger than $\log n$, each vertex should be chosen by maker about half the number of times it gets used by breaker, so maker should achieve about $1/3$ of the available degree at each vertex. The times maker is forced to deviate from this strategy because there are no edges available will be swallowed by the $\epsilon$.


Two clarifications following the comments: 


*Maker's extra degree at other vertices*. Treat this like you would the bonus move you get in a strategy stealing argument. We don't count the bonus degree towards our total at any vertex, and if our strategy ever tells us to play at a vertex where we've built up some bonus degree then we spend that and move arbitrarily (building up bonus degree at some two vertices). This handles the problem that arises if our strategy tells us to play at a vertex but we can't because we've already amassed too much bonus degree there.


*Why do we need the vertex degrees to be large?* In expectation we get to play at each vertex half as often as breaker. To say that this is in fact the typical behaviour we use a Chernoff inequality to say that the probability of differing from the expectation by a factor of more than $\epsilon$ at a vertex $v$ is bounded by an expression like $e^{-\epsilon^2d(v)}$, which tends to zero faster than $1/n$ (which is what we need to take a union bound over all $n$ vertices) provided that $d(v)$ is large enough compared to $\log n$.


