DominikPeters

A collection of some counterexamples I've found for
fair allocation of indivisible goods, mostly via random sampling.

DominikPeters

# Indivisible private goods, maximum Nash welfare
# Using Gurobi, this implements the ILP formulation from
# Caragiannis, Ioannis, et al. 
# "The unreasonable fairness of maximum Nash welfare." 
# ACM Transactions on Economics and Computation (TEAC) 7.3 (2019): 1-32.

from gurobipy import *
import math
import random

DominikPeters

# for two permutations of [0,1,...,n], compute how many swaps (not necessarily adjacent)
# are needed to transform one into the other
# code uses: distance of a permutation from the identity permutation
# equals n - #cycles in the cycle notation of the permutation

def cayley_distance(x,y):
    A = range(len(x))
    inv_y = tuple(y.index(a) for a in A)
    comp = tuple(x[inv_y[a]] for a in A)
    cycles = 0

DominikPeters

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