Timeline for Ticket lottery -- distributing $n$ tickets among $N$ people fairly
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 23, 2015 at 1:12 | comment | added | usul | I think the easiest approach is to take a uniformly random permutation of the groups, then give out tickets in this order until you run out of tickets. The extent to which this is a bad or non-random approach is essentially the extent to which you run into knapsack and boundary problems. So if you are assuming those effects are small, this should be fine. | |
| Feb 22, 2015 at 22:11 | comment | added | Dale | Ugh, yes $k = n$, which I've fixed in the text. The groups are disjoint. And of course, there is a "breakage" problem such as domotorp mentions -- part of the problem is to specify the degree we are willing to deviate from exact fairness so as to be able to deal with breakage. | |
| Feb 22, 2015 at 22:10 | history | edited | Dale | CC BY-SA 3.0 |
edited body
|
| Feb 22, 2015 at 19:58 | comment | added | domotorp | Do you want exactly $n/N$ chance of winning for each person? Then you definitely need more constraints. Imagine that $N$ is even, everyone is in a group of size two and $n$ is odd. | |
| Feb 22, 2015 at 19:52 | comment | added | domotorp | The groups are disjoint and $k=n$, right? | |
| Feb 22, 2015 at 16:59 | comment | added | Dale | I intend to avoid the knapsack problem by requiring the groups to be $<<N$ and allowing a small amount of inequality in chances near the beginning of the order, the end of the order, and the cut point $n$. | |
| Feb 22, 2015 at 3:17 | comment | added | Anthony Quas | A solution to this seems as though it should give a solution to the knapsack problem? | |
| Feb 22, 2015 at 2:10 | history | asked | Dale | CC BY-SA 3.0 |