0
$\begingroup$

I'm trying to organize a raffle that has two prizes — prize X and prize Y:

  • the $N_X$ X-fans want prize X and don't want prize Y,

  • the $N_Y$ Y-fans want prize Y and don't want prize X,

  • the other $N_{XY}$ are the XY-fans who would be happy with any of the two prizes.

If a XY-fan would have a higher chance of winning than a X-fan, that seems unfair.

I want to know how to randomly choose the winners in such a way that:

  • is fair (everybody has the same chance of winning)
  • nobody receives a prize that they do not want
  • nobody receives two prizes
  • there are as many winners as possible*
  • their probabilities of winning are as high as possible*

(if there is a way, or maybe there might be more than one way)

*I think that in some cases (depending on $N_X$, $N_Y$ and $N_XY$) the solution (if there is one) might have a nonzero chance that one of the two prizes will not be given to anyone. For example if $N_X=9$, $N_Y=4$ and $N_{XY}=0$ then I think that each X-fan would have to have a $\frac{1}{9}$ chance of winning, and for it to be fair then each Y-fan would then have to also have a $\frac{1}{9}$ chance of winning, but then (since there are only 4 Y-fans) there would be a $\frac{5}{9}$ chance that nobody wins prize Y.

Perhaps it might be better to try to solve the more general problem with an arbitrary number of prizes instead of focusing on two prizes.

