# Problem

Consider a race between at least $N$ runners from at most $K$ countries.

Each country that wishes to participate agrees to submit to the race committee a roster containing the number of runners that will participate along with an amount $1,000,000 * $q$ (where $q \in [0, 1]$) the country will donate to charity for each of its runners that finish in the top $N$ runners. Assuming that all possible race standings are equally likely, find the countries that should participate in the race so that the most money is donated to charity. # Outline Ultimately, we’ll use linear-fractional 0-1 programming to optimize this problem, but we’ll start with a description of the dynamics of the race. Then we’ll show the brute force approach to solving the problem in order to supply a baseline for both speed correctness. Along the way, we’ll develop an intuition why linear-fractional 0-1 programming is applicable in solving the problem. # Prerequisites For a given race, we can determine the outcomes by creating runner / country pairs, and looking at the country breakdowns of the $N$combinations of the runner / country pairs. Because payments to charity do not depend on which specific runners from a country finish in the top, we can disregard the complexity of looking at $N$permutations. For each $N$–combination, determining the country breakdown tells the amount of money that would be donated to charity. The expected payment to charity is computed by averaging over the possible outcomes. ## Expectation of $q$ for a given race exp_q_finishers returns the expected sum or average $q$ values of the top finishers (depending on the value of avg_q), given the countries participating in the race. In addition to the $q$ value, the function also returns a map of the different finishes from a country perspective (counts rather than individual runners). The astute reader will note that the values in the returned country_finishes map follow an unnormalized multivariate hypergeometric distribution, which can be verified by dividing each value (count) by the sum of values and comparing the probabilities to the multivariate hypergeometric distribution probability mass function. We can also run the keys in country_finishes through the multivariate hypergeometric distribution PMF to verify the probabilities sum to one, which is an indication the returned race finishes represent the comprehensive set of possible finishes. To see this in action, consider the following example. ### Example 1 Consider the race between the following three countries where the top $t$ = 11 finishers of the $p$ = 13 participants will have a charitable donation in their name with the amount dictated by the $q$ value for a runner’s country of origin. country # runners $q$ Algeria 5 0.5 Morocco 5 0.5 United Kingdom 3 0.31 There are 3,113,510,400 $= nPr(p, t)$ $= nPr(13, 11)$ $= \frac{ 13! }{ (13-11)! }$ unique race finishes for the top 11 finishers of this race. Again, individual race ordering does not matter since the problem is only concerned with the number of finishers from each country in the top 11. Therefore, combinations rather than permutations are appropriate. There are then $n = 78$ $= nCr(p, t) = nCr(13, 11)$ $= \frac{ 13! }{ 11! (13-11)! }$ unique finishes when order within the top 11 runners does not matter. If we let $% $ and $% $, and inspect the results of exp_q_finishers(r, q, t), we get the unique finishes, $F$, and the number of times each finish occurs in $C$. Note that the column vectors in $F$ represent a unique race outcome and therefore each column in $F$ sums to $t$ since there are $t$ top finishers. Notice: and These are important results because $t$, $p$ and $r$ are parts of the race definition, which tells us that we don’t actually need to simulate the possible races to determine the expected number of runners from each country that will finish in the top $t$. Determining the expected charitable donation for the race is just$1,000,000 times:

or $5,017,692.31 or about$456,153.85 per the 11 finishers.

## Brute force optimization of the problem

exp_q_finishers determines the expected sum of $q$ values for the top finishers, given set of countries entered into a race. brute_force_best, defined below, can be used optimize the objective in a brute force way by applying exp_q_finishers to each valid country combination and finding the one with the highest value for exp_q_finishers. This is rather straightforward and can be done as follows:

### Example 2

Find at most $K$ = 3 countries (from the list below) to participate in a race with at least $N$ = 11 runners, where the top $t$ = 11 runners’ countries will make a charitable donation according to the country’s $q$ value.

country # runners $q$
Algeria 5 0.5
Morocco 5 0.5
Tanzania 4 0.32
United Kingdom 3 0.31

By looking at the “# runners” column, it is apparent that 3 countries are required to fill out the race. So, the possible races (i.e., country combinations), along with their expected donation following the race and average donation per finisher are listed below.

# Conclusion

Linear-fractional 0-1 programming can be used to optimize grouped races where the objective is to maximize some definition of quality for the quickest finishers. In the examples above, the definition of quality is the size of charitable donations, but this same problem has applications in advertising. For instance, if an advertising budget allows for $N$ impressions over at most $K$ distinct placements, then placement quality over all potential placements could be optimized using the above formulation.

Thinking about the brute force search over the $N$–permutations representing all of the possible race finishes, the linear-fractional 0-1 programming formulation gives a good speed up. Further refinements are likely possible and some of those possible improvements are likely to be found in some of the references that follow.