Ordres médians et ordres de Slater des tournois
Charon, Irène ; Hudry, Olivier ; Woirgard, Frédéric
Mathématiques et Sciences humaines, Tome 136 (1996), p. 23-56 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Dans cet article, nous essayons de faire le point sur les résultats concernant les aspects combinatoires et algorithmiques des ordres médians et des ordres de Slater des tournois. La plupart des résultats recensés sont tirés de différentes publications ; plusieurs sont originaux.

In this paper, we try to enumerate the results dealing with the combinatorial and algorithmic aspects of the median orders and Slater orders of tournaments. Most of the quoted results may be found in the different papers devoted to these topics ; some others are new ones.

@article{MSH_1996__133__23_0,
     author = {Charon, Ir\`ene and Hudry, Olivier and Woirgard, Fr\'ed\'eric},
     title = {Ordres m\'edians et ordres de Slater des tournois},
     journal = {Math\'ematiques et Sciences humaines},
     volume = {136},
     year = {1996},
     pages = {23-56},
     mrnumber = {1411798},
     zbl = {0870.90095},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/MSH_1996__133__23_0}
}

Charon, Irène; Hudry, Olivier; Woirgard, Frédéric. Ordres médians et ordres de Slater des tournois. Mathématiques et Sciences humaines, Tome 136 (1996) pp. 23-56. http://gdmltest.u-ga.fr/item/MSH_1996__133__23_0/

[1] Adám, A. (1964) "Problem" in Theory of graphs and its applications, Proc. Coll. Smolenice, Czech. Acad. Sci. Publ.

[2] Alon, N. (1990) "The maximum number of Hamiltonian paths in tournaments ", Combinatorica, 10, 319-324. | MR 1099246 | Zbl 0724.05036

[3] Alon, N. et J. Spencer, The probabilistic method, J. Wiley, New York, 1992. | MR 1140703 | Zbl 0767.05001

[4] Alspach, B. (1967) "Cycles of each length in regular tournaments", Canad. Math. Bull., 10, 283-286. | MR 213261 | Zbl 0148.43602

[5] Arditti, D. (1984) "Un nouvel algorithme de recherche d'un ordre induit par des comparaisons par paires", in Data analysis and informatics III, E. Diday et al. (sd), North Holland, Amsterdam, 323-343. | MR 787645 | Zbl 0565.90030

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

[7] Banks, J., G. Bordes et M. Le Breton (1991) "Covering relations, closest orderings and hamiltonian bypaths in tournaments", Social Choice and Welfare, 8, 355-363. | MR 1129431 | Zbl 0734.90027

[8] Barthélemy, J.-P., G. Cohen et A. Lobstein (1992), Complexité algorithmique et problèmes de communication, Masson, Paris. | MR 1188183 | Zbl 0765.68005

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

[10] Barthélemy, J.-P., O. Hudry, G. Isaak, F.S. Roberts et B. Tesman (1995) "The reversing number of a digraph", Discrete Applied Mathematics, 60, 39-76. | MR 1339075 | Zbl 0826.05032

[11] 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

[12] Barthélemy, J.-P. et B. Monjardet (1988) "The median procedure in data analysis : new results and open problems", in Classification and related methods of data analysis, H.H. Bock (sd), North Holland, Amsterdam. | MR 999565

[13] Berge, C. (1970) Graphes, Gauthier-Villars.

[14] Berge, C. (1987) Hypergraphes, Gauthier-Villars. | Zbl 0623.05001

[15] Bermond, J.-C. (1972) "Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux", Math. Sci. hum, 37, 5-25. | Numdam | MR 300927 | Zbl 0239.05122

[16] Bermond, J.-C. et Y. Kodratoff (1976) "Une heuristique pour le calcul de l'indice de transitivité d'un tournoi", RAIRO, 10 (3), 83-92. | Numdam | MR 416971

[17] Black, D. (1958) The theory of committees and elections, Cambridge University Press, Londres. | Zbl 0091.15706

[18] Charon-Fournier, I., A. Germa et O. Hudry (1992) "Encadrement de l'indice de Slater d'un tournoi à l'aide de ses scores", Math. Inf. Sci. hum, 118,53-68. | Numdam | Zbl 0846.05040

[19] 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. Inf. Sci. hum, 119, 53-74. | Numdam | MR 1195698 | Zbl 0845.05050

[20] Charon-Fournier, I., A. Germa et O. Hudry, "Random generation of tournaments and asymmetric digraphs with given out-degrees", à paraître dans EJOR. | Zbl 0974.05502

[21] Charon, I., A. Guénoche, O. Hudry et F. Woirgard, "A branch and bound method applied to ordinal data analysis", Actes de l' "International Conference on Ordinal and Symbolic Data Analysis" (OSDA), Springer Verlag, à paraître.

[22] Charon, I., A. Guénoche, O. Hudry et F. Woirgard, "New results on the computation of median orders", Actes du "5e Colloque International de Théorie des Graphes et Combinatoire ", soumis pour publication.

[23] Charon, I. et O. Hudry, "Lamarckian genetic algorithms applied to the search of median orders", soumis pour publication.

[24] Charon, I., O. Hudry et F. Woirgard, "A 16-vertex tournament for which Banks set and Slater set are disjoint ", soumis pour publication. | Zbl 0895.05027

[25] Chartrand, G., D. Geller et S. Hedetniemi (1971) "Graphs with forbidden subgraphs", Journal of Combinatorial Theory, 10, 1, série B, 12-41. | MR 285427 | Zbl 0223.05101

[26] 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.

[27] Cook, W.D., I. Golan et M. Kress (1988) "Heuristics for ranking players in a round robin tournament", Computers and Operations Research, 15 (2),135-144. | MR 934628

[28] Debord, B. (1987) "Caractérisation des matrices de préférences nettes et méthodes d'agrégation associées", Mathématiques et Sciences Humaines 97, 5-17. | Numdam | MR 890684 | Zbl 0619.90005

[30] De La Vega, W.F. (1983) "On the maximal cardinality of a consistent set of arcs in a random tournament", Journal of Combinatorial Theory, 35, série B, 328-332. | MR 735201 | Zbl 0531.05036

[31] Erdös, P. et J.W. Moon (1965) "On sets of consistent arcs in a tournament", Canad. Math. Bull., 8, 269-271. | MR 182574 | Zbl 0137.43301

[32] Fishburn, P. (1977) "Condorcet social choice functions", SIAM Journal of Applied Mathematics, 33, 469-489. | MR 449470 | Zbl 0369.90002

[33] Fishburn, P. (1987) "Decomposing weighted digraphs into sums of chains", Discrete Applied Mathematics, 16, 15-31. | MR 878023 | Zbl 0606.05028

[34] Garey, M.R., et D.S. Johnson (1979) Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York. | MR 519066 | Zbl 0411.68039

[35] Goddard, S.T. (1983) "Tournament rankings ", Management Science, 29 (12), 1385-1392. | MR 809110 | Zbl 0527.90047

[36] Grötschel, M., M. Jünger, G. Reinelt (1984) "A cutting plane algorithm for the linear ordering problem", Operations Research, 32, 1195-1220. | MR 775257 | Zbl 0554.90077

[37] Grötschel, M., M. Jünger, G. Reinelt (1984) "Optimal triangulation of large real-world input-output-matrices", Statistische Hefte, 25, 261-295.

[38] Grötschel, M., M. Jünger, G. Reinelt (1985) "Facets of the linear ordering polytope", Mathematical Programming, 33, 43-60. | MR 809748 | Zbl 0577.05035

[39] Guénoche, A. (1988) "Order at minimum distance of a valued tournament ", communication à Modélisation, Analyse et Agrégation des Préférences et des Choix (TRAP 3), Marseille-Luminy.

[40] Guénoche, A. (1995) "How to choose according to partial evaluations ", in Advances in Intelligent Computing, B. Bouchon-Meunier et al. (sd), IPMU'94, Lecture Notes in Computer Sciences n° 945, Springer-Verlag, Berlin-Heidelberg, 611-618.

[41] Guénoche, A. (1996) "Vainqueurs de Kemeny et tournois difficiles", Math. Inf. Sci. hum, 133; | Numdam | MR 1411799 | Zbl 0870.90096

[42] Guénoche, A., B. Vandeputte-Riboud et J.-B. Denis (1994) " Selecting varieties using a séries of trials and a combinatorial ordering method", Agronomie, 14, 363-375.

[43] Guilbaud, G.T. (1952) "Les théories de l'intérêt général et le problème logique de l'agrégation", Économie Appliquée, 5 (4), repris dans Eléments de la théorie des jeux, Dunod, Paris, 1968.

[44] Guy, R.K. (1967) "A coarseness conjecture of Erdös", Journal of Combinatorial Theory, 3, 38-42. | MR 216983 | Zbl 0149.41501

[45] Hubert, L. (1976) "Seriation using asymmetric proximity measures", Br. J. Math. Statist. Psychol., 29, 32-52. | MR 429180 | Zbl 0334.92040

[46] Hudry, O. (1989) Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires, thèse de doctorat de l'ENST, Paris.

[47] Hudry, O. (1992) "Sur le nombre d'ordres médians de certains tournois ", Actes des journées Mathématiques Discrètes et Sciences Sociales, Amiens, 56-61.

[48] 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, Irvine, États-Unis.

[49] Hudry, O. et F. Woirgard (1995) "Lower and upper bounds of the maximum number of Slater's orders of tournaments", communication au 8e Colloque Franco-Japonais/4e Colloque Franco-Chinois Combinatoire et Informatique, Brest.

[50] Isaak, G. (1995) "Tournaments as feedback arc sets", The Electronic Journal of Combinatorics, 2. | MR 1352570 | Zbl 0829.68100

[51] Jacquet-Lagrèze, É. (1969) "L'agrégation des opinions individuelles", Informatique et Sciences Humaines, 4, 1-21.

[52] Jung, H.A. (1970) "On subgraphs without cycles in a tournament", Combinatorial theory and its applications II, Balatonfüred, P. Erdös, A. Renyi et V.T. Sös (sd), Amsterdam, North-Holland, 675-677. | MR 297635 | Zbl 0207.23002

[53] Jünger, M. (1985) Polyhedral combinatorics and the acyclic subdigraph problem, Heldermann Verlag, Berlin. | MR 788691 | Zbl 0557.68045

[54] Kadane, J.B. (1966) "Some equivalence classes in paired comparisons ", Ann. math. Statist., 37, 488-494. | MR 187342 | Zbl 0171.40101

[55] Kaykobad, M., Q.N.U. Ahmed, A.T.M. Shafiqul Khalid et R.-A. Bakhtiar (1995) "A new algorithm for ranking players of a round-robin tournament", Computers and Operations Research, 22 (2), 221-226. | Zbl 0814.90147

[56] Kemeny, J.G. (1959) "Mathematics without numbers ", Daedalus, 88, 577-591.

[58] Laffond, G. et J.-F. Laslier (1991) "Slater's winners of a tournament may not be in the Banks set", Social Choice and Welfare, 8, 355-363. | MR 1129432 | Zbl 0733.90008

[59] Laffond, G., J.-F. Laslier et M. Le Breton (1991) "Choosing from a tournament : a progress report and some new results", document de travail du CNAM.

[60] Landau, H.G. (1953) "On dominance relations and the structure of animal societies III. The condition for a score structure ", Bulletin of Mathematical Biophysics, 13, 1-19. | MR 41412

[61] Laslier, J.-F. (1996) "Solutions de tournois : un spicilège", Math. Inf. Sci. hum, 133. | Numdam | MR 1411797 | Zbl 0870.90014

[62] Lenstra, J.K. (1977) Sequencing by enumerative methods, Mathematical Centre Tracts n° 69, Mathematisch Centrum, Amsterdam. | MR 443968 | Zbl 0407.90025

[63] Marcotorchino, J.-F. et P. Michaud (1979) Optimisation en analyse ordinale de données, Masson, Paris.

[64] Miller, N. (1980) "A new solution set for tournaments and majority voting : Further graph-theoretical approaches to the theory of voting", American Journal of Political Science, 24 (1), 68-96.

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

[66] Monjardet, B. (1990) "Sur diverses formes de la "règle de Condorcet" d'agrégation des préférences", Math. Inf. Sci. hum, 111, 61-71. | Numdam | MR 1082274 | Zbl 0723.01012

[67] Moon, J.W. (1968) Topics on tournaments, Holt, Rinehart and Winston. | MR 256919 | Zbl 0191.22701

[68] Phillips, J.P.N. (1976) "On an algorithm of Smith and Payne for determining Slater's i and all nearest adjoining orders ", British Journal of Mathematical and Statistical Psychology, 29, 126-127.

[69] Poljak, S., V. Rödl et J. Spencer (1988) "Tournament ranking with expected profit in polynomial time", SIAM Journal Disc Math, 1 (3), 372-376. | MR 955653 | Zbl 0667.05030

[70] Poljak, S. et D. Turzik (1986) "A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound", Discrete Mathematics, 58, 99-104. | MR 820844 | Zbl 0585.05032

[71] Reid, K.B. (1969) "On set of arcs containing no cycles in tournaments", Canad. Math. Bull., 12, 261-264. | MR 250926 | Zbl 0181.51901

[72] Reinelt, G. (1985) The linear ordering problem : algorithms and applications, Research and Exposition in Mathematics 8, Heldermann Verlag, Berlin. | MR 831936 | Zbl 0565.68058

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

[74] Slater, P. (1961) "Inconsistencies in a schedule of paired comparisons", Biometrika, 48, 303-312.

[75] 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.

[76] Spencer, J. (1971) "Optimal ranking of tournaments ", Networks 1, 135-138. | MR 299532 | Zbl 0236.05110

[77] Spencer, J. (1978) "Nonconstructive methods in discrete mathematics ", in Studies in Combinatorics, G.C. Rota (sd), Mathematical Association of America, Washington DC, 142-178. | MR 513005 | Zbl 0407.05001

[78] Spencer, J. (1987) Ten lectures on the probabilistic method, CBMS-NSF Regional Conference Series in Applied Mathematics N° 52, SIAM, Philadelphie, États-Unis. | MR 929258 | Zbl 0703.05046

[79] Szele, T. (1943) "Kombinatorikai vizsgálatok az iránított teljes gráffal kapesolatban", Mat. Fiz. Lapok., 50, 223-256, traduit en allemand sous le titre " Untersuchungen über gerichtete vollständige Graphen", Publ. Math. Debrecen, 13 (1966), 145-168. | Zbl 0178.57703

[80] Thomassen, C. (1987) "Counterexamples to Adám's conjecture on arc reversals in directed graphs", Journal of Combinatorial Theory, 42, série B, 128-130. | MR 872413 | Zbl 0609.05041

[81] Younger, D.H. (1963) "Minimum feedback arc sets for a directed graph", IEEE Trans. of the profes. tech. group in circuit theory, 10 (2), 238-245.