Logic/game theory puzzle... a fair seeded bracket

Here’s an interesting logic/game theory puzzle, inspired by the fairly lame situation in the World Cup where Belgium and England were both guaranteed round of 16, but the loser of their match presumably ended up in a better place in the bracket. So… you’re running a tournament. There’s some initial round, and after the initial round, there are 16 qualifiers who make it into the final round, which will be a traditional 16-team single elimination bracket, with everyone locked into their spot in the bracket once the top 16 begins. Your 16 qualifiers ended up with scores or ratings coming into the top 16 which lets you rank them 1 through 16. So the traditional thing to do would be to pair 1 vs 16, 2 vs 15, etc, in a normal seeded bracket. However, for whatever reason, this particular competitive endeavor has lots of rock-paper-scissors matchups, and you don’t want to penalize the #1 ranked team by giving them a round-of-16 pairing that is particularly unfavorable. So, you decide that instead of a fixed seeded bracket, the bracket will be determined in some fashion where teams actually choose their positions in the bracket, with the highest-seeded teams being able to maximally control their position in the bracket, as their prize for winning the highest seeds. So, one by one, teams will place their names somewhere in the top-16 bracket, keep going until all spot are filled. But… picking first isn’t an advantage (because the bracket is entirely empty, you’re basically doing nothing). And picking last isn’t an advantage (because there’s only one empty spot). So… how should you order the picks such that the #1 seeded team has the “best” pick, the #2 seeded team has the second best, etc. Is it even possible? (The question as posed asks you to come up with a fixed pick order… could be expanded to allow any bracket-filling methodology.)

#1 gets to pick their round of 16 opponent. Then #2 gets to pick theirs, unless they were chosen by #1. Then #3 gets to pick, unless they were picked by #1 or #2, and so on, until all the round of 16 matches are set.

Then, #1 gets to pick which r16 match goes next to them in the bracket. That is, which game’s winner they’ll meet in the quarterfinals. Then #2 makes the same pick, if they haven’t already been placed, etc.

Then #1 gets to pick which other quarter bracket goes next to their quarter. Done.

That’s a good answer… although it’s not technically an answer to the first question I asked. If it HAD to be done purely as a simple order, take turns writing our names down in a 16-person bracket, then what’s the optimal ordering?

I’m not sure there’s any good way to do a simple ordering of picks. If you put #1 somewhere in the middle of the order, then any earlier easy teams would probably have been picked as opponents already.

Maybe a slightly different way to do it is in reverse seeding order, but allowing replacement, like is done at some holiday parties (and on Big Brother, I think :slight_smile: ). On each team’s turn, they can pick any spot in the bracket, even if it’s already occupied. If they pick an occupied spot, then that team has to choose a new spot, and they must choose an empty spot.

So if I’m understanding this correctly, a team is only picking a spot on the chart, not a opposing team? A team can either pick a spot that has an open opposing spot (in which case they don’t know who their opponent will be) or can pick an open spot that’s next to a team that already picked. But teams that are already matched up aren’t available. So, for example, if the 15th and 16th ranked teams were the first and second to pick; the 15th ranked team would pick any spot because they’re all equivalent at that point. Then the 16th ranked team would pick the spot opposing the 15th ranked team because that’s their best chance at winning. The third team to pick a spot wouldn’t be able to play the 15th or 16th ranked teams because they’re already committed to playing each other. Do I have it right?

It’s an interesting puzzle and I’m not seeing an obvious path to unraveling it. I’m going to think on it some. But not now because it’s one in the morning here.

I think the correct order would be 16-1-15-2-14-3 etc. My reasoning: The first pick is meaningless, and so it should go to the team with the least claim on a decision. And everyone wants to be the one to play against the 16 team, so the second pick is a premium pick, which should go to the team with the greatest claim. Similarly for later rounds: Seed 15 has no basis to choose, other than wanting to stay as far away from 1 as possible, and then seed 2 will want the position opposite 15 (as a side effect, this also means that a no-upsets tournament will end with 1 vs. 2 in the final, which is probably desirable).

Interestingly, if you did in order of rank, you’d end up with the traditional seeding.

Assume, for the sake of the example, that each team wants to play against the lowest ranked opponent.

Team 1 picks first. The board’s open so they just pick a random spot.

Team 2 has a choice between picking the spot against Team 1 or a spot in an open pair. They obviously would prefer to play any team other than 1 so they pick an open pair.

Teams 3 through 8 follow the same logic as 2 and each of them picks a spot in an open pair.

Team 9 picks and there are now no open pairs left. So they pick spot with the best opponent they can get; Team 8.

Teams 10 through 16 follow, each picking the weakest opponent who’s left. 16 ends up with the last open spot opposite 1, which everyone else avoided.

The final line-up:

A: 1
B: 16

C: 2
D: 15

E: 3
F: 14

G: 4
H: 13

I: 5
J: 12

K: 6
L: 11

M: 7
N: 10

O: 8
P: 9

It’s certainly the case that if the rankings are purely linear, that is, each team is favored to beat each “worse” team, then there’s no point in doing anything other than the straight normal seeded bracket. The question assumes that there are cycles and rock-paper-scissors etc. Maybe the #1 seed is by far the best team overall but everyone knows that it has a poorish matchup specifically vs #7 and #13.

If for some reason we are restricted to just “take turns placing names in a fixed bracket” (which is probably a stupid way to do it in the real world, but is what the pure form of the question is asking about) I’m pretty sure that the best picks are in the middle, when there’s both a fair amount of information and a fair amount of control. Early picks are meaningless (no information) and late picks are worthless (no control), so the best picks have to be in the middle.

Then I believe you have the standard 1-16, 2-15, 3-14 matchup where every chooses the optimal path to the end.

Here’s Lewis Carroll’s proposal (summarized in first paragraph of this blog), which is basically similar to the first half of a World Cup, but carried through to the end of the tournament:

Yes, that’s a minimal standard that any solution should meet. In the standard situation, you should get the standard result. But you might not, if there are weird situations like the OP alludes to. All of the situations which give the standard result in the standard situation are distinguished by what they do in the weird situation.

For instance, consider the case where an otherwise weak team is, due to RPS-ism, unusually capable against the Number 1 seed. That weak team would like a bracket where they face the #1 seed right away, and then can hope to get by against relatively weak opponents. The other teams would also like that, because then they have a good hope of eliminating their greatest threat early. But the #1 team wouldn’t like that, because they’d rather see that unusually capable team eliminated before they have to face them. Under Little Nemo’s proposal, the unusual team gets their wish: Nobody else chooses the matchup against #1 until it’s that team’s turn, and then they take it. Under my proposal, the #1 team gets their wish: If the unusual team is #16, then #1 can choose any other position, and if they’re not, then #1 can choose to play against #16, and either way avoid the dangerous team.

What about placing 9-16 in their traditional slots, and THEN letting 1-8 choose their first opponent? Or place 9-16, have 5-8 choose their opponent against 9-12 (the 4 best in the bottom half), and then letting 1-4 pick?