1
$\begingroup$

This is a real life problem. A group of people meet once a week to play a game between two teams. Each round 2 people are randomly appointed captains. Each captain takes turns picking people to be on their team. So far 17 people have turned up to these games. They are each represented by a different letter in the alphabet from A to Q. The players have different capabilities. The teams are usually 5 on 5 but it can vary if an odd number of people turn up for the game of if the captains agree that 2 weak players are equal to 1 strong player.

In the 7 rounds so far the scores have been:

ROUND1: TEAM 1 = AEHJK; TEAM 2 = BCDFIM; TEAM 1 SCORE = 10; TEAM 2 SCORE = 2; ROUND2: TEAM 1 = ABDFJ; TEAM 2 = CEGHI; TEAM 1 SCORE = 10; TEAM 2 SCORE = 3; ROUND3: TEAM 1 = ACEFK; TEAM 2 = BDGNO; TEAM 1 SCORE = 5; TEAM 2 SCORE = 1; ROUND4: TEAM 1 = ACFGI; TEAM 2 = BDJKPQ; TEAM 1 SCORE = 1; TEAM 2 SCORE = 4; ROUND5: TEAM 1 = ABIJ; TEAM 2 = CDFKOP; TEAM 1 SCORE = 3; TEAM 2 SCORE = 4; ROUND6: TEAM 1 = ABCFH; TEAM 2 = DEIKL; TEAM 1 SCORE = 10; TEAM 2 SCORE = 1; ROUND7: TEAM 1 = ACDIJ; TEAM 2 = BEFHK; TEAM 1 SCORE = 9; TEAM 2 SCORE = 0;

The organizers want to understand the strengths of each of the players so that they can organize more even match ups. If a teams strength is the sum of the strengths of each of the players then what is the strength of each player? It's possible that some combinations of players lead to a better result than would be predicted by a simple additive model. Is there a better way to accurately predict the results of the teams combinations? What is it?

$\endgroup$
  • 1
    $\begingroup$ Is this a puzzle or an actual problem you face? Note that there's no reason you should be able to assign each player a number such that the sum of the numbers assigned to a team predicts how likely the team is to win against the other team. This kind of stuff depends strongly on the properties of the game. For example, in a game like Pokémon some players are weak or strong against others, and in particular there are loops where player A reliably beats player B, who reliably beats player C, who reliably beats player A. $\endgroup$ – Qiaochu Yuan Aug 15 '13 at 0:25
  • $\begingroup$ There is probably some applicable voting system mathematics at work here, but I don't know what to call it. $\endgroup$ – rschwieb Aug 15 '13 at 0:45
  • $\begingroup$ This is a real problem we face. Are there better tags to use? $\endgroup$ – user2027987 Aug 15 '13 at 1:02
2
$\begingroup$

Microsoft have developed a ranking algorithm for just this problem that they use in their Xbox Live service.

(Xbox Live is an online gaming platform players meet to compete in games like football and Quake-like games). Their algorithm is called TrueSkill. They use it to measure player's skill and pair them up with players of similar skill on servers, so that everyone has a good time.

Here's the technical paper. http://research.microsoft.com/pubs/67956/NIPS2006_0688.pdf

There's also the classic ELO rating system which is widely used. I don't think it works for individual skill determination in team games though. http://en.wikipedia.org/wiki/Elo_rating_system

$\endgroup$
  • $\begingroup$ The TrueSkill algorithm looks suitable. Unfortunately my math's is not that great anymore. can you tell me what the answer is in this example and show how you worked it out? $\endgroup$ – user2027987 Aug 15 '13 at 1:14
  • $\begingroup$ You don't need to understand (much) math to use TrueSkill and you can't determine easily form the data you provided what the assessed relative strength of players will be because TrueSkill models skill with a Normal distribution which it uses evidence (game results) to improve in a Bayesian model. There are a number of libraries available that implement TrueSkill (in Python, C# even Javascript I think) and you can try one out if you like. $\endgroup$ – Bernd Wechner Feb 28 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.