Maximize Nash welfare for allocating indivisible goods

nash_indivisible.py

# 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

N = range(4) # agents
O = range(6) # items

# valuations
v = {(i,o) : random.randint(0,6) for i in N for o in O}

m = Model()
x = m.addVars(N, O, vtype=GRB.BINARY)
# x describes an allocation
m.addConstrs(quicksum(x[i,o] for i in N) == 1 for o in O)
W = m.addVars(N) # log utility
for i in N:
    u = quicksum(v[i,o] * x[i,o] for o in O)
    for k in range(1, sum(v[i,o] for o in O)+1):
        m.addConstr(W[i] <= math.log(k) + \
            (math.log(k+1) - math.log(k)) * (u - k))
m.setObjective(quicksum(W[i] for i in N), GRB.MAXIMIZE)
m.optimize()