n° 161, Printemps 2003, spécial Recherche opérationnelle et aide à la décision
The approval-voting polytope: combinatorial interpretation of the facets
Le polytope du vote par approbation : interprétation combinatoire des facettes
Résumé
Doignon et Fiorini (2003) déterminent toutes les facettes du polytope du vote approbatoire. Ils livrent ainsi une caractérisation d'un modèle probabiliste dû à Falmagne et Regenwetter (1996) : le modèle sous indépendance de taille pour le vote approbatoire. Le présent texte est un complément. Il donne d'abord une preuve alternative du résultat central, plus directe mais aussi constructive. L'interprétation combinatoire des facettes du polytope du vote approbatoire est ensuite étudiée. Enfin, une description linéaire du polytope est obtenue dans le cas où le nombre d'alternatives vaut 6.
Abstract
Doignon and Fiorini (2003)determine all facets of the approval-voting polytope, thus offering a characterization of the size-independent model for approval voting of Falmagne and Regenwetter (1996). The present paper is a follow-up. It first provides an alternate proof of the basic result, which is more direct and at the same time constructive. Then, the combinatorial interpretation of the facets of the approval-voting polytope is further investigated. Finally, we derive a linear description of the polytope in case the number of alternatives equals 6.
Index
- Mots clés :
- facette, flot dans un réseau, polytope du vote approbatoire, sous-ensemble stable d'un graphe
- Keywords :
- approval-voting polytope, facet, network flow, stable set in a graph
- Thèmes :
- combinatoire, graphes, ordres et préordres, votes
- Topics :
- combinatorics, graphs, orders and preorders, voting
Pour citer cet article
