Fixture Structure Discussion

A PlayDiplomacy competitive league

Moderator: mjparrett

Fixture Structure Discussion

Postby mhsmith0 » 19 Apr 2018, 06:29

I feel like I'm starting to overwhelm the relegation topic with my design notes so I'll split this out into its own topic, focusing on a few aspects of design (I think this is a separate discussion than standard suggestions so I posted it to main folder instead of suggestions subfolder):

Single Year Matchup Assignment Structure
1) Key Concepts
Before I get into the weeds, I want to establish a few concepts:
First, there is a design decision that has been made to avoid any triple matchups (i.e. no two players will see each other three times in the same season). Moreover, maximizing the spread of matchups (and/or minimizing the # of people who NEVER see each other in a season) is a design consideration as well.
Second, we can assign/order people based on which game they’re in for round 1, i.e however else we design things, players 1-7 are in game A (or game 1 if you prefer, but different numbering scheme for players and games is helpful IMO), players 8-14 are in game B, and players 15-21 are in game C. Similarly, “group A” refers to players 1-7, who were in game 1 together (used when convenient for describing stuff). In ANY design scheme, you will have this concept at work.
Third, we can order games in rounds 2, 3, and 4 based on how many players from each group are in it. Specifically, “game A” in round 2 can be defined as whichever game has the most players from game A in round 1 in it, game B in round 2 has the most players from game B in round 2, etc.
Fourth, design structures should be replicable between groups. If player 1 is in games A/B/C/A, then player 8 (first in group B) should be in B/C/A/B and player 15 (first in group C) should be in C/A/B/C, possibly subject to some additional tweaks (for instance, we could say that player 1 goes B/C/A in games 2/3/4, but player 8 goes C/A/B in games 3/4/2, and player 15 A/B/C in games 4/2/3, or the like). The main benefit is to make it substantially easier to create a setup the next year (if there are many ways to make a structure “fit”, then we can test each one to find what gives us the most balanced spread of matchups).

2) How do you spread group A around?
The first design structure decision becomes, how do you split up players from group A into all of the games in rounds 2-4? This isn’t necessarily obvious; you could, for instance, have round 2 see four group A players in game A, two in game B, and one in game C. Or you could do 3/3/1. Or you could do 3/2/2, or various other possible combinations.
As it turns out, to avoid triple matchups, you pretty much have to go with 3/2/2.
Let’s start by looking at 4/2/1. If even just round 2 is set this way, you can’t avoid triple matchups inside group A alone. Let’s break it down: for round 2, set players 1-4 in game A, players 5-6 in game B, and player C in game 7. In round 3, let’s say you put player 1 in game A, player 2 in game B, and player 3 in game C. Player 4 needs to be in one of the games, but ANY game he goes in, he’ll be triple-matched against one of players 1-3.
For 3/3/1, meanwhile, you can just barely fit in one instance of it, but if you do it twice, you’re forcing triple matchups. Let’s break it down: for round 2, set players 1-3 in game A, players 4-6 in game B, and player C in game 7. For round 3, if you’re going to do 3/3/1 again, let’s say player 7 goes into game A. But that means that you need to fit three people into game B, which means you need to fit two people from players 1-3 (causing a triplication) or two people from player 4-6 (ditto). Technically you can just barely make this fit if you go 3/3/1 once and 3/2/2 twice… but that’s a super awkward structure. Additionally, 3/2/2 allows you to maximize exposures to other groups, which is itself a useful goal (which was previously discussed as a design consideration).
So now that we’ve established 3/2/2 as “best” subject to our design constraints, we can discuss how to allocate specific group A members across particular games.

3) Why one group A member must be in game A all four rounds
The basic answer here is simple: you can’t avoid this without seeing people play each other three times. Why that is the case is more complicated, though…
To start with, if you go with this structure, you’re going to have three people in three group A games, three in two group A games, and one in just one group A game. So you have something like:
Player 1: A/A/A/B
Player 2: A/A/B/A
Player 3: A/B/A/A
Player 4: A/C/C/A
Player 5: A/C/A/C
Player 6: A/A/C/C
Player 7: A/B/B/B
The problem is, when you apply this construct to the other groups, you start getting overlaps…
Player 11 (analogue to player 4): B/A/A/B, i.e. 3/4 games are the same as player 1 (player 12 and player 2, player 13 and player 3, all have the same issue, and others pop up too)
So (at least I think) you pretty much CAN’T do it this way and avoid triples.
So you’re left with instead:
Player 1: A/A/A/A
Two players at A/A/?/?
Two players at A/?/A/?
Two players at A/?/?/A
Note that one consequence of this structure is that the distributions of opponents becomes somewhat uneven: player 1 will see fewer members of groups B and C than players 2-7 will, and the same is true of player 8 (who will run B/B/B/B) and player 15 (C/C/C/C).

