Class: Equalshares::Rules::Phragmen

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

Overview

Phragmén's sequential rule for approval participatory budgeting. Faithful port of pabutools' sequential_phragmen (resolute case).

Voters accumulate "load" (starting at 0). Buying a project raises all its approvers to a common load level (sum of their loads + cost) / |approvers|. At each step the project minimising that new maximum load is bought; the rule stops once the next project to buy would exceed the budget.

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 



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/equalshares/rules/phragmen.rb', line 13

def call
  start = now
  project_ids = election.project_ids
  approvers = election.approvers
  cost = election.costs
  budget_limit = election.budget
  approval_score = project_ids.to_h { |c| [c, approvers[c].length] }

  loads = Hash.new(0) # voter id -> current load
  remaining = project_ids.select { |c| cost[c] <= budget_limit }
  winners = []
  current_cost = 0

  loop do
    break if remaining.empty?

    min_maxload, argmin = min_new_maxload(remaining, approvers, loads, cost, approval_score)

    # Stop as soon as the next project to be bought would violate the budget.
    break if argmin.any? { |c| current_cost + cost[c] > budget_limit }

    selected = Tie.resolve_one(project_ids, cost, approvers, params, argmin)
    approvers[selected].each { |i| loads[i] = min_maxload }
    winners << selected
    current_cost += cost[selected]
    remaining.delete(selected)
    progress&.call((100 * current_cost / budget_limit).floor)
  end

  result(winners, start)
end