Two combinatorial problems involving lottery schemes: Algorithmic determination of solution sets

Abstract

Suppose a lottery scheme consists of randomly selecting a winning n-set from a universal m-set, while a player participates in the scheme by purchasing a playing set of any number of n-sets from the universal set prior to the winning draw, and is awarded a prize if k (or more) elements in the winning n-set match those of at least one of the player's n-sets in his playing set (1 ≤ k ≤ n ≤ m). Such a prize is called a k-prize. The player may wish to construct a smallest playing set for which the probability of winning a k-prize is at least ψ (0 < ψ ≤ 1), no matter which winning n-set is chosen from the universal set. Alternatively, the player might only be able to purchase a playing set of cardinality ℓ, in which case he may wish to construct his playing set so as to maximise his chances of winning a k-prize. In this paper these two combinatorial optimisation problems are considered. The aim of the paper is twofold: (i) to derive growth properties of and establish bounds on solutions to these problems analytically, and (ii) to develop a number of algorithmic approaches toward finding respectively upper and lower bounds on the solutions to these problems numerically.