Vainqueurs de Kemeny et tournois difficiles
Guénoche, Alain
Mathématiques et Sciences humaines, Tome 136 (1996), p. 57-65 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Dans cet article, on s'intéresse à la détermination des ordres médians des tournois valués. On propose d'une part des améliorations d'une méthode arborescente permettant de limiter le nombre de nœuds et donc d'accélérer l'énumération des ordres médians. D'autre part, pour les tournois difficiles qui restent incalculables, on propose de réduire le tournoi en éliminant certains candidats.

In this paper, we deal with the computation of median orders of weighted tournaments. First, we present improvements of a branch and bound method in order to speed up the enumeration of median orders. Then, for the hard tournaments for which these improvements are not sufficient, we study two ways to reduce the tournament by deleting vertices which appear as poor candidates.

@article{MSH_1996__133__57_0,
     author = {Gu\'enoche, Alain},
     title = {Vainqueurs de Kemeny et tournois difficiles},
     journal = {Math\'ematiques et Sciences humaines},
     volume = {136},
     year = {1996},
     pages = {57-65},
     mrnumber = {1411799},
     zbl = {0870.90096},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/MSH_1996__133__57_0}
}

Guénoche, Alain. Vainqueurs de Kemeny et tournois difficiles. Mathématiques et Sciences humaines, Tome 136 (1996) pp. 57-65. http://gdmltest.u-ga.fr/item/MSH_1996__133__57_0/

Banks, J. (1985) "Sophisticated voting outcomes and agenda control ", Social Choice and Welfare, 2, 295-306. | Zbl 0597.90011

Barthélemy, J.-P. et B. Monjardet (1981) "The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences, 1, 235-267. | MR 616379 | Zbl 0486.62057

Barthélemy, J.-P., A. Guénoche et O. Hudry (1989) "Median linear orders: heuristics and a branch and bound algorithm", European Journal of Operational Research, 41, 313-325. | MR 1020904 | Zbl 0689.90003

Charon-Fournier, I., A. Germa et O. Hudry (1992) "Utilisation des scores dans des méthodes exactes déterminant les ordres médians de tournois", Mathématiques, Informatique et Sciences Humaines, 119, 53-74. | Numdam | MR 1195698 | Zbl 0845.05050

Charon, I., O. Hudry et F. Woirgard (1996) "Ordres médians et ordres de Slater des tournois ", Mathématiques, Informatique et Sciences Humaines, ce même numéro. | Numdam | MR 1411798

Condorcet, M.J.A.N. Caritat (marquis de) (1785) Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix, Paris.

Guénoche, A. (1977) "Un algorithme pour pallier l'effet Condorcet", RAIRO, 11, 1, 73-83. | Numdam | Zbl 0356.90068

Hudry, O. (1989) Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires, Thèse ENST, Paris.

Hudry, O. et F. Woirgard (1994) "Combinatorics and voting theory: on the number of median orders of tournaments", communication à "Conference on combinatorics in the behavioral sciences", 15-19 août 1994, Irvine, États-Unis.

Kemeny, J.G. (1959) "Mathematics without numbers", Daedelus, 8, 577-591.

Laslier, J.-F. (1996) "Solutions de tournois : un spicilège", Mathématiques, Informatique et Sciences Humaines, ce même numéro. | Numdam | MR 1411797

Monjardet, B. (1973) "Tournois et ordres médians pour une opinion", Mathématiques et Sciences Humaines, 43, 55-70. | Numdam | MR 376451 | Zbl 0271.05114

Remage Jr., R. et W.A. Thompsonjr. (1966) "Maximum likelihood paired comparison rankings", Biometrika, 53,143-149. | MR 196854 | Zbl 0138.13207

Smith, A.F.M. et C.D. Payne (1974) "An algorithm for determining Slater's i and all nearest adjoining orders, British Journal of Mathematical and Statistical Psychology, 27, 49-52.