Tournament Structures

Discuss anything you like about chess related matters in this forum.
Brian Valentine
Posts: 430
Joined: Fri Apr 03, 2009 1:30 pm

Re: Tournament Structures

Post by Brian Valentine » Wed Apr 11, 2018 2:51 pm

I'm not sure that I understand the underlying assumptions in either Alex's or Chris' thinking, so I'll pitch in to see whether we can get to the bottom of it.

I think Alex is assuming that the seeding is correct. I can't see how his routes can be otherwise derived. I doubt correct ranking is possible and even if it was then in the bottom half the rankings would be a narrower span of prize winning odds.

The other issue seems to be fairness which has not been nailed down. My attempt at defining this would be something like: the pairing methodology does not significantly affect ones chances of winning relative to prior expectation. Getting back to earlier parts of the thread this might be widened from winning to being placed in the first k places.

Alex Holowczak
Posts: 8880
Joined: Sat May 30, 2009 5:18 pm
Location: Oldbury, Worcestershire
Contact:

Re: Tournament Structures

Post by Alex Holowczak » Wed Apr 11, 2018 3:24 pm

Brian Valentine wrote:
Wed Apr 11, 2018 2:51 pm
I think Alex is assuming that the seeding is correct. I can't see how his routes can be otherwise derived. I doubt correct ranking is possible and even if it was then in the bottom half the rankings would be a narrower span of prize winning odds.
Yes, I am assuming the seeding is correct. The seeding is based on Elo rating in the case of chess (just like it is in any chess tournament format), and the world rankings in the case of snooker with the exception of 1 and 2.

I'm saying that it is noticeable with the pairing system those two events employ that beyond about seed 32, seed and route difficulty do not have a linear relationship. Therefore, those seeds should probably be placed randomly in the bracket, rather than in strict seeding order. I can send you the graph if you like. :)

User avatar
Chris Goodall
Posts: 333
Joined: Sun Oct 10, 2010 6:40 pm
Contact:

Re: Tournament Structures

Post by Chris Goodall » Wed Apr 11, 2018 3:40 pm

Alex Holowczak wrote:
Wed Apr 11, 2018 1:28 pm
Chris Goodall wrote:
Wed Apr 11, 2018 11:23 am
Alex Holowczak wrote:
Wed Apr 11, 2018 10:20 am
You're right that it would favour the best teams/players though - that's precisely the point of re-seeding.
So why is that a desirable thing to do? The fact that you're holding a chess tournament and not a darts tournament favours the best chess players. They're already the most likely to win, because they're the best at the skill that you're measuring. The best possible tournament is one in which their greater likelihood of winning is exactly in proportion to their greater skill, no less and no more. Just as the ideal tournament shouldn't compress differences in strength, neither should it stretch them.
In which case, you might as well just pair any tournament completely randomly, and not seed anything.
Nope. Slippery Slope Fallacy. You could turn that around and say you "might as well" give the top seed a bye into the final, if you want to make their life easier.
Alex Holowczak wrote:
Wed Apr 11, 2018 1:28 pm
You're focusing on the impact of the 1, rather than the field. I think it's reasonable that in a seeded knockout tournament, the 1 gets an easier route than the 128. I mean, the 1 never has to play the 1, for starters, which makes it easier than every other seed. If you seed all 128 players, and you would expect the 1 to have the easiest route and 128 to have the hardest route, you might expect a nice straight line connecting the two together. But you don't, you get a graph with curves and changes of direction. Why should seed 90 have a harder route than seed 120? I don't think that's a feature of what one might describe as "the ideal tournament".
Because you're not doing the maths properly. You're adding the numbers together as if they're time-invariant. But the round in which you're expected to face seed p has a significant bearing on your probability of actually facing seed p in that round. If you're seeded 128, you've got a 100% chance of facing the top seed in round 1. There's no possible way of getting out of it, even if the top seed only has 1 pair of shorts. If you're one of the 64 players in the opposite half of the draw to the top seed, your chance of facing the top seed in the final is significantly less than 100%, because of the significant possibility that someone in the preceding 6 rounds will have knocked off the top seed for you, as indeed Xiangzhi did to Carlsen in round 3.
Chris Goodall, formerly known as Chris Wardle. ECF Grader for the ancient kingdom of Bernicia (or Northumberland and Durham, if you prefer). And now also Darlington. And the NCCU.
Newcastle is not in Scotland!

