Class: Equalshares::Rules::Maximin

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

Overview

The maximin support rule (Aziz, Lee & Talmon 2018; "Generalised Sequential Phragmén"), for approval ballots. Faithful port of pabutools' maximin_support.

At each step, for every still-affordable project, the minimum achievable maximum voter load of the committee W ∪ c is computed, and the project minimising it is bought. Rather than an LP (as pabutools uses), the minimum max-load is computed exactly: it equals the max-density subgraph value z*(W) = max_⊆ W, S≠∅ cost(S) / |approvers(S)| solved via a parametric max-flow (Dinkelbach iterations) in exact rational arithmetic. This keeps the rule pure-Ruby, dependency-free and exact.

Requires integer project costs (as in real pabulib data).

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 



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/maximin.rb', line 18

def call
  start = now
  project_ids = election.project_ids
  approvers = election.approvers
  # maximin needs integer costs to scale the max-flow network exactly.
  cost = project_ids.to_h { |c| [c, integer_cost(instance.projects[c]["cost"])] }
  budget_limit = integer_cost(instance.budget)

  available = project_ids.select { |c| cost[c].between?(0, budget_limit) }
  winners = []
  remaining_budget = budget_limit

  loop do
    available = available.select { |c| !winners.include?(c) && cost[c] <= remaining_budget }
    break if available.empty?

    argmin = argmin_by_load(available, winners, cost, approvers)
    selected = Tie.resolve_one(project_ids, cost, approvers, params, argmin)

    winners << selected
    remaining_budget -= cost[selected]
    progress&.call((100 * winners.sum { |c| cost[c] } / budget_limit).floor)
  end

  result(winners, start)
end