Binary linear programming solutions and non-approximability for control problems in voting systems

In this paper we consider constructive control by adding and deleting candidates in Copeland and Llull voting systems from a theoretical and an experimental point of view. We show how to characterize the optimization versions of these four control problems as special digraph problems and binary linear programming formulations of linear size. Our digraph characterizations allow us to prove the hardness of approximations with absolute performance guarantee for optimal constructive control by deleting candidates in Copeland and by adding candidates in Llull voting schemes and the nonexistence of efficient approximation schemes for optimal constructive control by adding and deleting candidates in Copeland and Llull voting schemes. Our experimental study of running times using LP solvers shows that for a lot of practical instances even the hard control problems can be solved very efficiently. (C) 2013 Elsevier B.V. All rights reserved.