6 2/11: The minority game

Here is a state-transition diagram for a simple n-player game:

The rules are very simple: players in the minority win. So if three people vote A and two vote B, then the three lose and the two win. If there are six players, three of which vote A and three of which vote B, then everyone loses because there is no minority. If there’s only one player then they can never win because they will never be in the (empty) minority. Also, with two players no one ever wins. So it’s really only interesting in groups of three or more.

This game sounds pretty dull but, like many other seemingly dull games, it’s useful in the field of game theory to analyze complex behaviors among large groups of interacting agents, be they people in social situations, entities in financial markets, or even matter in physical systems. This particular game is called a “minority game” and you can read more about it if you’re curious.

Our interest in this game isn’t its game-theoretic properties, but how we can code it up using Worlds and Universes. In particular, we’ll see a way to model state-transition systems by mapping each state down to its own class, with objects transitioning from one state to the next by morphing into new kinds of objects.

Exercise 1. The Universe will be responsible for coordinating the players, gathering their votes, and determining which players win and lose.

Create three Universe classes, join-universe%, vote-universe%, and win-lose-universe%, one for each state in the transition system.

  • join-universe%: Listen for new players for a moment, and then send a message to all known players to announce that voting will begin. The announcement doesn’t need to contain any meaningful information. Incoming messages can be ignored.

  • vote-universe%: Wait for all players to place a vote ("A" or "B"). After all votes are in, notify each player whether they’ve won (true) or lost (false) and advance to the next state. If a player places multiple votes, ignore all but the last one. Players that try to join during the voting phase can be ignored.

  • win-lose-universe%: Give the players a moment to accept their defeat or celebrate their victory, then start the game over in the Join state and notify the players of this. Again, this message doesn’t have to contain meaningful information. New players and incoming messages can be ignored in this state.

A few limitations to mind:
  • Even though we have multiple Universes, there can only be one tick-rate and, if you want to specify it, it must be defined on the initial Universe.

  • Each Universe can have its own methods like on-tick, on-disconnect, etc., but if they aren’t defined on the initial Universe then the system won’t know to look for it on subsequent Universes. If necessary, you can define “do-nothing” methods on your initial Universe that leave everything unchanged.

Exercise 2. The World will represent a player and is reponsible for connecting to the universe, picking a vote, and reporting the outcome.

Create three World classes, join-world%, vote-world%, and win-lose-world%, one for each state in the transition system.

  • join-world%: Register with the Universe and wait to be notified that voting has begun. As above, the notification won’t contain any meaningful information.

  • vote-world%: Let the player choose their vote and send it to the Universe ("A" or "B"). Listen for the message indicating whether we’ve won (true) or lost (false), and then advance to the next state.

  • win-lose-world%: Report the player’s fate and wait to be notified that the game is restarting. As above, the incoming message won’t contain meaningful information.

Worlds have the same limitations as Universes described above.

Does your game work properly? Try playing with your neighbors—if you followed the spec above, you should all be speaking the same protocol.

Exercise 3. I bet you have some repeated code. Since each Universe must have on-new and on-msg methods, There should be a few places in your three Universe classes where you wanted to ignore new connections or incoming messages, and you had to define do-nothing methods to appease the universe system.

Define a superclass to abstract the repeated code. Do you need to use overriding?

Exercise 4. If you used on-key or on-mouse to input the player’s vote, you’ll have a similar problem where you defined do-nothing methods on all but one of your World classes.

Clean up your World classes by defining a superclass, similar to the one above.

Exercise 5. If a player tries to join during the Vote or Win/Lose state they will be ignored—that’s pretty rude!

Change your vote-universe% and win-lose-universe% so that they queue up incoming players and pass them off to the join-universe% when the next round starts. To avoid repeated code, define and use a superclass to achieve this.