Alex Holowczak
Posts: 8880
Joined: Sat May 30, 2009 5:18 pm
Location: Oldbury, Worcestershire
Contact:

Re: Tournament Structures

Post by Alex Holowczak » Wed Apr 11, 2018 3:50 pm

Chris Goodall wrote:
Wed Apr 11, 2018 3:40 pm
Alex Holowczak wrote:
Wed Apr 11, 2018 1:28 pm
Chris Goodall wrote:
Wed Apr 11, 2018 11:23 am
So why is that a desirable thing to do? The fact that you're holding a chess tournament and not a darts tournament favours the best chess players. They're already the most likely to win, because they're the best at the skill that you're measuring. The best possible tournament is one in which their greater likelihood of winning is exactly in proportion to their greater skill, no less and no more. Just as the ideal tournament shouldn't compress differences in strength, neither should it stretch them.
In which case, you might as well just pair any tournament completely randomly, and not seed anything.
Nope. Slippery Slope Fallacy. You could turn that around and say you "might as well" give the top seed a bye into the final, if you want to make their life easier.
You mean like the World Championship, where chess does exactly that? :wink:
Chris Goodall wrote:
Wed Apr 11, 2018 3:40 pm
Alex Holowczak wrote:
Wed Apr 11, 2018 1:28 pm
You're focusing on the impact of the 1, rather than the field. I think it's reasonable that in a seeded knockout tournament, the 1 gets an easier route than the 128. I mean, the 1 never has to play the 1, for starters, which makes it easier than every other seed. If you seed all 128 players, and you would expect the 1 to have the easiest route and 128 to have the hardest route, you might expect a nice straight line connecting the two together. But you don't, you get a graph with curves and changes of direction. Why should seed 90 have a harder route than seed 120? I don't think that's a feature of what one might describe as "the ideal tournament".
Because you're not doing the maths properly. You're adding the numbers together as if they're time-invariant. But the round in which you're expected to face seed p has a significant bearing on your probability of actually facing seed p in that round. If you're seeded 128, you've got a 100% chance of facing the top seed in round 1. There's no possible way of getting out of it, even if the top seed only has 1 pair of shorts. If you're one of the 64 players in the opposite half of the draw to the top seed, your chance of facing the top seed in the final is significantly less than 100%, because of the significant possibility that someone in the preceding 6 rounds will have knocked off the top seed for you, as indeed Xiangzhi did to Carlsen in round 3.
This is true, but if you were to have percentages as the probability of which seed gets to the Final, then 1 would be at the top of the list; even if that number would be < 50%.

I think it would be possible to tweak my spreadsheet to reflect the odds based on the Elo ratings of the players who entered. If you then ran 1000 simulations using those odds, you might get another useful piece of information. But that's beyond both my Excel skills and time available...

User avatar
Chris Goodall
Posts: 333
Joined: Sun Oct 10, 2010 6:40 pm
Contact:

Re: Tournament Structures

Post by Chris Goodall » Wed Apr 11, 2018 4:12 pm

Alex Holowczak wrote:
Wed Apr 11, 2018 3:50 pm
Chris Goodall wrote:
Wed Apr 11, 2018 3:40 pm
Alex Holowczak wrote:
Wed Apr 11, 2018 1:28 pm


