Skip to main content
MathOverflow

Return to Question

edited body
Source Link
Dale
Dale
  • 429
  • 2
  • 8

Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > k$$N > n$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend the event together or not at all, that is, there are a-priori declared groups whom either all will win or none will win. (To avoid edge problems, assume that the size of all groups is $<< n$.) We want the distribution to be "fair" in the sense that every person has the same probability of getting a ticket regardless of how people are grouped (or not).

It seems to me that an equivalent but simpler formulation is that we want to randomly put $N$ people in a linear order subject to the constraints (1) each person has a $1/N$ chance of being in any particular position in the order and (2) certain relatively small ($<< N$) groups must appear in consecutive positions of the order. Given a solution to this problem, we would allocate the $n$ tickets to the people in the first $n$ positions in the order. (Requiring special case handling if a group spans positions $n$ and $n+1$.)

Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > k$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend the event together or not at all, that is, there are a-priori declared groups whom either all will win or none will win. (To avoid edge problems, assume that the size of all groups is $<< n$.) We want the distribution to be "fair" in the sense that every person has the same probability of getting a ticket regardless of how people are grouped (or not).

It seems to me that an equivalent but simpler formulation is that we want to randomly put $N$ people in a linear order subject to the constraints (1) each person has a $1/N$ chance of being in any particular position in the order and (2) certain relatively small ($<< N$) groups must appear in consecutive positions of the order. Given a solution to this problem, we would allocate the $n$ tickets to the people in the first $n$ positions in the order. (Requiring special case handling if a group spans positions $n$ and $n+1$.)

Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > n$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend the event together or not at all, that is, there are a-priori declared groups whom either all will win or none will win. (To avoid edge problems, assume that the size of all groups is $<< n$.) We want the distribution to be "fair" in the sense that every person has the same probability of getting a ticket regardless of how people are grouped (or not).

It seems to me that an equivalent but simpler formulation is that we want to randomly put $N$ people in a linear order subject to the constraints (1) each person has a $1/N$ chance of being in any particular position in the order and (2) certain relatively small ($<< N$) groups must appear in consecutive positions of the order. Given a solution to this problem, we would allocate the $n$ tickets to the people in the first $n$ positions in the order. (Requiring special case handling if a group spans positions $n$ and $n+1$.)

Source Link
Dale
Dale
  • 429
  • 2
  • 8

Ticket lottery -- distributing $n$ tickets among $N$ people fairly

Suppose that I have $n$ tickets for an event that I want to distribute fairly among $N > k$ people. In this simple case, a lottery suffices. But suppose certain groups of people want to attend the event together or not at all, that is, there are a-priori declared groups whom either all will win or none will win. (To avoid edge problems, assume that the size of all groups is $<< n$.) We want the distribution to be "fair" in the sense that every person has the same probability of getting a ticket regardless of how people are grouped (or not).

It seems to me that an equivalent but simpler formulation is that we want to randomly put $N$ people in a linear order subject to the constraints (1) each person has a $1/N$ chance of being in any particular position in the order and (2) certain relatively small ($<< N$) groups must appear in consecutive positions of the order. Given a solution to this problem, we would allocate the $n$ tickets to the people in the first $n$ positions in the order. (Requiring special case handling if a group spans positions $n$ and $n+1$.)