Csdrhrt

I have to divide holiday shifts at work into a group of 8, both AM and PM shifts need to be covered (we rotate between both AM & PM). A total of 24 holiday shifts with 3 major holidays (New Years, Thanksgiving, Christmas). I want to do a lottery system where everyone draws a number and then chooses the holiday shift they want to work the most, rotating through until none are left of the 24 shifts. Plan was to have them draw out of a hat 1-8. First round, #1 has first pick down to #8. Then for second round reverse the order, #8 being first pick down to #1. Problem is the third round. What is a fair system so most everyone will get a fair chance at choosing near the top of the list? Thanks so much!

It depends on exactly what is meant by fairness. But in the two iteration case, the key idea is that the total number (that is, the sum) of the number of slots taken away from each person on each go is the same. So in the two iteration case, each person gets a total of 15 slots taken away from them, with the first person getting 0 slots and then 15 slots, the second person getting 1 slot then 14 slots, and so on. And if we notice the number of slots taken away from a work picking in the $n$-th position is just $n-1$, then since each worker picks the same number of slots it's clear that a fair division is simply a division where the sum of the picking positions of each worker is the same for all workers. Since the picking positions are ${1,2,3,...24}$ we're looking to partition ${1,2,3,...,24}$ into eight sets of $3$, all of equal sum.

Now, instinctively it seems best to try and do something as you have above, and set it up so that each worker goes one time in each range of one third of picking positions $(1,8)$, $(9, 16)$, and $(17, 24)$, with the additional principle that no one picks again until everyone has gone on the current pick. This is a nice idea, and it's clear that since each person will go once in each range, it suffices to consider the sum of the positions relative to the range. So this would be formally equivalent to partitioning, ${ 1, 2, 3, ..., 8} times { 1, 2, 3, ..., 8} times { 1, 2,3, ..., 8}$ into 8 sets of 3 all of equal sum, with one from each subset. The trouble with that is that the total sum is

$$3sum_{i=1}^8 i = 3 frac{(8)(9)}{2} = 108 $$

see the problem? It's not divisible by $8$, so it can't be divided equally into eight numbers, and so in particular it can't be divided equally amongst the sums of each of the triples.

Even if you're willing to let go of this principle that everyone goes this time before someone goes again, this issue doesn't goes away, since in the full problem the sum is

$$sum_{i=1}^{24} i = frac{(24)(25)}{2} = 300 $$

which is still not divisible by $8$.

And so we see the fairest version of the problem is fundamentally impossible. So, we can't have it exactly fair. And since we're moving to an approximation, we might as well ditch the ${1,2,..., 24}$ approximation of the utilities of each pick. Instead, it's best to say the utilities are, say, normally distributed with mean $mu$ and standard deviation $sigma$. (It's best to think of $mu$ here as fairly negative, with a $sigma$ pretty small compared to the absolute value of $mu$. Because ideally, we don't want to have to artificially impose a distribution with the same number of workdays. Indeed, everyone works the same number of workdays, ideally, because it's fairest--even the best two shifts together should still be worse than the worst shift.

