Comment déterminer efficacement si une échelle donnée est valide?

Dans mon club de squash local, il y a une échelle qui fonctionne comme suit.

1. Au début de la saison, nous construisons une table avec le nom de chaque membre du club sur une ligne distincte.
2. Nous écrivons ensuite le nombre de parties gagnées et le nombre de parties jouées à côté de chaque nom (sous la forme: joueur gagne / parties).

Ainsi en début de saison la table ressemble à ceci:

Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0

Deux joueurs peuvent jouer un match, un joueur gagnant. Si le joueur le plus proche du bas de la table gagne, alors la position des joueurs est changée. Nous répétons ensuite l'étape 2., en mettant à jour le nombre de victoires et de jeux à côté de chaque joueur. Par exemple, si Alice bat Billy, nous avons

Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0

Ces matchs se poursuivent tout au long de la saison et finissent par entraîner l'inscription des joueurs dans l'ordre de force approximatif.

Malheureusement, la mise à jour se fait de manière plutôt aléatoire, donc des erreurs sont commises. Voici quelques exemples de tableaux invalides, c'est-à-dire des tableaux qui n'ont pas pu être produits en suivant correctement les étapes ci-dessus pour un ordre de départ (nous avons oublié l'ordre que nous avons utilisé au début de la saison) et la séquence des matchs et des résultats:

Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0

Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0

Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1

Étant donné un tableau, comment pouvons-nous déterminer efficacement s'il est valide? Nous pourrions commencer par noter ce qui suit:

1. L'ordre des noms n'a pas d'importance, car nous avons oublié l'ordre de départ d'origine.

2. Le nombre total de victoires doit correspondre à la moitié du nombre de parties jouées. (Cela montre que le premier exemple ci-dessus n'est pas valide.)

3. Supposons que la table soit valide. Ensuite, il y a un multigraphe - un graphique admettant plusieurs bords mais pas de boucles - avec chaque sommet correspondant à un joueur et chaque bord à un match joué. Ensuite, le nombre total de parties jouées par chaque joueur correspond au degré du sommet du joueur dans le multigraphe. Donc, s'il n'y a pas de multigraph avec les degrés de sommet appropriés, le tableau doit être invalide. Par exemple, il n'y a pas de multigraphe avec un sommet de degré un et un de degré trois, le deuxième exemple n'est donc pas valide. [Nous pouvons vérifier efficacement l'existence d'un tel multigraphe.]

Nous avons donc deux vérifications que nous pouvons appliquer pour commencer, mais cela permet toujours des tables invalides, comme le troisième exemple. Pour voir que cette table n'est pas valide, nous pouvons travailler en arrière, en épuisant toutes les manières possibles dont la table aurait pu apparaître.

Je me demandais si quelqu'un pouvait penser à un algorithme de temps polynomial (en nombre de joueurs et en nombre de jeux) pour résoudre ce problème de décision?

Ce n'est pas une réponse complète. Je donne un énoncé plus simple du problème et quelques remarques.

Nous commençons par un graphe où les sommets sont étiquetés avec .$[n]$

$v$$u$$label(v)<label(u)$

$G$$n$$e$

$\mathsf{NP}$$G$

Observation

$label(v)$$v$$v$

Je pense qu'il devrait être possible de combiner cette observation avec Havel-Hakimi pour donner un algorithme de temps polynomial.

Je n'ai pas résolu le problème, mais j'ai des résultats partiels, dont les déclarations sont données ci-dessous. J'écrirai les épreuves si quelqu'un est intéressé.

Proposition . Supposons que l'échelle (1) contient plus d'un joueur (2) contient un nombre égal de victoires et de pertes; et (3) est tel que chaque joueur a gagné au moins un match et perdu au moins un match. Ensuite, l'échelle est valide.

$W_i$$i$$L_i$$i$$R_i$ le rang (où le plus haut est le mieux).

Proposition (due à Fabio Parisi) . Si et l'échelle est valide, alors W i ≤ ∑ k : R k > R i , W k > $L_i=0$