[math-fun] (Second try) optimal advance tournament scheduling
Second try: Sorry about not writing this up better the first time. ººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººº Suppose we want to invent a schedule of matchups for 8 players, meeting in 4 sessions of head-to-head pairings — so after all 4 sessions (and 16 games in all) *the maximum information about player's strengths* can be extracted from the results. (In some sense!) (The schedule is to be decided in advance, independent of any tournament outcomes.) I'd guess you want to *ensure* that the "versus graph" edges connect those nodes who've played each other) is, by the end, in just one piece. But what else might be important? Note: To simplify the problem, assume that the entire schedule of play is determined in advance, and is independent of any outcomes. E.g., for 8 players and 4 sessions ((n,s) = (8,4)), one could label each vertex of a regular octagon with the players' names and use each of the 4 families of parallel lines between pairs of vertices as the matchup schedule for one of the 4 sessions. Here's an alternative schedule: Instead of an octagon, use the 8 vertices of a cube, 3 of whose matchups can each be defined by one family of parallel edges of the cube; the 4th matchup could be between endpoints of each great diagonal. Is one of these better than the other for extracting the best guess as to players' relative rankings? (If they're combinatorially equivalent (CE), then of course they're equal in information content, but CE-ness looks unlikely.) —Dan P.S. In order to truly solve this problem, we'd have to define it first: In what *sense* is an optimal schedule optimal? And what about (n,s) ≠ (8,4) ?
Octagon with parallel lines pairing, versus cube with edges and great diagonals... These look to me topologically identical. Am I missing something? (E.g., number octagon vertices clockwise 1, 2, 6, 5, 4, 3, 7, 8; number cube’s top corners clockwise 1, 2, 3, 4 and bottom corners below those in order 5, 6, 8, 7. Pairs in each are (1, 2), (1, 3), (1, 5), (1, 8), (2, 4), (2, 6), (2, 7), (3, 4), (3, 6), (3, 7), (4, 5), (4, 8), (5, 6), (5, 7), (6, 8), (7, 8).) — Mike
On Jun 15, 2019, at 9:54 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Second try: Sorry about not writing this up better the first time. ººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººº
Suppose we want to invent a schedule of matchups for 8 players, meeting in 4 sessions of head-to-head pairings — so after all 4 sessions (and 16 games in all)
*the maximum information about player's strengths*
can be extracted from the results. (In some sense!)
(The schedule is to be decided in advance, independent of any tournament outcomes.)
I'd guess you want to *ensure* that the "versus graph" edges connect those nodes who've played each other) is, by the end, in just one piece.
But what else might be important?
Note: To simplify the problem, assume that the entire schedule of play is determined in advance, and is independent of any outcomes.
E.g., for 8 players and 4 sessions ((n,s) = (8,4)), one could label each vertex of a regular octagon with the players' names and use each of the 4 families of parallel lines between pairs of vertices as the matchup schedule for one of the 4 sessions.
Here's an alternative schedule: Instead of an octagon, use the 8 vertices of a cube, 3 of whose matchups can each be defined by one family of parallel edges of the cube; the 4th matchup could be between endpoints of each great diagonal.
Is one of these better than the other for extracting the best guess as to players' relative rankings?
(If they're combinatorially equivalent (CE), then of course they're equal in information content, but CE-ness looks unlikely.)
—Dan
P.S. In order to truly solve this problem, we'd have to define it first: In what *sense* is an optimal schedule optimal?
And what about (n,s) ≠ (8,4) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
These are identical; the horizontally extreme points in the octagon are the top of the cube, and the vertically extreme points in the octagon are the bottom of the cube. On Sun, Jun 16, 2019 at 11:47 AM Mike Beeler <mikebeeler2@gmail.com> wrote:
Octagon with parallel lines pairing, versus cube with edges and great diagonals...
These look to me topologically identical. Am I missing something?
(E.g., number octagon vertices clockwise 1, 2, 6, 5, 4, 3, 7, 8; number cube’s top corners clockwise 1, 2, 3, 4 and bottom corners below those in order 5, 6, 8, 7. Pairs in each are (1, 2), (1, 3), (1, 5), (1, 8), (2, 4), (2, 6), (2, 7), (3, 4), (3, 6), (3, 7), (4, 5), (4, 8), (5, 6), (5, 7), (6, 8), (7, 8).)
— Mike
On Jun 15, 2019, at 9:54 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Second try: Sorry about not writing this up better the first time. ººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººººº
Suppose we want to invent a schedule of matchups for 8 players, meeting in 4 sessions of head-to-head pairings — so after all 4 sessions (and 16 games in all)
*the maximum information about player's strengths*
can be extracted from the results. (In some sense!)
(The schedule is to be decided in advance, independent of any tournament outcomes.)
I'd guess you want to *ensure* that the "versus graph" edges connect those nodes who've played each other) is, by the end, in just one piece.
But what else might be important?
Note: To simplify the problem, assume that the entire schedule of play is determined in advance, and is independent of any outcomes.
E.g., for 8 players and 4 sessions ((n,s) = (8,4)), one could label each vertex of a regular octagon with the players' names and use each of the 4 families of parallel lines between pairs of vertices as the matchup schedule for one of the 4 sessions.
Here's an alternative schedule: Instead of an octagon, use the 8 vertices of a cube, 3 of whose matchups can each be defined by one family of parallel edges of the cube; the 4th matchup could be between endpoints of each great diagonal.
Is one of these better than the other for extracting the best guess as to players' relative rankings?
(If they're combinatorially equivalent (CE), then of course they're equal in information content, but CE-ness looks unlikely.)
—Dan
P.S. In order to truly solve this problem, we'd have to define it first: In what *sense* is an optimal schedule optimal?
And what about (n,s) ≠ (8,4) ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ 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/ --
participants (3)
-
Dan Asimov -
Mike Beeler -
Tomas Rokicki