In which case, you might as well just pair any tournament completely randomly, and not seed anything.
Nope. Slippery Slope Fallacy. You could turn that around and say you "might as well" give the top seed a bye into the final, if you want to make their life easier.
You mean like the World Championship, where chess does exactly that? :wink:
Except Carlsen doesn't get a bye into the final by being the top seed, does he. He get a bye into the final by being the previous champion. You can't compare the two.
Alex Holowczak wrote:
Wed Apr 11, 2018 3:50 pm
Chris Goodall wrote:
Wed Apr 11, 2018 3:40 pm
Alex Holowczak wrote:
Wed Apr 11, 2018 1:28 pm
You're focusing on the impact of the 1, rather than the field. I think it's reasonable that in a seeded knockout tournament, the 1 gets an easier route than the 128. I mean, the 1 never has to play the 1, for starters, which makes it easier than every other seed. If you seed all 128 players, and you would expect the 1 to have the easiest route and 128 to have the hardest route, you might expect a nice straight line connecting the two together. But you don't, you get a graph with curves and changes of direction. Why should seed 90 have a harder route than seed 120? I don't think that's a feature of what one might describe as "the ideal tournament".
Because you're not doing the maths properly. You're adding the numbers together as if they're time-invariant. But the round in which you're expected to face seed p has a significant bearing on your probability of actually facing seed p in that round. If you're seeded 128, you've got a 100% chance of facing the top seed in round 1. There's no possible way of getting out of it, even if the top seed only has 1 pair of shorts. If you're one of the 64 players in the opposite half of the draw to the top seed, your chance of facing the top seed in the final is significantly less than 100%, because of the significant possibility that someone in the preceding 6 rounds will have knocked off the top seed for you, as indeed Xiangzhi did to Carlsen in round 3.
This is true, but if you were to have percentages as the probability of which seed gets to the Final, then 1 would be at the top of the list; even if that number would be < 50%.
Of course 1 would top the list, but the list isn't important: any percentage less than 100% means that facing 1 in the final is an advantage over facing 1 in the first round. It could be <50% or it could be 99%.
Chris Goodall, formerly known as Chris Wardle. ECF Grader for the ancient kingdom of Bernicia (or Northumberland and Durham, if you prefer). And now also Darlington. And the NCCU.
Newcastle is not in Scotland!

Alex Holowczak
Posts: 8880
Joined: Sat May 30, 2009 5:18 pm
Location: Oldbury, Worcestershire
Contact:

Re: Tournament Structures

Post by Alex Holowczak » Wed Apr 11, 2018 4:23 pm

Chris Goodall wrote:
Wed Apr 11, 2018 4:12 pm
Alex Holowczak wrote:
Wed Apr 11, 2018 3:50 pm
Chris Goodall wrote:
Wed Apr 11, 2018 3:40 pm

Nope. Slippery Slope Fallacy. You could turn that around and say you "might as well" give the top seed a bye into the final, if you want to make their life easier.
You mean like the World Championship, where chess does exactly that? :wink:
Except Carlsen doesn't get a bye into the final by being the top seed, does he. He get a bye into the final by being the previous champion. You can't compare the two.
You can - the UK Snooker Championship decides to award its number 1 seed to the defending champion, irrespective of his ranking. You could reasonably argue that the Chess World Champion awards its defending champion the number 1 seed, and therefore gives him a bye into the Final.

User avatar
Chris Goodall
Posts: 333
Joined: Sun Oct 10, 2010 6:40 pm
Contact:

Re: Tournament Structures

Post by Chris Goodall » Wed Apr 11, 2018 5:28 pm

Alex Holowczak wrote:
Wed Apr 11, 2018 4:23 pm
Chris Goodall wrote:
Wed Apr 11, 2018 4:12 pm
Alex Holowczak wrote:
Wed Apr 11, 2018 3:50 pm

You mean like the World Championship, where chess does exactly that? :wink:
Except Carlsen doesn't get a bye into the final by being the top seed, does he. He get a bye into the final by being the previous champion. You can't compare the two.
You can - the UK Snooker Championship decides to award its number 1 seed to the defending champion, irrespective of his ranking. You could reasonably argue that the Chess World Champion awards its defending champion the number 1 seed, and therefore gives him a bye into the Final.
If you insist.
Alex Holowczak wrote:
Wed Apr 11, 2018 3:50 pm
I think it would be possible to tweak my spreadsheet to reflect the odds based on the Elo ratings of the players who entered. If you then ran 1000 simulations using those odds, you might get another useful piece of information. But that's beyond both my Excel skills and time available...
You wouldn't need to simulate; you could sum expected strength (defined in terms of seeding) up through the tree. For example, in a 128-player tournament, if for some reason every match was a coin flip, on average the tournament would be won by the 64½th seed. If every match was a comparison of seeding, on average the tournament would be won by the 1st seed. Some outcome function in between those two extremes (say, Zipf's law), would give you some expected winner in between those two extremes.
Chris Goodall, formerly known as Chris Wardle. ECF Grader for the ancient kingdom of Bernicia (or Northumberland and Durham, if you prefer). And now also Darlington. And the NCCU.
Newcastle is not in Scotland!

