Simple implementation of the Probabilistic Serial fair division mechanism

probabilistic_serial.py

from fractions import Fraction

def probabilistic_serial(profile):
    "input is a list of preference lists"
    N = range(len(profile)) # agents
    O = range(len(profile[0])) # items
    supply = {o : Fraction(1,1) for o in O}
    allocation = {(i,o) : Fraction(0,1) for i in N for o in O}
    while any(supply.values()):
        # in each iteration, at least one remaining item is fully depleted
        eating = {}
        eaters = {o : 0 for o in O} # number of agents eating each item
        for i in N:
            o_ = next((o for o in profile[i] if supply[o]))
            eating[i] = o_
            eaters[o_] += 1
        # how much time until the first remaining item is depleted
        time = min(supply[o] / eaters[o] for o in O if supply[o] and eaters[o])
        for i in N:
            allocation[i,eating[i]] += time
            supply[eating[i]] -= time
    return allocation
    
# example from https://en.wikipedia.org/w/index.php?title=Probabilistic-serial_procedure&oldid=915874133#Example
allocation = probabilistic_serial([[0,1,2,3],[0,1,2,3],[1,0,3,2],[1,0,3,2]])
for i in range(4):
    print(str(i) + ": " + ", ".join([str(float(allocation[i,o])) for o in range(4)]))
# produces
# 0: 0.5, 0.0, 0.5, 0.0
# 1: 0.5, 0.0, 0.5, 0.0
# 2: 0.0, 0.5, 0.0, 0.5
# 3: 0.0, 0.5, 0.0, 0.5