Deciding the validity of the score sequence of a soccer tournament

Definitions and mathematical statement

Fix $n\ge1$ labelled teams. Each unordered pair plays exactly once. The possible contributions of the match between $i$ and $j$ to their respective scores are $(3,0)$, $(0,3)$, or $(1,1)$, corresponding to a win, a loss, or a draw. Given nonnegative integers $s_1,\ldots,s_n$, decide whether all matches can be assigned outcomes so that team $i$ receives exactly $s_i$ points.

More formally, for each $i<j$ choose $(a_{ij},a_{ji})\in\{(3,0),(0,3),(1,1)\}$ and require \[ \sum_{j\ne i}a_{ij}=s_i \quad(1\le i\le n). \] Is there a deterministic polynomial-time algorithm for this decision problem, and for producing an outcome table when one exists? The scores are given in binary; immediate infeasibility bounds such as $s_i\le3(n-1)$ can be checked first.

No match outcomes are fixed beforehand. Allowing an arbitrary partially played schedule as additional input is a different, more constrained problem. The total score determines the number of drawn matches: if $m=\binom n2$, that number must equal $3m-\sum_i s_i$. This necessary aggregate condition does not specify how the individual scores can be simultaneously realized by pairwise matches.

Short English statement

Can one efficiently decide whether prescribed team scores are possible in a complete soccer tournament with three points for a win and one for a draw?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000026 (AMR-029-0026), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Deciding the validity of the score sequence of a soccer tournament. Original source indexed by AMR-029-0026. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Deciding the validity of the score sequence of a soccer tournament. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Deciding_the_validity_of_the_score_sequence_of_a_soccer_tournament.