Optimal algorithms for exact, inexact, and approval voting

The design of optimal n-way voting algorithms based on the structure of the input object space is considered. The design techniques are then extended to inexact and approval voting schemes. It is shown that efficient theta (n)-time voting algorithms can be designed when the input object space is small. Next in the hierarchy is the case of a totally-ordered object space that supports worst-case theta (nlogn) algorithms for both exact and inexact voting as well as for certain approval-voting schemes. An unordered input object space leads to worst-case Omega (n/sup 2/) algorithms, even when a distance metric can be defined on the input object space. Some observations on the relationship of voting to other well-studied problems, particularly sorting, are also included.<>