The "Perfect" Lineup

Question

Alice is the head of her high-school quiz bowl league. She is in charge of choosing who will play in the next quiz bowl tournament. She has executive authority about who plays when, and she can change her mind at any time, as long as it isn't for the game that is currently being played.

The rules of how she can put players on her team are as follows.

1. She is in charge of a single team, which competes in every single round of the game.
2. The team she is in charge of must have exactly 4 people playing at any time. Any person who is on the team that is not actively playing must sit out.
3. As rounds progress, she can decide who is playing at any given time, unless its for the round she is actively playing on. If she does not like the line-up that is currently playing, she must wait until the round ends to change it.
4. The entire tournament consists of an arbitrarily large number of rounds.

In general, this means that the order of events is

[Pick players]
Play a round
[Re-assign players]
Play another round

and so on. Unfortunately for Alice, she does not know how many people will be on her team, and she does not know the skill level of any player. Thankfully, she can keep track of the scores of the players on her team during the rounds to determine who is answering the most, the second most, the third most, and so on.

Unfortunately, the teammates she has are pesky, and have strong feelings about how much each should be playing. Because of this, Alice has determined the following.

1. If Alice were to make the team consist of only the best 4 players, their team would win the tournament.

2. If Alice were to assign players completely at random, their team would lose.

3. The players on her team have reached a consensus - they are willing to play in unequal amounts, as long as the team selection is as fair as possible, while guaranteeing that they still win the championship.

How can Alice create the most fair teams, while ensuring victory?

---

Reminder: A team that is 100% fair, consists of completely random players, and a team that is 0% fair consists of only the best players.

Answer 1

This question cannot be answered - there are simply too many contradictory conditions present in this set-up for a meaningful answer to exist.

1. If Alice does not know the skill level of any of her team members to begin with, it will be necessary for her to deploy every single team member at least once, completely at random, in order for her to know their skills levels. (The lack of this knowledge is self-defeating, as any strategy made without this knowledge will necessarily be random and purposeless).

2. To achieve #1, Alice will have to play at least n/4 (n being the number of members) rounds at random, which already defeats the condition of having 100% victory since it is impossible for those n/4 rounds to have been played by the best players (unless n = 4). This already requires the unstated assumption that scores attained in one round are comparable with scores attained in a second round.

To make this puzzle meaningful, it would be a good start to say that Alice knows the skill level of every single team member, and that victory is equivalent to having the best players play as much as possible while maintaining some level of randomness. In this case, the solution would be to:

First, assign every member a score from n to 1, where n is the number of members. The best player should receive n, and the worst to get 1. Ties are allowed.

Then,

Conduct a lottery at the beginning of every round, where each member will have as many lots as his/her score. As such, strong players have a higher probability of being deployed (for the win), while weaker players have a non-zero chance of playing (for the lulz). This ought to satisfy everyone, the pesky b**tards.

Answer 2

The question seems under-specified.

In particular, we're effectively being asked to maximise the "fairness" function, with no definition of what the team considers "fair" apart from the 0% and 100% data points.

It's also unclear how much variation in skill we've got and how much that manifests itself in any given round (e.g. would a good player ALWAYS outperform a bad player on every round, or merely on average in the long term, but the bad player could get lucky).

It is assumed that the reference to "completely at random" in the question refers to use of a uniform probability selection process.

As "fairness" has not been defined, I'll define it for the purpose of this answer as "for those who are not currently playing, the ratio between the lowest and highest probability of being selected for the next round". i.e. if everyone who is currently not playing has an equal (and non-zero!) chance of being selected for the next round, it is 100% fair, and if anyone has a 0% chance of being selected for the next round it is 0% fair.

By this definition, weighted probability functions (such as in Xenocacia's answer) would have a fairness ratio defined by the ratio between the lowest weight given to a player and the highest weight.

The following procedure is proposed as a 100% fair (by the above definition) method by which a good team can be formed in the long term:

After each round, the worst performing member in that round is ejected from the team, and replaced with another member selected completely at random. The other 3 retain their places.

Over time, it is likely that the 3 of the best players will stay on the team most of the time. If any of those 3 best players have a "bad round" they'll join the pool of players on the sidelines until they're selected to play in the team again (at which point they'll probably be retained for at least several more rounds).

By this method, no player's position on the team is 100% "safe" (which could be the basis for a different definition of "fair"...) - if the very best player who has stayed on the team for many rounds has an unusually bad round, whilst the other players have at least a reasonably good round, the long-term best player could be ejected from the team and enter the selection pool. In the long term this won't matter as they'll eventually be selected for the team again, and likely retain their place for many more rounds...

The most likely time that one of the 3 best players could be ejected from the team is when the 4th player is also one of the best, and it's unlikely that the team will ever have more than one player known to have very poor performance.