A note on the query complexity of the Condorcet winner problem |
| |
| Authors: | Ariel D. Procaccia |
| |
| Affiliation: | School of Computer Science and Engineering, The Hebrew University of Jerusalem, Jerusalem 91904, Israel |
| |
| Abstract: | Given an unknown tournament over {1,…,n}, we show that the query complexity of the question “Is there a vertex with outdegree n−1?” (known as a Condorcet winner in social choice theory) is exactly 2n−⌊log(n)⌋−2. This stands in stark contrast to the evasiveness of this property in general digraphs. |
| |
| Keywords: | Analysis of algorithms Graph algorithms Theory of computation Concrete complexity Social choice |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
