Skip to content

Instantly share code, notes, and snippets.


Dominik Peters DominikPeters

View GitHub Profile
DominikPeters /
Created Aug 29, 2020
Calculate Kemeny's rule using gurobipy
from gurobipy import *
import itertools
def better(vote, a, b):
return vote.index(a) < vote.index(b)
def kemeny(profile):
# a profile is a list of rankings, e.g. [(0,1,2),(1,2,0),(1,2,0)]
C = profile[0]
w = {}
DominikPeters /
Created Aug 27, 2020
Python implementation of the merge insertion sort algorithm
# Implementation of the Merge Insertion sort algorithm
# -- a sort algorithm that is efficient w.r.t. number of pairwise comparisons
# based on the description in
# This is not intended to be time- or space-efficient.
# "less" is a function such that less(x,y) is true iff x should go to the left of y
# Dominik Peters, August 2020
# imports only needed for test at the bottom
from __future__ import print_function
DominikPeters / __counterexamples_fair_division.txt
Last active Jun 9, 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 /
Created Apr 29, 2020
Maximize Nash welfare for allocating indivisible goods
# 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 /
Created Apr 29, 2020
Compute Cayley distance between two rankings
# 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 /
Created Apr 29, 2020
Simple implementation of the Probabilistic Serial fair division mechanism
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