In this paper we address the problem of electing a committee among a set of m candidates on the basis of the preferences of a set of n voters. We consider the approval voting method in which each voter can approve as many candidates as he likes by expressing a preference profile (boolean m -vector). In order to elect a committee, a voting rule must be established to ‘transform’ the n voters’ profiles into a winning committee. The problem is widely studied in voting theory; for a variety of voting rules the problem was shown to be computationally difficult and approximation algorithms and heuristic techniques were proposed in the literature. In this paper we follow an Ordered Weighted Averaging approach and study the k -sum approval voting (optimization) problem in the general case 1 ≤ k < n . For this problem, we provide different mathematical programming formulations that allow us to solve it in an exact solution framework. We provide computational results showing that our approach is efficient for medium size test problems ( n up to 200, m up to 60), since in all tested cases it was able to find the exact optimal solution in very short computational times.

Mathematical Programming formulations for the efficient solution of the k-sum approval voting problem / Ponce, Diego; Puerto, Justo; Ricca, Federica; Scozzari, Andrea. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 98:(2018), pp. 127-136. [10.1016/j.cor.2018.05.014]

Mathematical Programming formulations for the efficient solution of the k-sum approval voting problem

Federica Ricca;
2018

Abstract

In this paper we address the problem of electing a committee among a set of m candidates on the basis of the preferences of a set of n voters. We consider the approval voting method in which each voter can approve as many candidates as he likes by expressing a preference profile (boolean m -vector). In order to elect a committee, a voting rule must be established to ‘transform’ the n voters’ profiles into a winning committee. The problem is widely studied in voting theory; for a variety of voting rules the problem was shown to be computationally difficult and approximation algorithms and heuristic techniques were proposed in the literature. In this paper we follow an Ordered Weighted Averaging approach and study the k -sum approval voting (optimization) problem in the general case 1 ≤ k < n . For this problem, we provide different mathematical programming formulations that allow us to solve it in an exact solution framework. We provide computational results showing that our approach is efficient for medium size test problems ( n up to 200, m up to 60), since in all tested cases it was able to find the exact optimal solution in very short computational times.
2018
Approval voting; Ordered Weighted Averaging (OWA); k -sum optimization problems
01 Pubblicazione su rivista::01a Articolo in rivista
Mathematical Programming formulations for the efficient solution of the k-sum approval voting problem / Ponce, Diego; Puerto, Justo; Ricca, Federica; Scozzari, Andrea. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 98:(2018), pp. 127-136. [10.1016/j.cor.2018.05.014]
File allegati a questo prodotto
File Dimensione Formato  
Ricca_Mathematical-Programming-ComputerOR_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 722.18 kB
Formato Adobe PDF
722.18 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1171846
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact