Suppose two children are sharing a victory condition equally between them...

[jack]

You know the trick for two people to fairly divide a cake. ie. one person halves it, and the other chooses which half. I was thinking about this in the context of choosing rules for a boardgame, which might be asymmetrical, like Thud or Tafl. It may also involve random elements during the game.

Q. Suppose two evenly matched players Al and Ben would like some new rules, but aren't sure they can agree them fairly.

A. Let Al choose the rules, and Ben choose whether to play white or black. Al has an incentive to make the sides even.

Q. What if the sides are intended to be uneven? Say, it's traditional that white has a 2/3 chance of winning?

A. Let Al choose the rules. Ben, instead of choosing to play as white or play as black, chooses between "playing as black", or "Toss a coin. Only if you win the toss and the game as white, you win."

Then if Al defines the rules as desired, both Ben's choices give a 1/3 chance of winning, but if Al makes either side have a greater than designated chance, Ben can choose that for teh win.

Q. What if the advantage to white isn't known? Suppose there are a family of existing games where white has an advantage, but exactly how much isn't known? And we want to introduce an en passant rule or other change intended not to affect that advantage?

A. Hmmm. I'm not quite sure how to measure that. Can I try an intermediate step?

Q. OK. The players have a board and rules giving white an unknown probability P of winning. Al must estimate P at P_al, and then, what? Why is Al incentivised to make P_al accurate?

A. Let Ben choose either to play the game with Al as white or let Al win on a die throw with probability P_al. Al will not make P_al too low, or he'll reduce his chance of winning.

Q. That works to stop P_al being too low. What stops it being too high?

A. Um. You can't let Ben play white because white has an advantage already, and you can't adjust for it because you can't know what it is. You could let Ben let Al win with probability P²/P_al.

Q. No you can't. That's not guaranteed to be between 0 and 1.

A. Doh! OK, win with probability P² (eg. winning if he wins two consecutive games with the same set up), but count that as a payoff of winning 1/P_al games!

Q. I don't like that. I can just about buy that I might equate wining this with winning two of those, but to feel like I won 1/P_al times? It won't feel like it counts, which blows the incentive away.

Can you do it, where the only payoffs are 1, winning, or 0, losing?

That's as far as my thoughts took me. Can anyone solve that, or show it's impossible?

Some notes:

* A binary payoff of 1 or 0 is the same as 1 or -1. I don't think it makes any difference if it's zero-sum.
* I started thinking this about Magic:TG, but *tried* to simplify the final question I was considering.
* We assume that the players have enough experience that they fairly can estimate the probability of winning.
* Ideally you'd never have to play multiple games, but I think we must allow that. Also approximations. It's cheating to say "Play 100 games and measure the proportion" though.
* In real life you might just agree the rules and cut the cake as fairly as you can anyway; but I'm still interested in the theoretical question.

Comments

[mair_in_grenderich]

Hm, I need some clarification.

We start with something like this:

There's some probability, P_A, that the player at position A at the "start" of the game will win the game (for a fairly broad definition of position).

Then we change the game by adding a move before the "start" which determines which of two players will be in position A.

If player X has a probability P_M of reaching position A from that move, then he has a probability P_W = (P_M)*(P_A) + (1-P_M)*(1-P_A) of winning the game. (Did I remember my elementary probability right?).

So we can construct the move so that P_M depends on P_A in such a way that

1. P_W = P_A

You can do this with your die-throwing mechanism.

Next, we state that P_A is unknown. Player Y gives player X an estimate of P_A, P_A', so that P_W' is player X's probability of winning and is equal to P_A', given your construction above.

Next you want to change the game so that

if P_A' != P_A, P_W' < P_W.

Now, P_W' is the actual probability of X winning, and is a function of both P_A' (through P_M) and P_A. And P_W is a function solely of P_A.


So, suppose we fix P_A at some point, and then maximise P_W' wrt to P_A', we want to find that P_W' is maximised at the point where P_A=P_A'. I think (among other options) some quadratic on P_A' will do that: I know the quadratics whizz off into infinity at the tails, but P_A' is limited to being between 0 and 1 anyway. Or you could take logs or something to catch them.

This feels like it's gone wrong somewhere, perhaps when I fixed P_A, but if not, er, we just need to work backwards from the function P_W' to find a mechanism that corresponds to it ;-)

[cartesiandaemon.livejournal.com]

That is paralleling my logic. I think the problem comes that in choosing the function so you can make a game with that probability of winning.

If the quadratic is something like 1-(P_A-P_A')^2, you can't say "And I win with probability that" because it includes the unknown P_A. You need to construct some rules, and that might not be possible for eg. 2.P_A.P_A'.

[mair_in_grenderich]

Ah! so P_M cannot be a function of P_A, because P_M sorta needs to be compatable by X, and X doesn't know P_A ? But that's basically impossible, right?

[cartesiandaemon.livejournal.com]

Well, it can be *some* functions of P_A. For instance, it can be P_A -- that player plays the game from position A, and if wins, takes position A. Or P_A^2, or 1-P_A, or p.P_A, where 0<1<p. What I'm not sure of is what function in general satisfy that, and if any of them represent a quadratic like the one we want. (It's more complicated than that because you need to make sure players will be playing as hard as possible. Or that one player always has to play White, which you get in magic because they designed the deck for that side. But we'll worry about those if we find any answer.)

[mair_in_grenderich]

where 0<1

that's pretty much universally true, isn't it?

[cartesiandaemon.livejournal.com]

Doh! Did you see the html? It ate my post! Though it was still wrong. I meant to say,

Well, it can be *some* functions of P_A. For instance, it can be P_A -- that player plays the game from position A, and if wins, takes position A. Or P_A^2, or 1-P_A, or p.P_A, where 0<p<1.

What I'm not sure of is what function in general satisfy that, and if any of them represent a quadratic like the one we want.

(It's more complicated than that because you need to make sure players will be playing as hard as possible. Or that one player always has to play White, which you get in magic because they designed the deck for that side. But we'll worry about those if we find any answer.)

[(Anonymous)]

Ever read The Strategy of COnflict by Thomas C, Schelling? This sounds scarily like some of the scenarios he studies.
Abner

[cartesiandaemon.livejournal.com]

Oh, interesting. *adds to list* Thanks!

[adrian2084.livejournal.com]

^.^

*gulp*

scary....

[cartesiandaemon.livejournal.com]

Scary?