Re: [math-fun] optimal advance tournament scheduling
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@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@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.
To generate inequivalent graphs, use either genreg or nauty/geng; either should work fine (although I find genreg to be faster, even though nauty is better known). -tom On Tue, Jun 18, 2019 at 9:05 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
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@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@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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Quoting "Keith F. Lynch" <kfl@KeithLynch.net>:
(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.)
I implicitly used most of the N <=> 26-N symmetry. I varied the center cell C from 1...13 (only), and reported the total count of 5x5 magic squares for each center value. Then I doubled the total for C = 1...12 and added the count for C=13. This saved about half the time. I decided not to use the value symmetry for C=13: It complicates the program, and increases the chance of an undetected bug. You can only use some of the row (and column) permutations: You can permute the rows in the left half (minus the center row if N is odd), and do the mirror permuation in the right half. Then follow up by choosing some (or none or all) rows in the left half, and exchange each with its mirror row in the right half. Then do the same things to the columns. A curious consequence of the center row (and column) being fixed in the center, is that the size of the group of allowed permutations is the same when N=2K or 2K+1. Rich
There are only 6 non-isomorphic 4-regular (quartic) 8-node graphs. They are listed here, as generated by genreg (after some minor editing). Taillenweite is diameter. Graph 1: 1 : 2 3 4 5 2 : 1 3 4 5 3 : 1 2 6 7 4 : 1 2 6 8 5 : 1 2 7 8 6 : 3 4 7 8 7 : 3 5 6 8 8 : 4 5 6 7 Taillenweite: 3 Graph 2: 1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 4 7 4 : 1 2 3 8 5 : 1 6 7 8 6 : 2 5 7 8 7 : 3 5 6 8 8 : 4 5 6 7 Taillenweite: 3 Graph 3: 1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 5 7 4 : 1 2 6 8 5 : 1 3 7 8 6 : 2 4 7 8 7 : 3 5 6 8 8 : 4 5 6 7 Taillenweite: 3 Graph 4: 1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 5 7 4 : 1 2 7 8 5 : 1 3 6 8 6 : 2 5 7 8 7 : 3 4 6 8 8 : 4 5 6 7 Taillenweite: 3 Graph 5: 1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 7 8 4 : 1 2 7 8 5 : 1 6 7 8 6 : 2 5 7 8 7 : 3 4 5 6 8 : 3 4 5 6 Taillenweite: 3 Graph 6: 1 : 2 3 4 5 2 : 1 6 7 8 3 : 1 6 7 8 4 : 1 6 7 8 5 : 1 6 7 8 6 : 2 3 4 5 7 : 2 3 4 5 8 : 2 3 4 5 Taillenweite: 4 On Tue, Jun 18, 2019 at 9:05 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
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@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@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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Some quick observations: given two players who are adjacent in the ordering, we cannot tell who is stronger if they do not actually play one another; this means that a tournament schedule without a Hamiltonian path can never give enough information to reconstruct the entire ordering. It also means that an incomplete tournament schedule can never guarantee reconstruction of the full ordering. On Wed, Jun 19, 2019 at 10:46 AM Tomas Rokicki <rokicki@gmail.com> wrote:
There are only 6 non-isomorphic 4-regular (quartic) 8-node graphs. They are listed here, as generated by genreg (after some minor editing). Taillenweite is diameter.
Graph 1:
1 : 2 3 4 5 2 : 1 3 4 5 3 : 1 2 6 7 4 : 1 2 6 8 5 : 1 2 7 8 6 : 3 4 7 8 7 : 3 5 6 8 8 : 4 5 6 7 Taillenweite: 3
Graph 2:
1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 4 7 4 : 1 2 3 8 5 : 1 6 7 8 6 : 2 5 7 8 7 : 3 5 6 8 8 : 4 5 6 7 Taillenweite: 3
Graph 3:
1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 5 7 4 : 1 2 6 8 5 : 1 3 7 8 6 : 2 4 7 8 7 : 3 5 6 8 8 : 4 5 6 7 Taillenweite: 3
Graph 4:
1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 5 7 4 : 1 2 7 8 5 : 1 3 6 8 6 : 2 5 7 8 7 : 3 4 6 8 8 : 4 5 6 7 Taillenweite: 3
Graph 5:
1 : 2 3 4 5 2 : 1 3 4 6 3 : 1 2 7 8 4 : 1 2 7 8 5 : 1 6 7 8 6 : 2 5 7 8 7 : 3 4 5 6 8 : 3 4 5 6 Taillenweite: 3
Graph 6:
1 : 2 3 4 5 2 : 1 6 7 8 3 : 1 6 7 8 4 : 1 6 7 8 5 : 1 6 7 8 6 : 2 3 4 5 7 : 2 3 4 5 8 : 2 3 4 5 Taillenweite: 4
On Tue, Jun 18, 2019 at 9:05 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
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@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@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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Keith F. Lynch -
Michael Collins -
rcs＠xmission.com -
Tomas Rokicki