Sign in to follow this  
rovertos

Any known anti-coordination (or crowding) strategy games?

Recommended Posts

Hello,

Straight quote from wikipedia: "crowding game is defined as a game where each player's payoff is non-increasing over the number of other players choosing the same strategy."

Do you know of any strategy games built on this principle? I have been contemplating lately on how such a game could be made interesting, given a large number of players taking simultaneous turns. In theory, on a very abstract level, such a game would be constantly balancing itself - as soon as a single dominant strategy emerges, it is automatically rendered ineffective by the fact that more players are using it. Therefore, to win, you would always have to anticipate the crowd's movement and think differently...

Does this remind you of anything, or do you think this makes any sense?

Thank you

 

Share this post


Link to post
Share on other sites

If I'm understanding the concept correctly, this applies (in a non-rigorous sense) to any game where there are multiple limited resources. e.g. If 4 players can all choose to harvest lumber to build boats or mine gold to build knights, then the more people choose "Prefer Lumber", the worse that strategy is likely to perform (as there is less of it, thus less potential payoff). The same applies to "Prefer Gold".

However, the idea that it renders dominant strategies non-existent is not entirely true, at least not in the useful sense. It's an insufficient condition in the single-game case - you'd need to ensure that the payoff is decreasing (not just non-increasing), and by an amount sufficient to make some other strategy superior (which may require more concurrent players than your game might support).

This also extends into the iterative form (where the game is played repeatedly), because even a crowding strategy could become evolutionarily stable across the player base if it is sufficiently better than the alternative to the point where people would be fools to consider the alternative. e.g. In a 4 player game, if knights are far better than boats, 90% of your players might choose the knight-building, knowing that unless they enter a game with 3 boat-builders, they are guaranteed to beat any boat builders and have an even chance against other knight-builders.

I guess the TL;DR is that this is a very useful property to have in your game, but it isn't a Get Out Of Jail card when it comes to balancing strategies against each other. :)

Edited by Kylotan
switch iron for gold, thus making post actually make sense

Share this post


Link to post
Share on other sites
Hello, thanks for the reply. :)
 
Whether a crowding strategy could become evolutionary stable, I guess, is dependent on game parameters outside the crowding aspect of the game, i.e. game constants such as "knights being far better than boats", as you mentioned. Therefore this either comes down to balancing game constants in the traditional sense, or to the removal of game constants altogether. In the latter case, which is far more interesting as brainstorming material, I think that the real challenge becomes not to prevent the game from becoming evolutionary stable, but to prevent it from degrading into a game of chance, when chaos takes over and no strategy can emerge other than making a decision and hoping for the best.
 
For example, consider a large number of players, making their way one node per turn through a complex interconnected graph. All players start at node A with the same amount of points and they all share the same goal of reaching node Z at the far end of the graph. The game is played in simultaneous turns: during the command phase each player chooses an adjacent node to move to, and during the execution phase the game charges each player an amount of points equal to the number of players that chose the same destination node multiplied by a constant that is particular to their starting node. For example, if 30 players move from A to B, and the constant for A is 1.5, then the game deducts 30*1.5=45 points from each of these players. Any player that finds himself with a negative number of points is eliminated from the game.
 
Given this setting, one strategy that immediately emerges as dominant is NOT to follow the shortest route, as most of the players are likely to follow that one and therefore find themselves starved for points and eliminated from the game halfway to Z. But then again, if most players are veterans who grasp this strategy and decide to go for it, then the noobs who choose the opposite strategy win. Therefore to NOT follow the shortest route is no longer a dominant strategy and, obviously, if you consider to follow the shortest route as dominant strategy then you can read this paragraph the other way round and the veterans loose every time, the reason being of course that "most players are veterans" and in this game if you play like most of the people play you lose.
 
So, does this sound like a viable game concept to you? Or is it, essentially, glorified rock-paper-scissors?

Share this post


Link to post
Share on other sites

Therefore this either comes down to balancing game constants in the traditional sense, or to the removal of game constants altogether. In the latter case, which is far more interesting as brainstorming material, I think that the real challenge becomes not to prevent the game from becoming evolutionary stable, but to prevent it from degrading into a game of chance, when chaos takes over and no strategy can emerge other than making a decision and hoping for the best.