4) Filling in the rest of the fixture list
We can start by defining players 2-3 as being in game A round 2, 4-5 in game B round 2, and 6-7 in game C round 2.
After that, game A in rounds 3 and 4 must have exactly one of players 4/5, and one of 6/7.
For the remainder, it’s really a matter of testing out what results in the widest variety of connections between players, while avoiding triples.
That gives us:
Player 1 A/A/A/A
Player 2 A/A/B/B, and Player 3 A/A/C/C (giving them each one of B and C results in less rather than more variety of connections)
Player 4 A/B/A/B, and player 5 A/B/B/A (again, flipping a B to a C reduces the variety of connections overall)
Player 6 A/C/A/C, and player 7 A/C/C/A
Then group B repeats the structure, just with A->B->C->A (so player 8 gets B/B/B/B, player 9 B/B/C/C, etc), then do it again for group C.
The other benefit of this structure (and this is where I think it really shines) is that you can redefine the structure in a bunch of different ways while having the sets of matchups be equivalent.

To wit: let’s flip rounds 2 and 1
New round 1:
Game A: players 1, 2, 3, 13, 14
Game B: players 4, 5, 8, 9, 10, 20, 21
Game C: players 6, 7, 11, 12, 15, 16, 17
New round 2:
Game A: players 1-7
Game B: players 8-14
Game C: players 15-21

Players 1-3, 8-10, and 15-17 have no change.
Player 4: A/B/A/B turned into B/A/A/B
Player 14: B/A/A/B turned into A/B/A/B
Player 7: A/C/C/A turned into C/A/C/A
Player 18: C/A/C/A turned into A/C/C/A
So the exact same set of 12 games (just in a different order), results in some number of players being reordered, but the structure as a whole remains valid. For instance, “player 2” in the main model could instead be interpreted as “player 4” if you flip around rounds 2 and 3, “player 6” if you flip around rounds 2 and 4, or player 3/5/7 if you flip around groups B and C (since they’re both arbitrarily defined anyway). And then you can play around with it even more just by flipping around what is considered “round 1”.
THIS then means that as long as you can create one or more valid “year 2” tables given year 1 data (i.e. “player 1 in 2018 becomes player 18 in 2019” or the like), you can fit that a lot of different ways, which gives you maximum flexibility to test things out given different combinations (by my count, it was 144 different ways to look at the same set of year 1 matches).