User avatar
Chris Goodall
Posts: 333
Joined: Sun Oct 10, 2010 6:40 pm
Contact:

Re: Tournament Structures

Post by Chris Goodall » Wed Apr 11, 2018 11:06 pm

Alex Holowczak wrote:
Wed Apr 11, 2018 3:50 pm
Chris Goodall wrote:
Wed Apr 11, 2018 3:40 pm
Because you're not doing the maths properly. You're adding the numbers together as if they're time-invariant. But the round in which you're expected to face seed p has a significant bearing on your probability of actually facing seed p in that round. If you're seeded 128, you've got a 100% chance of facing the top seed in round 1. There's no possible way of getting out of it, even if the top seed only has 1 pair of shorts. If you're one of the 64 players in the opposite half of the draw to the top seed, your chance of facing the top seed in the final is significantly less than 100%, because of the significant possibility that someone in the preceding 6 rounds will have knocked off the top seed for you, as indeed Xiangzhi did to Carlsen in round 3.
This is true, but if you were to have percentages as the probability of which seed gets to the Final, then 1 would be at the top of the list; even if that number would be < 50%.

I think it would be possible to tweak my spreadsheet to reflect the odds based on the Elo ratings of the players who entered. If you then ran 1000 simulations using those odds, you might get another useful piece of information. But that's beyond both my Excel skills and time available...
I've done some Excelling, and the upshot is I still think I'm right, but for different reasons.

That being pencilled in to face p in a later round decreases your chance of facing p at all is a factor, but not necessarily the decisive factor. You can create scenarios where this is the decisive factor (a single "monster" and 127 players of equal strength), but you can also create scenarios where your wibbly wobbly line shows up (Zipf).

There's another factor though, which is: at what point are you comparing each player's projected route difficulty? If you're comparing it before round 1, then the relationship is linear: everyone plays the seed that is 129 minus their own seed.

If you're comparing it after round 1, then you have to make sure you're comparing like with like. If you're the 128th seed and you've just beaten the top seed, your future route through the tournament may appear to be easier than the 127th seed's route was at the start of the tournament. But that doesn't take into account that the 127th seed's route changed when you beat the top seed. Instead of going through the top seed, the 127th seed's route now goes through you. Or more likely, it goes through the 4th seed. You can't compare your own route in a world where you've beaten the top seed, to everyone else's route in a world where you haven't.

EDIT - this paper seems to confirm that, if you define envy-freeness as the absence of any player who would prefer to swap seedings with a lower-seeded player before the tournament starts, it's always possible to contrive some set of win probabilities that violates the envy-freeness condition, such as my "monster" competition that I mentioned above. Intuitively, if there's a monster in your competition, facing the monster as late as possible is to your advantage.

