ON SPARSE APPROXIMATIONS TO RANDOMIZED STRATEGIES AND CONVEX COMBINATIONS

A randomized strategy or a convex combination may be represented by a probability vector p = (p1,..., p(m)). p is called sparse if it has fe w positive entries. This paper presents an approximation lemma and app lies it to matrix games, linear programming, computer chess, and unifo rm sampling spaces. In all cases arbitrary probability vectors can be replaced by sparse ones with only logarithmically many positive entrie s) without losing too much performance.