View kemeny.py
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 = {} |
View merge_insertion.py
# 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 | |
# https://en.wikipedia.org/w/index.php?title=Merge-insertion_sort&oldid=959884881 | |
# 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 |
View __counterexamples_fair_division.txt
A collection of some counterexamples I've found for | |
fair allocation of indivisible goods, mostly via random sampling. |
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 |
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 |
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 |