Class: Equalshares::Rules::Greedy

Inherits:
Base
  • Object
show all
Defined in:
lib/equalshares/rules/greedy.rb

Overview

Greedy approximation of utilitarian welfare, generalised over a satisfaction measure. Faithful port of pabutools' greedy_utilitarian_welfare (additive, resolute case).

Projects are picked in order of decreasing "satisfaction density" = total satisfaction of the project divided by its cost, resolving ties by the tie-breaking order; any project that still fits the remaining budget is taken (knapsack greedy). For Cost_Sat the density is the approver count.

Instance Method Summary collapse

Methods inherited from Base

call, #initialize

Constructor Details

This class inherits a constructor from Equalshares::Rules::Base

Instance Method Details

#call ⇒ Object 



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/equalshares/rules/greedy.rb', line 14

def call
  start = now
  project_ids = election.project_ids
  approvers = election.approvers
  cost = election.costs
  sat = Satisfaction.for(params.satisfaction)

  order = Tie.total_order(project_ids, cost, approvers, params)
  order_index = order.each_with_index.to_h
  ranked = project_ids.sort_by { |c| [-density(c, cost, approvers, sat), order_index[c]] }

  winners = []
  remaining_budget = election.budget
  ranked.each do |c|
    next unless cost[c] <= remaining_budget

    winners << c
    remaining_budget -= cost[c]
  end

  result(winners, start)
end