GCR Algorithm

[dotandanino]

Hello,

We are computer science students currently working on a research project to implement the algorithms presented in the AAAI-24 paper "Fair Lotteries for Participatory Budgeting" (by Haris Aziz, Xinhang Lu, Mashbat Suzuki, Jeremy Vollen, and Toby Walsh).

While building our implementation on top of pabutools, we noticed that the Greedy Cohesive Rule (GCR) mentioned in the literature is not currently documented or exposed in the package's rules module. We wanted to ask if there is an existing, unreleased implementation of GCR within the repository that we might have missed, or if there are any plans to include it in an upcoming release?

[Simon-Rey]

There is implementation of the rule, nor any plan to implement it. It is, to me at least, unclear how to implement it in a way that is not too slow. So I'll be curious to see what you propose :)

[erelsgl]

Just to make sure I understand: is this the GCR algorithm?

• Loop over all subsets S of active voters. For each S do:
  • Loop over all subsets T of unselected projects such that cost(T) <= (B/n)*|S|. For each such T do:
    • Let beta_[S,T] := min(|A[i] intersect T| for i in S)

Choose the pair S,T for which beta_[S,T] is the largest. Add T to the budget, and mark agents in S as inactive.