From a game theoretical point of view, the best way to analyze this problem is to model it as a lottery and organize the choices and outcomes in a tree. You'll have to sit in the game theorist's shoes and pretend you're looking at two third parties, not yourself and one other player.

Here there are two ways of attack...let's call them A1 and A2. Let us call the two ways that your opponent can defend as D1 and D2. A1 will succeed only if the opponent plays D2, and A2 will succeed only if the opponent plays D1. There are four possible outcomes:

A1D1, A1D2, A2D1, A2D2.

Each outcome carries for you a different reward, or payoff. It is convenient to use a utility function U(x) that assigns these utilities. For instance, suppose you play A1 and the opponent plays D1, then the payoff you get is U(A1D1)...in this case, since A1 is blocked by D1, we get U(A1D1)=0. Similarly, U(A2D2)=0. For U(A2D1) and U(A1D2), any positive values will work, but for now, we can assign the value 1 to these functions.

Furthermore, each outcome has a different probability of occurence. It is convenient to use a probability function P(x) that assigns these probabilities. For instance, the probability of your opponent using D1 would be P(D1), and the probability of your opponent using D2 would be P(D2). The values P(A1) and P(A2) would be the probability that you would use the moves A1 and A2 respectively, if you were a rational agent, a third person. All values of P(x) are between 0 and 1. You will have to evaluate the probabilities of the four outcomes above as follows:

P(A1D1) = P(A1)P(D1)
P(A1D2) = P(A1)P(D2)
P(A2D1) = P(A2)P(D1)
P(A2D2) = P(A2)P(D2)

Note: You cannot assume that the probabilities for D1 and D2 will just be 50-50 because your opponent is not deciding his moves by flipping a coin...he is looking at his position, other countrys' positions, and other information such as what a third player might have promised in terms of support, etc. Similarly, you have to evaluate the probabilities of yourself moving A1 and A2 by examining the information available to you and imagining how you would act if you were a third person.

Then, you decide whether to use attack move set A1 or attack move set A2 based on your expected value E(x) for each of these moves. E(x) is given by the following formula:

E(A1) = P(A1D1)U(A1D1)+P(A1D2)U(A1D2)

Since U(A1D1)=0 and U(A1D2)=1, E(A1)=P(A1D2)=P(A1)P(D2).

Similarly, E(A2) = P(A2D1)U(A2D1)+P(A2D2)U(A2D2). Since U(A2D1)=1 and U(A2D2)=0, E(A2)=P(A2D1)=P(A2)P(D1).

Now you decide your moves based on which E is higher. If E(A1)>E(A2), you move A1...and so on.

Depending on your E value, the A that you choose is the optimum strategy in the game.

You may also think the opponent will make the same calculation and play the opposite move.

This already assumes that the opponent is making a similar calculation.

I thought that sort of dilemma was what game theory was meant to cut through..

@ava2790 this is interesting, even if a little over my head. How do you know this stuff? Are you a student? How could I go about learning more?

It is possible to do an analyses by assuming that your opponent is a little stupid and not making informed choices rationally. But it's more long winded and no fun.

@spyman - I am an economics major. Any elementary gametheory text will give you the info needed to analyze simple games like this. Of course, taking classes with a leading mechanism design theorist can help sometimes :-p

I am a mathematics student with some interest into game theory. From what I understand, you should not only consider the basic strategies A1 an A2, but also mixed strategies: with probability p i choose A1, and with 1-p i choose A2. Then both players choose such a mixed strategy, in a way that if their opponent knew he was using that strategy, he couldn't take advantage of it.

In a simple example: there are two attacks, two defenses. If you choose A1 always, your opponent knows this, and he chooses D1 always. But if you have a 50-50 mixed strategy, you're opponent has 50 percent change of losing a center, no matter what his strategy is.

In this case: three attacks, two defenses. You should mix the options 50-50 as a defender, and as an attacker you should try the first attack 50 percent of the time, and the other you can just mix anyway you want.

Mind you, this analysis assumes that there is no difference between the centers. As Ava explained, U(A1D1)=U(A2D2)=0, etc. We all know this is not the case. I'd rather lose belgium than paris, if i'd be playing france. Perhaps there is a chance that your ally stabs you, etc. These considerations should be included into the U function. Then the analysis is the same, and then there will probably not be a 50-50 split, but a split which focuses more on the important centers.

Thanks for that addendum, basvanopheusden. A mixed strategy is of course more flexible than a pure strategy, and there is plenty of information online regarding pure and mixed strategies for further reference.

Thanks guys. Final question though - in 'a split which focuses more on the important centers', what's the optimal strategy if you know your opponent weights the centres with the same importance you do? Because if he's more likely to defend Paris than Belgium, then surely you should put a higher weight on attacking Belgium, even though taking Paris has a higher payoff.