5) Filling in future years’ fixture lists
As alluded to earlier, this really depends on the specifics of your judgment criteria (do you want to minimize cases where someone plays an opponent twice in consecutive years? Do you want to “seed adjust” the tables so that the best players from one year will be likelier to avoid each other the next year? Some other criteria?).
The starting point is to create some kind of algorithm so that you’re guaranteed to avoid instances where players miss each other for two full years in a row (ignoring substitution type issues, of course). I’m not 100% what I did was most optimal (although I strongly suspect it's close), but the following table:

1 A A A A 9
2 A A B B 4
3 A A C C 13
4 A B A B 8
5 A B B A 12
6 A C A C 19
7 A C C A 7
8 B B B B 18
9 B B C C 6
10 B B A A 5
11 B C B C 11
12 B C C B 14
13 B A B A 21
14 B A A B 16
15 C C C C 20
16 C C A A 1
17 C C B B 3
18 C A C A 2
19 C A A C 17
20 C B C B 15
21 C B B C 10

Achieves that goal while keeping the number of repeat doubles reasonably low (25 pairings among 21 slots [50 if you double count, i.e. players 1 and 4 double dipping counting as 2 instead of 1 pairing] ).
To interpret the table: player 1 in 2018 becomes player 10 in 2019, so his draw is A/A/A/A in 2018, and B/B/A/A in 2019.
Player 10 in turn becomes player 5 the next year, for a rotation of B/B/A/A the first year and A/B/B/A the next, etc.
Proud holder of the Superior Tophat of Solving, an item entrusted with the forum's most prominent smartass
User avatar
Posts: 3616
Joined: 11 Dec 2015, 06:55
Location: Phoenix, AZ
Class: Star Ambassador
Standard rating: (1269)
All-game rating: (1439)
Timezone: GMT-7

Re: Fixture Structure Discussion

Postby mhsmith0 » 19 Apr 2018, 06:38

And as an illustrative example, I randed the same type of example as I'd done in last hread for league 1 with seven losses due to promotion/relegation:

Results Round 1 Round 2 Round 3 Round 4 Round 1 Round 2 Round 3 Round 4
bindlestiff C B B C C C C C
Machor A B B A B B B B
mjparrett C B A B A A C C
bdferris1 A B C B A B A B
jimbobicus C C C C C B C B
WarSmith A C C A C A A C
GruGloG C C A A C C B B
Verse9 A C A C B A B A
prgm B C B A A B B A
StarkAdder B A A B C B B C
greggybear C A A C A A B B
DirtyHarry B A B C A C A C
Pootleflump A A C C A C C A

(first four games are 2018, next four are 2019)

No one sees more than three opponents four times over the course of two years, and most see less (the average is 1.6 currently).

I might be able to get that down a bit more... but probably not massively so. At any rate though, that seems pretty ok for frequency of matchups? All the more so since I've also solved out for making sure every remainer plays every other remainer at least once in either 2018 or 2019.
Proud holder of the Superior Tophat of Solving, an item entrusted with the forum's most prominent smartass
User avatar
Posts: 3616
Joined: 11 Dec 2015, 06:55
Location: Phoenix, AZ
Class: Star Ambassador
Standard rating: (1269)
All-game rating: (1439)
Timezone: GMT-7

Re: Fixture Structure Discussion

Postby V » 19 Apr 2018, 13:52

There are a couple remarkable aspects to this fixture setting progress for future PDL seasons. One that we found a league participant capable of doing the mathematics & that it even appears enjoyable!
Great work & very impressive results to date. Assuming I manage to hang in there & retain league 1 status, I look forward to seeing next year’s fixture list. I won’t be checking it for correctness however!
Platinum Classicist
Voilà! In view, a humble vaudevillian veteran cast vicariously as both victim and villain by the vicissitudes of Fate. This visage, no mere veneer of vanity, is a vestige of the vox populi, now vacant, vanished.
User avatar
Posts: 796
Joined: 04 May 2014, 21:28
Class: Star Ambassador
Standard rating: 1769
All-game rating: 1827
Timezone: GMT-6

Re: Fixture Structure Discussion

Postby mjparrett » 20 Apr 2018, 12:57

I haven't read the full details (as a lot of it is lost on me!), but thanks very much for putting it together.

To answ er a couple of points (some of which are from the other thread); yes I understand the concept of a league and playing people year on year. But in a 7 player game and 21 people to a league with a certain amount of promotion/relegation, you don't want things getting too stale.

If I had been better at maths in the first place I would have implemented a system that minimized the amount of people who never play each other. So I am all in favour of bringing this fixture structure in from next season. It would be nice to automate it in such a way that I could still do the fixtures for league 1, but it is probably a good idea that I don't anyway from a fairness perspective.

This solution, in turn, affects the numbers of promotion. As stated, my main reason for 7 (other than the relevance of it in Diplomacy) was to stop the leagues getting stale. League 2 will naturally have less an issue as it has promotion and relegation but the top and bottom leagues will suffer if only 2 or 3 moved each year, ESPECIALLY with the current fixture headache in place. With this in mind I would be prepared to support a move to 4 or 5 movers each year (provided this didn't mess up the maths above!), and hope that would encourage better/more risky play. Does this also need done in conjunction with a new scoring system? I don't know, and I worry there would be too many suggestions.

Posts: 387
Joined: 01 Mar 2017, 20:05
Location: Scotland
Class: Star Ambassador
Standard rating: 1425
All-game rating: 1472
Timezone: GMT

Re: Fixture Structure Discussion

Postby boldblade » 20 Apr 2018, 14:27

mjparrett wrote:but the top and bottom leagues will suffer if only 2 or 3 moved each year

According to the rules thread the bottom league also experiences relegations.
Posts: 338
Joined: 05 Feb 2014, 17:33
Class: Star Ambassador
Standard rating: (1474)
All-game rating: (1488)
Timezone: GMT

Return to PlayDip Diplomacy League

Who is online

Users browsing this forum: No registered users and 0 guests