It would be pretty impractical to remove the 'constants' entirely, because there both has to be some quantity that reduces as crowding grows, and something has to factor into the payoff matrix.

The term "game of chance" doesn't really apply unless you add a random factor in there. Picking between different pure strategies randomly to form a mixed strategy is a core concept in game theory, because it precisely represents the type of situation you describe. e.g. If everyone picks Rock, then the dominant pure strategy is to pick Paper... but then people would pick Scissors... then Rock... etc. Hence the dominant mixed strategy is to pick one of the three randomly.

 

Regarding your game concept, in game theoretical terms it doesn't seem particularly complex. There will be some equilibrium point between "pick the shortest route, likely to be popular" and "pick the longest route, likely to be least popular" that depends on the number of people playing the game, the length of the various routes, etc., and a sufficiently large player base will identify the set of routes that represent the best tradeoff. Assuming a simplified version of the game where you must pick your whole route before play, the dominant strategy would simply be a mixed strategy where they pick from that "tradeoff set" somewhat randomly. The actual dominant strategy will be doing exactly the same, but adjusting the route slightly to account for the other players' choices.

There are similarities here to Chess (pick one of several standard openings which are known to be good, then adjust) and Magic: The Gathering (build a deck usually fitting one of several archetypical decks, but adjust play to suit the opponent's decision). So it's clear that a good implemention can be viable as a playable game. But the crowding aspect is not an essential part of this property - all that is necessary is that it is a sequential (multi-turn) game where opponents can react to each other. The crowding concept potentially adds interest by forcing a larger number of strategies to be considered in games of 3 or more players, and that is interesting in itself.

Share this post


Link to post
Share on other sites
Thank you for your help. I am not an expert on game theory and it is encouraging to know the premise is viable. 
 
It looks like I have some studying to do if I was to come up with an appropriate graph for the game map, where every node has the following 2 properties:
 
1. Movement cost multiplier: This is the value that is multiplied to the number of players moving from this node to a connected node, in order to calculate the total cost for the move.
 
2. Idle net gain: This is the number of points awarded to the player for opting to skip a turn while staying on this node.
 
I am guessing that a random graph of the sort would not work, meaning it would not provide the players with enough viable options to consider, or "equilibrium points" that you mentioned, if I dared to use a term I do not fully understand. Any ideas on how a game theorist would approach this?

Share this post


Link to post
Share on other sites

Perhaps one thing that is not obvious is that "game theory" is not really "the theory of making games". As such, most people who make games do not use game theory to make them, and most experts in game theory do not make games. :)

As such, you're in relatively uncharted territory. Many game designers have a basic grasp of game theory but few would be digging deep into the concepts at this stage, instead preferring to create their abstract game based on other criteria.

For your situation, a random graph is a decent starting point, but then you'd want to analyse it for any obviously dominant strategies and remove or adjust them. One approach might be to code a simple AI that would play the game according to different strategies (e.g. "pick randomly at each point", "pick randomly from one of several predetermined routes", "always pick route X") and see if any of those are obviously dominant by measuring the average payoff. You can then test the crowding aspect by increasing the number of AI players that use a certain strategy and seeing how the payoff declines, and whether that decline is sufficient to keep it in check. You can also perform iterative tests where AI players may change their behaviour (e.g. keep current strategy 75% of the time, or switch to the last game's winning strategy 25% of the time) to see if the population evolves towards a small set of strategies, or towards just one, or whether it oscillates, etc.

Armed with this data, you can make adjustments to the graph and re-run the process, seeing whether it improves the behaviour you see (or otherwise).

Share this post


Link to post
Share on other sites

The game you are looking for is called economics.

 

When someone first discovers a popular product, there will be a huge demand, and Low supply for now, so prices are high. As the initial man reaches demand, prices drop but the volume is high enough that he still gains a profit more massive than when supply is low.

 

Now enter the other players. They all see the profit and want in on the action. A few of them will drop profits as options are introduced. But more players will evetually tag in. So demand is low, and supply is high. In fact the profits continue to fall till they are marginal or loosing money.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this