Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix timeout of irresolute sequential rules with many ties #72

Open
martinlackner opened this issue Jul 4, 2023 · 0 comments
Open

Fix timeout of irresolute sequential rules with many ties #72

martinlackner opened this issue Jul 4, 2023 · 0 comments
Labels
enhancement New feature or request help wanted Extra attention is needed

Comments

@martinlackner
Copy link
Owner

The following program runs for a (very) long time:

from abcvoting.preferences import Profile
from abcvoting import abcrules

profile = Profile(num_cand=10)
profile.add_voter({0, 1, 2,3,4,5,6,7,8,9})
committeesize = 10
abcrules.compute_seqpav(profile, committeesize, resolute=False)

The problem is that with resolute=False all possible permutations of candidates are considered, to see if another committee can be found. This problem occurs in the implementation of all sequential rules.

The solution is to recognize that all candidates are equivalent and can be replaced with each other.
That is, all candidates are replaced by a placeholder (say A) and we store that the ballot consists of 10 copies of A. Only when outputting committees, we resolve the placeholders and replace them with all possible combinations of candidates (in case of the example, there is only one possibility).

Challenge: correctly use multi-sets instead of sets in all sequential algorithms.

@martinlackner martinlackner added enhancement New feature or request help wanted Extra attention is needed labels Jul 4, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request help wanted Extra attention is needed
Projects
None yet
Development

No branches or pull requests

1 participant