Mixed strategy is what the most successful poker players use because it keeps their opponents from getting a read based on position/preflop bet size.

ava's analysis is more applicable than the minimax strategy to much diplomacy, but if you are totally lost, then the following logic should be applied:

Let's call your strategies A1 and A2, and his D1, D2 and D3

where A1 defeats D1, and A2 defeats D2 and D3, and the value of each victory is 1, whilst the value of each non-victory is 0 (measuring in SCs say)

Then we have:
......A1..A2
D1..1.....0
D2..0.....1
D3..0.....1

We can immediately see that D2 and D3 are equivalent to one another, so there is no point in treating them separately, so let's consolidate them into "DD" meaning "Either D2 or D3, they make no difference"

......A1..A2
D1..1.....0
DD.0.....1

And now we can see that it is a simple, symmetrical situation, so you should play A1 and A2 with equal probability.

Meanwhile, the defender should play D1 and DD with equal probability, but it makes no difference whether he plays D2 or D3

Now for the answer if the centres are of different values coming up:

Haha I was typing up a long one for that, but you can take this one, Ghost ;)

Here's an interesting article, related along the vein of game theory in end game choices
http://devel.diplom.org/Zine/F1995M/Dreier/Endgame.html

Ah. Good ol truth tables

Suppose that in the win of A1 over D1, you get a centre that is more important, worth 1.1, in the win of A2 over D2, you get a centre that is averagely important, worth 1 and in the win of A2 over D3 you get an unimportant centre worth only 0.9

Now our table is:


......A1....A2
D1..1.1....0
D2..0.......1
D3..0.......0.9

Before we start the anaysis, we can see that from the defenders point of view, D2 is never as good as D3, so he won't play D2. We can thus remove it from the table to give:

......A1....A2
D1..1.1....0
D3..0.......0.9

Now we want what is known as a maximin strategy (I shan't define that here, but the point is that it takes the expected result out of your opponent's hands)

Suppose for the moment that your opponent plays pure strategy D1, and we play A1 p of the time and A2 1-p of the time. Then our winnings are 1.1p

If he plays pure strategy D3, our winnings are 0.9-0.9p

We can plot these on a graph:

http://7893772042130947902-a-1802744773732722657-s-sites.googlegroups.com/site/phpdiplomacytournaments/test-1/game%20theory.png?attachauth=ANoY7coHocsW-45nrXQtk1bAua--eBL8asqOLiPCBGdfVaz5u2jxJzo1n0I-d4hlMRbbFvwFd4PUIwtCwbQdVGQA3wb9P0LHFvxOpYO4cUriwejUxTZQdo39Dv5EyvNjz_1JzMTXbnCzPi43hSrFFZyInoxErM8CAUT7VK6PYzwfsjBCVWfJ1W07sZuXBMQBOlmVWOOQ9v8mkRNISFZNsHJLnjWT8VJf5rctAgrE0vmIABcvZb7Gfe4%3 &attredirects=0

The green highlighting shows the minimum expected result for each value of p, and the yellow blob is the maximum possible for this value.

So the value of p you want is the value you have for that value, so you need to find the value of p where:

1.1p=0.9-0.9p

2p=0.9
p-0.45

Therefore you should play A1 45% of the time, A2 55% of the time

The graph again:

http://tinyurl.com/3a9jwwl

TGM, your values for the payoffs affect your final probability...just making a note of this. If the numbers were 1, 2 and 3 you would arrive at a different solution.

I know, I was showing the method by means of an example.

Ah, now, that is interesting. The implication being that the more important the centre, the less often you should aim to take it....?

...which I see is exactly the conclusion that the article yebellz links to comes to.

Sometimes, you can outguess your opponent. If you think france is an risky player who thinks he can outsmart others, he will put more weight on belgium as opposed to paris. If not, you should go for belgium more often than paris.

Ghost - is it possible to prove that P(A1)>P(A2), strictly speaking? I believe that is precisely the conclusion hopsy has come to from your example.

It all boils down to knowing your opponent. All theory is good, but we are talking about people here, and you will need to know what type of the player you are playing against in order to make a good decision.

The analysis you've received are correct, however when it comes to fill in real numbers and calculate the chances, you have a big problem - unless you know who you are playing against (AKA "metagaming" on this site...)

Not true, Bask. You may have run into similar situations a couple of times before in this game against this particular player. If he acts predictably, you aren't metagaming to assume he'll do the same thing again. If he always chooses the reverse option from last time, you can predict he will agian and adjust accordingly. But it is always within the same game and therefore not metagaming at all.

How can knowing your opponent be "Metagaming"? I look at my opponents games all the time. That way you can get a measure of how far you can trust them. It doesn't mean I won't work with them, just means I know when to stop working with them.

Also, I would think it might be best to do this analysis from your opponents perspective rather than your own, then you can make the appropriate move.

