This is an old revision of the document!
In a football match problem with n games there are n pairs of teams playing playing against one another. The outcome of every game is given by the numbers 0, 1, and 2, according to whether the game was a draw, whether the home team won, or whether the home team lost. It is possible to bet on the outcomes of these games. A series of n bets gives a win if at most 2 of the games in the series were predicted in error. The classical problem asks for the smallest number of bets such that, no matter the outcome, there is a winning bet.
This problem can be solved with coding theory. We can identify the possible outcomes of the games by a vector of length n over the field GF(3). The task is to find the smallest number of vectors (=bets) such that any vector in GF(3)^n (=outcome of the games) has Hamming distance at most 2 from a bet.
In this project we are interested in a soft version of this problem in which there are prior probabilities for the outcome of each game, and there is a confidence level, P; the task is to find the smallest number of bets such that, given the prior probabilities, with probability at most P none of the bets wins. The student should study optimization techniques for finding a good set of bets.
Contact: Harm Cronie
Room: BC 150
Tel: 021 6931205
Email: harm [dot] cronie [at] epfl [dot] ch