Bachelor´s Degree Project Presentation: Efficient sampling of solutions to a system of linear inequalities in the game GOALS

Abstract: In this work, two algorithms for generating players in the football game GOALS are proposed and compared. The players are generated to fulfill constraints in a 31-dimensional attribute space, as well as requirements on the distribution of the generated players.

The problem is to find a mathematical description of the problem and a solution technique so that players can be generated from a uniform distribution on the space of all possible solutions. The space of points satisfying the constraints is interpreted as the intersection of a convex polytope and a hyperplane. This is then transformed to a convex polytope in 30-dimensions where the algorithms are applied, and it is shown that reversing this transformation preserves the uniform distribution and yields points satisfying all constraints.

We apply two Markov Chain Monte Carlo techniques for sampling in the convex polytope: Hit-and-run and Vaidya Walk. The samples (X0, . . . , Xn) generated by these algorithms approach a uniform distribution for large n, but the variables Xi and Xi+1 are highly correlated. We want low correlation between successive samples and to achieve this we utilize thinning. The algorithms are compared based on autocorrelation, trace plots to detect non-random patterns and the runtime of the algorithms. It is shown that Hit-and-run has better characteristics for this problem and as such is the preferred algorithm.