It is metagaming (meta means outside of), but we return to acceptable versus unacceptable metagaming. This is completely acceptable and, as it happens, human nature.

"Ghost - is it possible to prove that P(A1)>P(A2), strictly speaking? I believe that is precisely the conclusion hopsy has come to from your example."

Well, under the axioms of game theory, the kind of logic I presented will always hold. However, diplomacy is much more than game theory

And game theory is just theory. It makes certain assumptions about the human thought process which don't take into account the emotional aspect and past history of the players in question.

All theory makes simplifying assumptions. That doesn't make it redundant. It just means you shouldn't rely entirely on theory.

or the effect that a couple of carefully placed words can have.

let's assume we're talking about 1901 fall moves.

Italy has moved to piedmont, france has moved marsielles to spain.
Burgundy is empty and so is MAO.

Now France has two options for spain - safe move to mars OR riskey hold.
Italy has two options - pointless move to mars OR equally pointless hold.

In the best case for france (Spain holds, Piedmont holds OR Spain bounces Piedmont in Mars) - The french player picks up Spain AND can build in Mars (likely a fleet to use against Italy)
In the middle case for France (Spain moves to Marsielles and Piedmont holds) France neither picks up the build nor is able to build in mars.
In the worst case for France (Spain holds, Piedmont takes mars) Italy has it's one positive result.

Pied - Attack / Hold
Spain Attack +1.5 +0
Hold -1 +1.5
(for France - relative values for italy reversed and counting the option to build in mars as +0.5 for france)

This is a fairly simple setup and can be analysed as above - but as Italy having Austria tell france Italy is DEFINITELY holding, you can greatly affect the outcome. (though it depends on the diplomacy)

Still i can't figure out the mixed strategy? anyone?

The mixed strategy is simply attack MAR with probability 1 and hold PIE with probability 0.

how is that mixed?

http://en.wikipedia.org/wiki/Strategy_(game_theory)#Pure_and_mixed_strategies

yeah, so in this case you're claiming that the ideal mixed strategy is a pure strategy (or a degenerate mixed strategy - let's not mince words...)

Still the carrot for France is that +1.5 vs +0...

orathaic, what you do is simply draw the two graphs again.

Looking at it from Italy's point of view, if France goes pure holds he has 1.5-2.5*p where p is the proportion of the time Italy holds, and if France goes pure move then he has 1.5p

The minimax is when 1.5p=1.5-2.5p
p=1.5/4=3/8

So Italy should hold 3/8ths of the time.

Similarly, France should hold 3/8ths of the time

ignore that post for a mo, I've screwed something up I fear

Corrected:


orathaic, what you do is simply draw the two graphs again.

Looking at it from Italy's point of view, if France goes pure holds he has 1.5-2.5*p where p is the proportion of the time Italy **attacks**, and if France goes pure move then he has 1.5p

The minimax is when 1.5p=1.5-2.5p
p=1.5/4=3/8

So Italy should **attack** 3/8ths of the time.

Similarly, France should hold 3/8ths of the time

@Draugnar & TrustMe

There is a reason I put "metagaming" in quoting sign. You know my position about what other people call "metagaming" - I believe this is the whole point of this game, but lets not discuss it again.

If you will look at the post above (TGM about when to hold and when to move), you will clearly see that the assumption there that we are talking about an anonymous gunboat that is being played by people with flawless logic. Furthermore, it ignores the position that France and Italy will enter if the move will succeed or fails.

One more thing, regarding the "same player, same situation" remark. It is extremely hard to reproduce exactly the same situation on the board, especially with exactly the same players. The mere fact that players learn from game the game, changes the whole situation.

What I would like to say is that the only "certain" way to know what the other player is going to do is to make him suggest an idea, make him believe it is his idea, and make him be passionate about it.

Analyzing Diplomacy using game theory on the page of the forum is fruitless (unless you are gunboating vs anonymous players who are perfectly reasonable, and maybe not even then).

thanks TGM, i still don't know how to calculate it...

well mostly, also is -2.5 the relative difference - ie the italian gain plus the french loss, i'm not sure where you came up with the figure.

@Bask - 'Furthermore, it ignores the position that France and Italy will enter if the move will succeed or fails. ' - really, i had thought i added into my consideration the (rather arbitrary) value of having an extra supply center, and being able to build.

Everything else bieng equal, italy is either in peidmont/ mars, and france is either in spain or mars.

But losing mars is considered a loss for france no matter what, and gaining mars is considered a win for italy... How we value these win/loss situation is i admit entirely arbitrary.

Yes a game theoretic minimax answer will tell you the optimal mixed strategy, and playing thus you will on average do better.

That it doesn't guarentee you the right guess every time doesn't matter, it is only on average over many guesses that you will gain a maximum advantage. Though a game is made up of many such decisions, you may not win even if you make hte best guess everytime.... So limited use, but not completely fruitless.