DominikPeters

# 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

A collection of some counterexamples I've found for
fair allocation of indivisible goods, mostly via random sampling.

DominikPeters

Hyperref configuration including back references from the bibliography to the pages where the reference was cited.

\usepackage[pagebackref]{hyperref}
\hypersetup{
	pdfencoding=auto, 
	psdextra,
	colorlinks=true,
	citecolor=green!50!black,
	linkcolor=red!60!black,

DominikPeters

# 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

DominikPeters

import cvxpy as cp
import math

def compute_hi(rankings):
    """Compute h_i(a) for all voters and alternatives."""
    hi = []
    for ranking in rankings:
        h = {}
        for a in ranking:
            h[a] = set(ranking[:ranking.index(a)+1])

DominikPeters

// usage: node mes.js <path-to-pb-file>

const fs = require('fs');
const readline = require('readline');

function parsePBFile(filePath) {
    return new Promise((resolve, reject) => {
        const meta = {};
        const projects = {};
        const votes = {};

DominikPeters

cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div>div>strong
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(4)
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(5)
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(6)
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(7)
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(8)
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(9)
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(10)
cmt3.research.microsoft.com##div[data-bind="foreach: questions"]>div.row:nth-of-type(15)
cmt3.research.microsoft.com##div[data-bind="foreach:reviews"] > h2

DominikPeters

# Adapted from https://github.com/martinlackner/abcvoting/blob/6aacadb0e3e70e4f83a82225b05730f72a6230d4/abcvoting/generate.py#L166

def mallows(reference_ranking, dispersion):
    distributions = []
    for i in range(len(reference_ranking)):
        distributions.append([dispersion ** (i - j) for j in range(i + 1)])
    while True:
        vote = []
        for i in range(len(reference_ranking)):
            pos = random.choices(range(i + 1), weights=distributions[i], k=1)[0]

DominikPeters

def nash(N, A, u, rounds=500):
    "N is set of voters, A is set of alternatives, u is a utility dictionary"
    "where u[i,x] >= 0 is the utility of i for x, usually either 0 or 1"
    p = {x : 1/len(A) for x in A}
    for _ in range(rounds):
        q = {x : 0 for x in A}
        for i in N:
            util = sum(u[i,x] * p[x] for x in A)
            for x in A:
                q[x] += (1/len(N)) * (u[i,x] * p[x]) / util

DominikPeters

# first install pdftk. For recent MacOS version, get it here: https://www.pdflabs.com/tools/pdftk-the-pdf-toolkit/pdftk_server-2.02-mac_osx-10.11-setup.pkg

import os

os.system(f"pdftk input.pdf output uncompressed.pdf uncompress")

with open("fixed.pdf", "wb") as outfile:
  for line in open("uncompressed.pdf", "rb"):
      patterns = [
          b"This content downloaded from",