So, yeah, the problem is basically, given a set of $24$ utilities (for instance evenly and normally distributed, but possibly the set ${1,2,..., 24 }$, how can we best partition this set into $8$ subsets to minimize the range of total utility. That is, we want to minimize the maximum difference between any two workers.

Though this is still a problem that is in nature mathematical, and there may be very clever approaches, nowadays it could be reasonably considered to do with computation. (If you wanted to, say, look at the problem by hand you could consider partitioning ${1,2,..., 24 }$ or ${ 1, 2, 3, ..., 8} times { 1, 2, 3, ..., 8} times { 1, 2,3, ..., 8}$ into 8 sets of three so that half of them sum to 37 and 38, or half to 14 and 15, respectively, and that's as good as you can do. It hasn't been fast enough to run on my computer, but I've put together some brute force Python code that hasn't run on my computer in 10 minutes yet, but might, say, run in a day. (Note, that cited in the code is that the partitions algorithm is taken from tack Overflow).

So, I didn't get as far as an answer, which may be a bit disappointing, but hopefully you understand what precisely your problem is and how to (approximately, of course) solve it.

(A statistical sidenote: It is clear, that the expected value of total utility of each worker will be fixed as long as your method is random, and in that sense your method will always be fair, but I've assumed here you want to minimize your range. Maybe you don't. Maybe you prefer to minimize, say, your standard deviation (thought range makes the most sense to me). In that case your problem changes, but in any case you'll eventually find the best distribution of triples (or partitions, if you do think there is enough utility disparity to warrant one shift being equivalent to multiple, though this again seems unlikely), and then assign each person a triple randomly).

from scipy.stats import norm



mu = -80

sigma = 10

shifts = 24

workers = 8



def genUtilities(numShifts, m, s):

    mult = 1/(numShifts + 1)

    utils = 

    for i in range(1, numShifts + 1):

        utils.append(norm.ppf(mult*i) * s + m)

    return utils



# Code from Stack Overflow https://stackoverflow.com/questions/18353280/iterator-over-all-partitions-into-k-groups

def clusters(l, K):

    if l:

        prev = None

        for t in clusters(l[1:], K):

            tup = sorted(t)

            if tup != prev:

                prev = tup

                for i in range(K):

                    yield tup[:i] + [[l[0]] + tup[i],] + tup[i+1:]

    else:

        yield [ for _ in range(K)]



def neclusters(l, K):

    for c in clusters(l, K):

        if all(x for x in c): yield c



def getBestDistribution(utils, numWorkers):

    def getRange(part):

        tots = 

        for i in range(0, len(part)):

            tots.append(sum(part[i]))

        return max(tots) - min(tots)

    bestRange = None

    bestPart = 

    for part in neclusters(utils, numWorkers):

        curPart = part

        curRange = getRange(curPart)

        if bestRange is None or curRange < bestRange:

            bestRange = curRange

            bestPart = curPart

    return bestPart



def getRes(part, utils):

    res = 

    for workingPerson in part:

        listOshifts = 

        for shiftUtil in workingPerson:

            listOshifts.append(1+utils.index(shiftUtil))

        res.append(listOshifts)

    return res



#utilities = genUtilities(shifts, mu, sigma)

utilities = range(1, 25)

ans = getRes(getBestDistribution(utilities, workers), utilities)



print(ans)

Solution

I optimized the above code for the specific case of Utilities ${1,2,...,24}$ with the principle that no one picks again before everyone has picked this round. If you want source I can provide it, but I think it doesn't help all that much, so I might as well avoid cluttering up the answer with it. The idea is that instead of checking all $$ sum_{i=0}^{24} left { begin{array} 24 \ i end{array}right } = 120582710957928740 $$ partitions as the code does, or even checking all $$left { begin{array} 24 \ 8 end{array} right } = 82318282158320505 $$ possible partitions, we fix the first 8, go through all $$8! cdot {8 choose 4} = 2822400$$ ways to have the next eight numbers go, and check for repeats if the four chosen people have a sum 14 and the next four 13. So, in this case, the code runs almost instantly. And gives us a result. So, I'll list one way to do it here. All the sums are 37 and 38, and so if we want to, as we set out to do initial distribute the number of total spots taken as equally as possible, since the range is one, it's clear this is the best you can do. So, the way to go is as follows. I will put the responses in the form $$ text{Person p: Ai, Bj, Ck}$$ which means the person who draws randomly position $p$ should go $i$-th in the first round of choosings, $j$-th in the second round of choosing, and $k$-th in the third round. And, I should state that though I don't know the answer for the general normal utilities, this is quite probably the very best you can do.

$$ text{Person 1: A1, B8, C4}$$
$$ text{Person 2: A2, B6, C5}$$
$$ text{Person 3: A3, B5, C6}$$
$$ text{Person 4: A4, B2, C7}$$
$$ text{Person 5: A5, B1, C8}$$
$$ text{Person 6: A6, B7, C1}$$
$$ text{Person 7: A7, B4, C3}$$
$$ text{Person 8: A8, B3, C2}$$

So the rounds look like

$$text{Round A: 1,2,3,4,5,6,7,8} $$
$$ text{Round B: 5,4,8,7,3,2,6,1} $$
$$ text{Round C: 6, 8, 7, 1,2,3,4,5 }$$

Note that the sums after two rounds are rather different, and this must be, since the total sums can be nearly the same, if the total sums after two rounds are the same, then there are only 2 third sums to get to 13 and 14, and that's a problem. But have people go in that order, and you're being, roughly speaking, as fair as possible. Though it is slightly better to be any of people 1,2, 4 or 8. (I didn't plan that, but it's slightly better to be a power of 2).