Proportional Representation in Vote Streams
This addresses the challenge of efficient real-time decision-making in large-scale elections or surveys for computational social choice and streaming data applications, though it appears incremental as it builds on existing voting rules with algorithmic optimizations.
The paper tackled the problem of selecting representative committees from large streams of votes in real-time, developing space-efficient algorithms for multiwinner proportional representation voting rules like Approval-based and Borda-based variants, and showed that it's possible to identify approximate committees with fixed size using space independent of voter count.
We consider elections where the voters come one at a time, in a streaming fashion, and devise space-efficient algorithms which identify an approximate winning committee with respect to common multiwinner proportional representation voting rules; specifically, we consider the Approval-based and the Borda-based variants of both the Chamberlin-- ourant rule and the Monroe rule. We complement our algorithms with lower bounds. Somewhat surprisingly, our results imply that, using space which does not depend on the number of voters it is possible to efficiently identify an approximate representative committee of fixed size over vote streams with huge number of voters.