def complete_utilitarian(N, C, cost, u, b, W): util = {c: sum([u[c][i] for i in N]) for c in C} committee_cost = sum([cost[c] for c in W]) while True: next_candidate = None highest_util = float("-inf") for c in C.difference(W): if leq(committee_cost + cost[c], b): if util[c] / cost[c] > highest_util: next_candidate = c highest_util = util[c] / cost[c] if next_candidate is None: break W.add(next_candidate) committee_cost += cost[next_candidate] return W

def method_of_equal_shares(N, C, cost, u, b): W = set() total_utility = {c: sum(u[c].values()) for c in C} supporters = {c: set([i for i in N if u[c][i] > 0]) for c in C} budget = {i: b / len(N) for i in N} while True: next_candidate = None lowest_rho = float("inf") for c in C.difference(W): if leq(cost[c], sum([budget[i] for i in supporters[c]])): supporters_sorted = sorted(supporters[c], key=lambda i: budget[i] / u[c][i]) price = cost[c] util = total_utility[c] for i in supporters_sorted: if leq(price * u[c][i], budget[i] * util): break price -= budget[i] util -= u[c][i] rho = price / util \