Research question, then: what can we say about the envy-freeness of a tournament where the distribution of playing strengths is log-normal, like it is for elite chess players (until you get to the top 10 in the world, who are all a bit undergraded relative to the rest because they don't have as many higher-graded players they can draw with)?
Chris Goodall, formerly known as Chris Wardle. ECF Grader for the ancient kingdom of Bernicia (or Northumberland and Durham, if you prefer). And now also Darlington. And the NCCU.
Newcastle is not in Scotland!

Mick Norris
Posts: 7415
Joined: Tue Apr 17, 2007 10:12 am
Location: Bolton, Greater Manchester
Contact:

Re: Tournament Structures

Post by Mick Norris » Thu Apr 12, 2018 9:12 am

Alex Holowczak wrote:
Tue Apr 10, 2018 10:41 pm
I think I've concluded that seeding 128 players in a 128-player knockout doesn't work from a "fairness" perspective, with the possible caveat that it works if you re-seed after each round; so the highest remaining seed plays the lowest remaining seed in each round, a bit like the NFL playoffs.
I see that both the NFL and the MLS reseed, but the NBA do not (although the WNBA do); ice hockey's Stanley Cup did between 1994 and 2013 but no longer does; off topic I know, but I wonder why the differences and changes
Any postings on here represent my personal views and should not be taken as representative of the Manchester Chess Federation www.manchesterchess.co.uk

User avatar
Chris Goodall
Posts: 333
Joined: Sun Oct 10, 2010 6:40 pm
Contact:

Re: Tournament Structures

Post by Chris Goodall » Thu Apr 12, 2018 9:07 pm

https://stacks.stanford.edu/file/druid: ... mented.pdf

"For any n = 2^r ≥ 8, there exists a set of n players with a monotonic winning probability matrix P such that it is not possible to find an envy-free seeding S for the balanced knockout tournament between these n players."

There you go then!
Chris Goodall, formerly known as Chris Wardle. ECF Grader for the ancient kingdom of Bernicia (or Northumberland and Durham, if you prefer). And now also Darlington. And the NCCU.
Newcastle is not in Scotland!

Alex Holowczak
Posts: 8880
Joined: Sat May 30, 2009 5:18 pm
Location: Oldbury, Worcestershire
Contact:

Re: Tournament Structures

Post by Alex Holowczak » Thu Apr 12, 2018 9:41 pm

Chris Goodall wrote:
Thu Apr 12, 2018 9:07 pm
https://stacks.stanford.edu/file/druid: ... mented.pdf

"For any n = 2^r ≥ 8, there exists a set of n players with a monotonic winning probability matrix P such that it is not possible to find an envy-free seeding S for the balanced knockout tournament between these n players."

There you go then!
Very interesting :)

User avatar
Michael Farthing
Posts: 1794
Joined: Fri Apr 04, 2014 1:28 pm
Location: Morecambe, Europe

Re: Tournament Structures

Post by Michael Farthing » Thu Apr 12, 2018 9:57 pm

Image

User avatar
Chris Goodall
Posts: 333
Joined: Sun Oct 10, 2010 6:40 pm
Contact:

Re: Tournament Structures

Post by Chris Goodall » Thu Apr 12, 2018 10:34 pm

Alex Holowczak wrote:
Thu Apr 12, 2018 9:41 pm
Chris Goodall wrote:
Thu Apr 12, 2018 9:07 pm
https://stacks.stanford.edu/file/druid: ... mented.pdf

"For any n = 2^r ≥ 8, there exists a set of n players with a monotonic winning probability matrix P such that it is not possible to find an envy-free seeding S for the balanced knockout tournament between these n players."

There you go then!
Very interesting :)
Having said that, I think I've found an error in his proof. Oops.

Going to have to read all the papers that cite this one now, and see whether any of them consider the same scenario.

Will you all stop saying interesting things that I have to go and research, please :P

EDIT - his conclusion is still true. I've proven it a slightly different way. If your matrix has a monster in it, the only envy-free seeding (and the only order-preserving seeding) is "runaway seeding", where the strongest competitors are placed furthest away from the monster, thusly:

{{{Monster-8}vs.{7-6}}vs.{{5-4}vs.{3-2}}}

Any other seeding would place one of 2, 3, 4 and 5 in the same half of the draw as the monster, and one of 6, 7 and 8 in the opposite half, and then the former would envy the seeding of the latter.

But runaway seeding can easily be broken by a probability matrix in which there is no monster, but competitors 7 and 8 are in fact potted plants. Then all of 2, 3, 4 and 5 would be envious of 6.

The probability that I can be bothered pointing this out to the author of the paper is given by PB, where PB is a small number.
Last edited by Chris Goodall on Fri Apr 13, 2018 9:43 am, edited 1 time in total.
Chris Goodall, formerly known as Chris Wardle. ECF Grader for the ancient kingdom of Bernicia (or Northumberland and Durham, if you prefer). And now also Darlington. And the NCCU.
Newcastle is not in Scotland!

