{{ message }}

Instantly share code, notes, and snippets.

# Dominik PetersDominikPeters

Created Aug 29, 2020
Calculate Kemeny's rule using gurobipy
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 w = {}
Created Aug 27, 2020
Python implementation of the merge insertion sort algorithm
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
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.
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
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
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)) # 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.