Skip to content

Instantly share code, notes, and snippets.

Dominik Peters DominikPeters

Block or report user

Report or block DominikPeters

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
@DominikPeters
DominikPeters / __counterexamples_fair_division.txt
Last active May 2, 2020
Counterexamples in fair division
View __counterexamples_fair_division.txt
A collection of some counterexamples I've found for
fair allocation of indivisible goods, mostly via random sampling.
@DominikPeters
DominikPeters / nash_indivisible.py
Created Apr 29, 2020
Maximize Nash welfare for allocating indivisible goods
View 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
@DominikPeters
DominikPeters / cayley_distance.py
Created Apr 29, 2020
Compute Cayley distance between two rankings
View cayley_distance.py
# 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
DominikPeters / probabilistic_serial.py
Created Apr 29, 2020
Simple implementation of the Probabilistic Serial fair division mechanism
View 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
You can’t perform that action at this time.