\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac2{{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Noga Alon, Michael Krivelevich, Joel Spencer and Tibor Szab\'o}
%
%
\medskip
\noindent
%
%
{\bf Discrepancy Games}
%
%
\vskip 5mm
\noindent
%
%
%
%
We investigate a game played on a hypergraph $H=(V,E)$ by two players,
Balancer and Unbalancer. They select one element of the vertex set $V$
alternately until all vertices are selected. Balancer wins if at the
end of the game all edges $e\in E$ are roughly equally distributed
between the two players. We give a polynomial time algorithm for
Balancer to win provided the allowed deviation is large enough.  In
particular, it follows from our result that if $H$ is $n$-uniform and
has $m$ edges, then Balancer can achieve having between
$n/2-\sqrt{\ln(2m)n/2}$ and $n/2+\sqrt{\ln(2m)n/2}$ of his vertices on
every edge $e$ of $H$.  We also discuss applications in positional
game theory.

\bye

.