First, it is easy to observe that if the number m of alternatives A is bounded—assuming voters are not weighted (we briefly discuss weighted voters in what follows) and the voting rule satisfies anonymity—then both PW and NW are computable in polynomial time if the voting rule supports polynomial winner determination (Conitzer et al., 2007; Walsh, 2007). This is so because there are only a constant number of distinct votes b = m! that may be cast by any voter. By anonymity, the number of voters casting each vote is sufficient to determine a winner, and there are at most (n + 1) b such “count” profiles that need to be enumerated
If you want to change selection, open document below and click on "Move attachment"
- (no access) - CompSocBook.pdf, p246
|status||not read|| ||reprioritisations|
|last reprioritisation on|| ||suggested re-reading day|
|started reading on|| ||finished reading on|