I'm thinking out loud (silently, since this is typing, not talking)
about how to program the "optimal advance tournament scheduling"
problem. Partly to clarify my own thoughts, and partly in hopes
that someone else will find any errors or come up with better ideas.
(For instance Mike Beeler noticed I said, and looked up, "trivalent"
when I meant "tetravalent." Thanks.)
First, I've decided not to bother excluding non-connected graphs,
as there are so few that it would take more time to exclude them
than getting rid of them would save.
We're only dealing with graphs that have 8 vertices and 16 edges. How
can such a graph be non-connected? Can it have 4 vertices in each
piece? No. A complete graph on 4 vertices is 6 edges, for a total of
12. (I didn't mention earlier, as it was too obvious, that no player
will play more than one game with each other player, as the additional
game would provide no new information.) What about 5 and 3? Still
no, as the complete graphs on 5 and 3 have a total of 13 edges.
What about 6 and 2? Yes, but there's only one such graph; it consists
of the complete graphs of 6 and 2 vertices. And the score of that
is 16, regardless of which players are in which positions, since we
have complete information about the ordering of the 6 and complete
information about the ordering of the other 2, but no information that
relates any of the former to either of the latter, and 28 - 2*6 = 16.
Knowing the score of that arrangement will be a useful test of my
program.
What about 7 and 1? Yes. There are at most (21 choose 16)*8 labeled
graphs. That's 162792, a very small proportion of the 30421755 total
labeled graphs, about 1/187. (Both numbers are actually smaller, as
I'm ignoring symmetries.)
What about graphs in more than two pieces? There aren't any. Not
with 8 vertices and 16 edges.
All graphs will always be represented by an 8x8 matrix with a 1 at
both A,B and B,A meaning that A and B play a game, and 0 in both those
locations meaning that they don't. There will be 16 1s and 12 0s
in each half of the (symmetric) matrix, excluding the main diagonal
(whose contents are irrelevant).
Or, if it's a directed graph, with a 1 at A,B and a 0 at B,A meaning
that A won a game against B, a 1 at B,A and a 0 at A,B meaning that B
won a game against A, a 0 in both locations if they didn't play each
other, and a 1 in both locations if there's a bug in my program.
I can see two main approaches. I can generate all 30-million+ labeled
graphs. In each case each vertex number will be the same as the
player rank number. I need to solve each of them, by placing an arrow
on each edge, from the stronger (lower numbered) to the weaker (higher
numbered) player. I then raise that directed-graph non-symmetric
matrix to every power, 1 through 7, add those 7 matrices together, and
subtract the number of 0s in the sum matrix (other than those on the
main diagonal) from 28 to get the score. After doing that with all 30
million+, I average the scores over the equivalent graphs, i.e. those
which are identical except for the labels on the vertices, i.e. those
whose non-directed matrices are identical under a permutation of the
rows combined with an identical permutation of the columns.
The other approach is to somehow generate only one of each equivalent
graph. I could then try all 8! ways of assigning player rank numbers
to vertex numbers (instead of those numbers always being the same),
and figure out the score of each of them by the above method, then
take the average of the scores. But I can get away with only trying
8!/2 ways, doubling the speed, due to symmetry. If I always put
player 1 on one of vertices 1 through 4 rather than 5 through 8, I
don't lose any information, since I'm only excluding mirror-image
arrangements, in which the players are ranked in the opposite order,
and those have the exact same scores.
(Digression: Decades ago I noticed these same two kinds of symmetries
in magic squares. How many order-4 magic squares with numbers 1-16
(or 0-15, or any other 16 equally spaced numbers) are there? The
number usually given is 880, in which rotations and reflection are
allowed. But you can permute the rows if you permute the columns the
same way. That brings it down to 220. But there's also a very
different kind of magic-preserving symmetry: Reverse the order of the
numbers. That doesn't knock it down to 110, however, due to a broken
symmetry, i.e. that transform sometimes links an arrangement back to
a permutation of itself rather than to a distinct arrangement. If
I recall correctly, it knocks it down to 166. I recall that at
about the same time I was counting 4x4 magic square, our listmaster
was doing the same with 5x5. I recall reading that he used the
row-permutation symmetry, but I don't know whether he also used the
number reversal symmetry.)
While I'm averaging the scores of the equivalent graphs, I can also
keep track of whether the maximum score of any of them is always 28,
(and if it's not, whether it's because I've stumbled into one of the
few non-connected graphs), and what the minimum score is, and any
other statistic anyone is interested in, within reason.
So, how can I find only one of each set of equivalent graphs?
I can put the 12 0s and 16 1s in the upper right half of the
(non-directional, symmetric) matrix in order, left to right, top to
bottom, to make a unique 28-bit number, and define the canonical one
as being the smallest in the equivalence class, but that doesn't
help me *generate* it, as contrasted with generating all 30-million+
matrices and discarding most of them.
And now to catch up on replies in this thread:
Mike Beeler <mikebeeler2(a)gmail.com> wrote:
> In the real world, there could be a further scheduling criteria
> about ?exhaustion?, if an otherwise worse player can beat a better
> player if the better player has played more games.
Exhaustion isn't an issue if, as I suspect Dan meant, every player is
playing simultaneously. Also, it contradicts my arbitrary axioms of
consistency and transitivity.
> Even further, the games each has played perhaps should be weighted
> by the (estimated) strength of the opponent.
Estimated by whom, how? We have no information about any of the
players other than whom they beat and whom they are beaten by in this
16-game tournament.
> I agree, there might be some graphs that suck. That is, the graph
> is all in one piece, but no outcome of the games allows a complete
> ranking of all the players. In Dan?s case of 8 players and 16
> games, it is merely my intuition that there are no such graphs.
I tried, with pen and paper, to find a connected graph without a
non-looping path of length 7. Perhaps a stellate graph, in which
several short loops emanate from one very busy player? I wasn't able
to find one. But then I didn't try very hard. Any graph with a
non-looping path of length 7 will have a perfect score for at least
two possible rankings of players. And graphs without such a path, if
any exist, might have a perfect score anyway. It's one more thing to
have my program check for.
Mike Beeler <mikebeeler2(a)gmail.com> wrote:
> Indeed, my concern is with the definition of "the maximum
> information = about player's strengths=E2=80=9D, as Dan put it.
> In a competition, it = may be more important to identify the top
> player(s) than to obtain the = maximum information theoretic
> information.
If so, the organizer would have arranged the tournament to seek that
information, by repeatedly choosing the winners of each game and
pitting them against each other. But Dan said that who plays whom
doesn't depend on who wins which games, so I conclude that the
organizer doesn't care more about who is the best player than about
the rankings of the other players.
