Vainqueurs de Kemeny et tournois difficiles

Alain Guénoche

Mathématiques et Sciences Humaines (1996)

  • Volume: 133, page 57-65
  • ISSN: 0987-6936

Abstract

top
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.

How to cite

top

Guénoche, Alain. "Vainqueurs de Kemeny et tournois difficiles." Mathématiques et Sciences Humaines 133 (1996): 57-65. <http://eudml.org/doc/94477>.

@article{Guénoche1996,
abstract = {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.},
author = {Guénoche, Alain},
journal = {Mathématiques et Sciences Humaines},
keywords = {computation of median orders; weighted tournaments; branch-and-bound},
language = {fre},
pages = {57-65},
publisher = {Ecole des hautes-études en sciences sociales},
title = {Vainqueurs de Kemeny et tournois difficiles},
url = {http://eudml.org/doc/94477},
volume = {133},
year = {1996},
}

TY - JOUR
AU - Guénoche, Alain
TI - Vainqueurs de Kemeny et tournois difficiles
JO - Mathématiques et Sciences Humaines
PY - 1996
PB - Ecole des hautes-études en sciences sociales
VL - 133
SP - 57
EP - 65
AB - 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.
LA - fre
KW - computation of median orders; weighted tournaments; branch-and-bound
UR - http://eudml.org/doc/94477
ER -

References

top
  1. Banks, J. (1985) "Sophisticated voting outcomes and agenda control ", Social Choice and Welfare, 2, 295-306. Zbl0597.90011
  2. Barthélemy, J.-P. et B. Monjardet (1981) "The median procedure in cluster analysis and social choice theory", Mathematical Social Sciences, 1, 235-267. Zbl0486.62057MR616379
  3. 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. Zbl0689.90003MR1020904
  4. 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. Zbl0845.05050MR1195698
  5. 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. MR1411798
  6. 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. 
  7. Guénoche, A. (1977) "Un algorithme pour pallier l'effet Condorcet", RAIRO, 11, 1, 73-83. Zbl0356.90068
  8. Hudry, O. (1989) Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires, Thèse ENST, Paris. 
  9. 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. 
  10. Kemeny, J.G. (1959) "Mathematics without numbers", Daedelus, 8, 577-591. 
  11. Laslier, J.-F. (1996) "Solutions de tournois : un spicilège", Mathématiques, Informatique et Sciences Humaines, ce même numéro. MR1411797
  12. Monjardet, B. (1973) "Tournois et ordres médians pour une opinion", Mathématiques et Sciences Humaines, 43, 55-70. Zbl0271.05114MR376451
  13. Remage Jr., R. et W.A. ThompsonJr. (1966) "Maximum likelihood paired comparison rankings", Biometrika, 53,143-149. Zbl0138.13207MR196854
  14. 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. 

NotesEmbed ?

top

You must be logged in to post comments.