Compilation complexity
Compilation complexity is the smallest number of bits required to summarize a input to a function, such that the output of the function can be computed correctly. The notion was particulatly studied in voting theory.[1] Often, a group has to accept a decision, but some of the voters have not arrived yet. It is desired to take the votes of the present voters and summarize them such that, when the other voters arrive, we can determine the winner. The compilation complexity of a voting-rule is the smallest number of bits required for the summary.
An important advantage of low compilation complexity is that it makes it easier to verify voting outcomes. For example, suppose an elections are held in a country of 1,000,000 people, divided into 1000 voting-stations of 1000 voters each. Low compilation complexity lets us summarize the outcome in each voting-station separately, which is relatively easy to verify by double-counting by representatives of the parties. Then, every citizen can verify the final outcome by summing the results from the 1000 voting stations. This verifiability is important so that the public trusts and accepts the voting rule.[1]
Topics
Related problems
- Knowledge compilation - compiling a part of the input offline, such that the when the online input arrives, the output can be computed quickly. Here, the goal of the compilation is to save time, rather than to save space.
- Complexity of vote elicitation - given a voting rule, a set of known votes and a set of new voters, is the outcome of the vote already determined from the known votes:
- Computation of possible and necessary winners - given a voting rule, a set of incomplete votes (partial orders on the set of candidates), who are the candidates who can still possibly win the election, and is there a candidate who surely wins it?
- Communication complexity - given a voting rule and a set of voters, what is the worst-case number of bits transmitted by the best protocol allowing to compute the outcome of the election?
References
- ^ a b Chevaleyre, Yann; Lang, Jérôme; Maudet, Nicolas; Ravilly-Abadie, Guillaume (2009-07-11). "Compiling the votes of a subelectorate". Proceedings of the 21st International Joint Conference on Artificial Intelligence. IJCAI'09. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.: 97–102.
- ^ Xia, Lirong; Conitzer, Vincent (2010-07-04). "Compilation Complexity of Common Voting Rules". Proceedings of the AAAI Conference on Artificial Intelligence. 24 (1): 915–920. doi:10.1609/aaai.v24i1.7627. ISSN 2374-3468.
- ^ Karia, Neel; Lang, Jérôme (2021-05-18). "Compilation Complexity of Multi-Winner Voting Rules (Student Abstract)". Proceedings of the AAAI Conference on Artificial Intelligence. 35 (18): 15809–15810. doi:10.1609/aaai.v35i18.17901. ISSN 2374-3468.