$\endgroup$
6
  • $\begingroup$ The constraint that everyone must have an equal chance of winning (some prize), and you're willing to potentially not award a prize in order to meet that constraint, is an interesting twist. Is there any real-world scenario that requires such a constraint? $\endgroup$
    – antkam
    Apr 21, 2021 at 18:41
  • 1
    $\begingroup$ If a XY-fan would have a higher chance of winning than a X-fan, that seems unfair. — Why? Please share your thoughts on what is fair to you. $\endgroup$ Apr 21, 2021 at 22:36
  • $\begingroup$ One example: X-fans are heterosexual, Y-fans are homosexual, XY-fans are bisexual. Some might argue that unequal chances of winning could be discrimination on the basis of sexual orientation. $\endgroup$ Apr 22, 2021 at 6:50
  • $\begingroup$ (but I still think it's a cool mathematical problem even without considering a real-world scenario) $\endgroup$ Apr 22, 2021 at 10:53
  • $\begingroup$ Try to use digraphs whose edges measure utility, or something like that. At the moment, you don't have a complete model. $\endgroup$ Apr 22, 2021 at 11:24

2 Answers 2

0
$\begingroup$

UPDATE: This is now a full solution

The interesting twist in this question is that everybody must have the same probability of winning (some prize). Let this probability be $p$, and we want to maximize $p$.

Without loss lets assume $N_X \ge N_Y$.

Case $1$: $N_X \ge N_Y + N_{XY}$.

  • $p = \frac{1}{N_X}$. Obviously no higher $p$ is possible.

  • First do a random draw to give away the X prize among the X-fans.

  • Next do a random draw to give away the Y prize among the Y-fans, the XY-fans, and $K$ number of dummy people where $K = N_X - N_Y - N_{XY}$. If a dummy person wins this draw, then the Y prize is not awarded.

Case $2a$: $N_X < N_Y + N_{XY}$ and $N_X + N_Y + N_{XY}$ is an even number, say $= 2D$.

  • $p = \frac{2}{N_X + N_Y + N_{XY}} = \frac{1}{D}$. Obviously, no higher $p$ is possible.

  • First randomly pick a $K$-subset of XY-fans to join the X-fans to create an X-pool. The rest of the XY-fans join the Y-fans to create a Y-pool. $K = D - N_X$ s.t. each pool has $D$ fans.

  • Do a random draw to award the X prize among the $D$ fans in the X-pool.

  • Do a random draw to award the Y prize among the $D$ fans in the Y-pool.

Case $2b$: $N_X < N_Y + N_{XY}$ and $N_X + N_Y + N_{XY}$ is an odd number, say $2D+1$.

  • I cannot find a simple solution to this, but I have a rather complicated solution below (which also works for 2a).

UPDATE: General solution for case 2b (which also works for case 2a)

The general solution for 2b (and 2a) works by listing all possible outcomes. An outcome is an assignment of who gets which prize. There are $4$ types of outcomes.

  • (type-a) X-fan gets X-prize, Y-fan gets Y-prize. There are $N_X N_Y$ such outcomes, and let $a$ be the probability of picking a specific such outcome.

  • (type-b) X-fan gets X-prize, XY-fan gets Y-prize. There are $N_X N_{XY}$ such outcomes, and let $b$ be the probability of picking a specific such outcome.

  • (type-c) XY-fan gets X-prize, Y-fan gets Y-prize. There are $N_{XY} N_Y$ such outcomes, and let $c$ be the probability of picking a specific such outcome.

  • (type-d) XY-fan gets X-prize, another XY-fan gets Y-prize. There are $N_{XY} (N_{XY} -1)$ such outcomes, and let $d$ be the probability of picking a specific such outcome. (Note that swapping prizes between two XY-fans are two different outcomes.)

So we have four unknowns. They satisfy four equations, so they can be solved. Here $p = \frac{2}{N_X + N_Y + N_{XY}} = $ an individual's win prob.

  • Total probability: $N_X N_Y a + N_X N_{XY} b + N_{XY} N_Y c + N_{XY} (N_{XY} -1) d = 1$

  • X-fan individual win prob: A specific X-fan has $N_Y$ type-a outcomes and $N_{XY}$ type-b outcomes where he/she wins. So: $N_Y a + N_{XY} b = p$.

  • Y-fan individual win prob: Similarly, a specific Y-fan has favorable type-a and type-c outcomes: $N_X a + N_{XY} c = p$.

  • XY-fan individual win prob: A specific XY-fan has favorable type-b, type-c, type-d outcomes. Note that there are $2 (N_{XY} - 1)$ favorable type-d outcomes for him/her (who he/she shares with, and which prize goes to him/her). So: $N_X b + N_Y c + 2(N_{XY} - 1) d = p$.

Once we solved for $a,b,c,d$, then simply draw one outcome among all four types, with these probabilities. E.g. pre-assign each outcome its own small non-overlapping range of the right length in the $(0,1)$ interval and then drawing from $Uniform(0,1)$.

$\endgroup$
7
  • $\begingroup$ Nice, case 1 and case 2a look good. Maybe a pool-based solution is not necessary for case 2b. I found a partial solution that works for at least some of case 2b, where both winners are picked together instead of in separate pools. $\endgroup$ Apr 24, 2021 at 8:59
  • $\begingroup$ @doubleclick - Here is a full solution. I am not happy with it coz it's so complicated :( but at least it works for case 2b. $\endgroup$
    – antkam
    Apr 24, 2021 at 17:03
  • $\begingroup$ Interesting, if I'm not mistaken then the four equations are not linearly independent and the solution still has one degree of freedom. For example for $N_X=N_Y=1$, $N_{XY}=3$ I found $a=6d-\frac{1}{5}$, $b=c=\frac{1}{5}-2d$ and $d$ is not fixed, with solutions ranging from $a=0,b=c=\frac{2}{15},d=\frac{1}{30}$ to $a=\frac{2}{5},b=0,c=0,d=\frac{1}{10}$ while still satisfying all the requirements. $\endgroup$ Apr 25, 2021 at 20:25
  • $\begingroup$ Huh, I didnt expect the linear dependence in that example! Well that means there are indeed many solutions to your problem for the $(1,1,3)$ case. You can easily check that both your quoted solutions satisfy all your requested criteria, so they're both valid. It'd be interesting to investigate when the equations are dependent -- e.g. only for $(1,1,3)$ and a few other cases? Only when $N_X = N_Y$? Always? -- But sadly I don't have time to check now. In any case, this does answer your original question. :) $\endgroup$
    – antkam
    Apr 26, 2021 at 11:35
  • $\begingroup$ FWIW, the $(N_X,N_Y,N_{XY}) = (1,2,3)$ case is linearly independent, with the unique solution $(a,b,c,d) = (1/6, 0, 1/18, 1/18)$ (assuming I didnt make any algebraic mistakes) $\endgroup$
    – antkam
    Apr 26, 2021 at 11:39
0
$\begingroup$

Another partial solution

The partial solution by antkam works for most cases. I focused on simple cases for which it doesn't work (such as $N_X=1$, $N_Y=1$, $N_{XY}=1$ or $N_X=1$, $N_Y=0$, $N_{XY}=2$) and found a partial solution for some (but not for most) of the remaining cases.

Case $N_X \leq 1$ and $N_Y \leq 1$ (no extra restrictions on $N_{XY}$)

  • Pick two winners with everybody having a probability $\frac{2}{N_X + N_Y + N_{XY}}$ of winning.
  • There are up to 4 possible outcomes for the two winners in this case
  1. 1 X-fan and 1 Y-fan: Give prize X to the X-fan and prize Y to the Y-fan.
  2. 1 X-fan and 1 XY-fan: Give prize X to the X-fan and prize Y to the XY-fan.
  3. 1 XY-fan and 1 Y-fan: Give prize X to the XY-fan and prize Y to the Y-fan.
  4. 2 XY-fans: flip a coin to decice who gets which prize.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.