Winner Determination Problem (COMSOC)

Definition

Winner Determination Problem (COMSOC)

To determine a winner, we may need the following:

Input: A preference profile $P=(C,V,R)$ and an alternative $c^{\ast }\in C$.
Question: Is $c^{\ast }$ a winner under rule $\lambda$?

Polynomial

Polynomially decidable voting rules

For $\lambda \in \{$ Plurality, Borda, STV, Lull $\}$, winner determination can be solved in polynomial time.