User avatar
Chris Goodall
Posts: 333
Joined: Sun Oct 10, 2010 6:40 pm
Contact:

Re: Tournament Structures

Post by Chris Goodall » Thu Apr 12, 2018 10:49 pm

Mick Norris wrote:
Thu Apr 12, 2018 9:12 am
Alex Holowczak wrote:
Tue Apr 10, 2018 10:41 pm
I think I've concluded that seeding 128 players in a 128-player knockout doesn't work from a "fairness" perspective, with the possible caveat that it works if you re-seed after each round; so the highest remaining seed plays the lowest remaining seed in each round, a bit like the NFL playoffs.
I see that both the NFL and the MLS reseed, but the NBA do not (although the WNBA do); ice hockey's Stanley Cup did between 1994 and 2013 but no longer does; off topic I know, but I wonder why the differences and changes
https://pdfs.semanticscholar.org/a16b/e ... 95a2d3.pdf

"Baumann, Matheson, & Howe (2010) noted that reseeding causes teams and spectators to have to make last-minute travel plans, which both increases costs and potentially reduces demand, and that reseeded tournaments eliminate popular gambling options related to filling out full tournament brackets, potentially reducing fan interest in the tournament."

That's from a guy called Alexander Karpov, so you know it's applicable to chess.
Chris Goodall, formerly known as Chris Wardle. ECF Grader for the ancient kingdom of Bernicia (or Northumberland and Durham, if you prefer). And now also Darlington. And the NCCU.
Newcastle is not in Scotland!

Alex Holowczak
Posts: 8880
Joined: Sat May 30, 2009 5:18 pm
Location: Oldbury, Worcestershire
Contact:

Re: Tournament Structures

Post by Alex Holowczak » Fri Apr 13, 2018 12:39 pm

Chris Goodall wrote:
Thu Apr 12, 2018 10:49 pm
Mick Norris wrote:
Thu Apr 12, 2018 9:12 am
Alex Holowczak wrote:
Tue Apr 10, 2018 10:41 pm
I think I've concluded that seeding 128 players in a 128-player knockout doesn't work from a "fairness" perspective, with the possible caveat that it works if you re-seed after each round; so the highest remaining seed plays the lowest remaining seed in each round, a bit like the NFL playoffs.
I see that both the NFL and the MLS reseed, but the NBA do not (although the WNBA do); ice hockey's Stanley Cup did between 1994 and 2013 but no longer does; off topic I know, but I wonder why the differences and changes
https://pdfs.semanticscholar.org/a16b/e ... 95a2d3.pdf

"Baumann, Matheson, & Howe (2010) noted that reseeding causes teams and spectators to have to make last-minute travel plans, which both increases costs and potentially reduces demand, and that reseeded tournaments eliminate popular gambling options related to filling out full tournament brackets, potentially reducing fan interest in the tournament."

That's from a guy called Alexander Karpov, so you know it's applicable to chess.
I'm not sure I agree with any of those three assertions. That it "causes teams and spectators to have to make last-minute travel plans" is not true at all. Whether you re-seed or not ... it's a knockout tournament. No one with any sense is going to book travel tickets to a round of a knockout tournament that they haven't qualified for yet, or when you don't know who or where you're playing. So wouldn't you just wait until the pairings are published?

Organisers can come up with their own ways of making life difficult for travelling fans without relying on the seeding of brackets, anyway. We see it in the Premier League with games moved for television, particularly to unhelpful times to access grounds on public transport or get home in an evening. The AFL came up with its own impressive way of upsetting fans - their lease of the MCG said that at least one game per round of the playoffs had to be played there. And so one year, Adelaide's fans had to travel to the MCG to watch their team play a home playoff game against ... Melbourne. :roll:

I don't know how popular "fill the bracket" gambling is in the UK - it's certainly popular in March Madness, but I don't think that has quite made it over to the UK. My not remotely educated impression is that match-by-match gambling, or potentially gambling on a series of events down a list (e.g. the Scoop6) is more popular. I realise their comments are "potentially reduces", but I don't think either has a very large potential.
Last edited by Alex Holowczak on Fri Apr 13, 2018 2:05 pm, edited 1 time in total.

Post Reply