search

pbvoting / pabutools

A complete set of tools to work with participatory budgeting elections.
https://pbvoting.github.io/pabutools/
GNU General Public License v3.0
7 stars 12 forks source link

Added cstv algorithm and tests. #29

Closed tjhv10 closed 2 months ago

tjhv10 commented 2 months ago

An implementation of the algorithms in: "Participatory Budgeting with Cumulative Votes", by Piotr Skowron, Arkadii Slinko, Stanisaw Szufa, Nimrod Talmon (2020), https://arxiv.org/pdf/2009.02690 Programmer: Achiya Ben Natan Date: 2024/05/16.

Simon-Rey commented 2 months ago

Hi!

Thanks for contributing. I quickly went through the code, it looks good to me but is not (at the moment) super consistent with the rest of the package. It is important to maintain consistency for the users, so here is a list of things to do/include/correct:

Once again, thanks for contributing! If you need help with anything, let me know :)

tjhv10 commented 2 months ago

Hi, thank you for the feedback. I will work on the things you suggested and commit the changes asap.

On Tue, 25 Jun 2024, 12:08 Simon-Rey, @.***> wrote:

Hi!

Thanks for contributing. I quickly went through the code, it looks good to me but is not (at the moment) super consistent with the rest of the package. It is important to maintain consistency for the users, so here is a list of things to do/include/correct:

  • For typing list, do not use List from the typing module but list the builtin class and import annotations from future to ensure compatibility with lower version of Python
  • Make sure that the function is consistent with the rest of the package ("donors" should probably be "profile", "projects" should be "instance", the instance should be the first parameter, and then the profile etc...)
  • The outcome of a rule needs to be BudgetAllocation object
  • The rules of the package should take a "resoluteness" parameter such that, when set to "False", the irresolute outcome is returned
  • Is there any tie-breaking happening in the rule? Then there must be a tie_breaking parameter to handle the ties (of type TieBreakingRule)
  • You need to allow having an initial budget allocation through a parameter "initial_budget_allocation"
  • Do not include a main both in the tests and in the package
  • Remove the examples from the file in the package, no need to include these in the package
  • In the docs of the main function, add a brief description of the rule, see the other rules as examples
  • Update the docs-source files to include the new rule, so that should be in source/usage/rules.rst and in source/reference/rules.rst

Once again, thanks for contributing! If you need help with anything, let me know :)

— Reply to this email directly, view it on GitHub https://github.com/pbvoting/pabutools/pull/29#issuecomment-2188377297, or unsubscribe https://github.com/notifications/unsubscribe-auth/A4XZP3EE4P47NMT4XCRXA4TZJEXSJAVCNFSM6AAAAABJYKALZKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDCOBYGM3TOMRZG4 . You are receiving this because you authored the thread.Message ID: @.***>

tjhv10 commented 2 months ago

Few comments: first of all I fixed some things already: 1,2,3. You can see them in the last commit.

For number 4: can you explain exactly what the parameter resoluteness does and what it should do in my code? I couldn't understand it from the other files in the directory.

For number 5: there is no tie braking in my code and in the paper I implemented.

For number 6: The intel budget allocation is inside of the input of the donors. The initial budget is the sum of all of the donations.

I will fix the rest of the errors when the code will be ready in the other areas. Thank you for your help.

Simon-Rey commented 2 months ago

I'll have a new look soon.

About resoluteness: the idea is the following: it may be that the rule can at some point choose between several projects (for instance because they all have the same score). If resoluteness is set to False, in this case you need to output all the budget allocations that could be selected (based on any arbitrary choice of ties projects). To give you another example it would consist is returning all the maximum flows in a flow algorithm instead of just one maximum.

I'm surprised that you are saying that there is no tie breaking. For instance if all projects have the same cost and all voters give the same contribution to all projects, what happens?

erelsgl commented 2 months ago

@Simon-Rey Regarding irresolute rules: since the rule is sequential, I am not sure how to make them irresolute. Does it require to keep a tree with all possibilities in each step? This tree might grow very large and complex if there are many iterations.

Simon-Rey commented 2 months ago

Yes it's bad in terms of complexity, but it's anyways a feature that is only interesting on small instances. You can check the implementation of the greedy max welfare, there is a all_budget_allocations list that is populated by side effect. (https://github.com/pbvoting/pabutools/blob/main/pabutools/rules/greedywelfare/greedywelfare_rule.py)

tjhv10 commented 2 months ago

Hi, I added tie breaking to the algorithm. I didn't succeed to add the resoluteness = False feature so I added this error: if not resoluteness: raise NotImplementedError('The "resoluteness = False" feature is not yet implemented'). If you want to see the closest I got to add the resoluteness = False feature you can check it in the best try for resulteness commit which is here: https://github.com/pbvoting/pabutools/pull/29/commits/21d3e64da9fd5bc4f45c2453dee0e9f1f895dfe5

Simon-Rey commented 2 months ago

That looks all good to me. Thanks for the effort you put into this :)

Simon-Rey commented 2 months ago

Ok I looked more carefuly at the code now and I have changed a lot of things. Many things were not correct, the typing notably but also the use of the different elements of the package. You can check my changes, let me know if you spot any mistake. I still need to update the tests.

tjhv10 commented 2 months ago

Ok I looked more carefuly at the code now and I have changed a lot of things. Many things were not correct, the typing notably but also the use of the different elements of the package. You can check my changes, let me know if you spot any mistake. I still need to update the tests.

I looked throw the code and you really changed a lot. I think the names of the functions you changed their name should remain the names I did because then it is easier to compare the code to the paper the code is based on but it is your library and you can do what ever you like. If you wander what is this line: "donor[chosen_project] += (np.ceil(change * 100000000000000)/ 100000000000000) # TODO: What is this?? " it is the easiest way I found to round up a number in the 14th number after the point which is a crucial feature that the code will not work without it for now because of rounding errors in python which makes the r to be 0.999999999999999999 instead of 1 and then the while loop will not stop running. If you find a better way to change the r to 1 after one iteration instead of the while running a few times to fix the rounding mistake of python please change this part, it will make the minimal transfer function to work a lot faster and better.

Simon-Rey commented 2 months ago

Ok for the fraction, I anyways need to update the code so that it uses the function functionalities of the package (because we already have code to deal with fractions).