[bushindo]

Four friends are playing a game. They have a pool of 100 dollars. Let's say that they have a unit square, with the corners located at (0,0),(1,0), (1,1), and (0, 1). Each player would sequentially take turn marking a point on the unit square. After the 4 markers are placed, the square is divided into 4 region, each centered at one of the markers. The rule for region division is that if any point on the square has the smallest distance to marker i, then it belongs to marker i. Apply that to the infinite number of points consisting the square, and you have the area associated with each marker. At this stage, each player wins an amount of the $100 that is proportional to their polygon's area. For instance, if player A mark a point so that he has 50% of the area, he wins $50 bucks. The remaining money are divided proportionally between the other 3.

Here is an example.

Here, there are four point marked on the square, and the square is divided into 4 regions by the rule defined above. Note that boundaries between any two regions are actually lines that are equidistant from the two marked locations. The pink point has the largest area (about 35%), so the player who placed that point wins about $35.

1) Suppose that you are playing this game, and you have to go first. Where would you mark your point? Assume your opponents will each try to maximize their winnings, with no collusion between any two party.

2) suppose that you are playing this game, and you're offered the choice to go first, second, third, or last, which would you pick to ensure the highest expected winning? Assume your opponents will each try to maximize their winnings, with no collusion between any two party.

Edited July 10, 2009 by bushindo

[Guest]

im about to go to bed after a night out, so this is without work. so the solution is probably definitely right.

if your first 1/3 the diagonal from a corner and if you had to choose a position i would think third.

[Guest]

if i were first player i'd probably play dead center of the square. this makes it the hardest for the other three players to get more than 25 percent, assuming they don't collude.

however i believe the best player to be would be fourth, as you essentially have perfect information, and can calculate how to maximize the most area.

[superprismatic]

An intriguing problem, indeed. I have some thoughts

which may be of some help in approaching it:

If we drop down a dimension to the unit interval, one would hope that the problem would be a lot easier. Even though we are now dealing with lengths instead of areas, it still seems to be quite difficult. Discussion of this one-dimensional case may prove fruitful. I thought of this because there exist one-to-one functions between the unit interval and the unit square (although they can't be continuous).

Edited July 11, 2009 by bonanova
spoiler added

[Guest]

(this is a voronoi diagram, isn't it?? Kind of reminds me of a multi player supermarket problem...)

Well, a two player optimal game is for player 1 to play in the exact center, which is sqrt(2)/2, sqrt(2)/2. Any other place reduces his payoff while increasing his opponent's. I think, that the optimal strategy, for player n+1 is to create the largest area from the current largest polygon on the board.

I can't quite get it up to three or more players. I'm thinking that each player should play along the diagonal at some portion of the number of players left or something. I just cannot think of where to go (i.e. the starting point).

My brain is fried now..

[bonanova]

1) Suppose that you are playing this game, and you have to go first.

Where would you mark your point?

On a diagonal, slightly more than 1/3 from a corner.

2) suppose that you are playing this game, and you're offered the choice to go first, second, third, or last

which would you pick to ensure the highest expected winning?

Assuming smart play, 3^rd.

Assuming greedy play, 4^th.

Note that the area you own after playing can only decrease as the game goes on.

Player 1 (P₁) begins by marking at (x, y).

P₂ maximizes his area, temporarily, by playing arbitrarily close to [x, y], toward the center,

in such a way that their boundary line has slope m = y/x.

Then

A₁ = 1/2 [mx² + 2xy + y²/m] If P₁ marks center then A₁ = 1/2.

A₂ = 1 - A₁.

There are two ways to optimize strategy: [1] Greedy, maximizing your temporary area or [2] Smart, maximizing your final area.

In the case of two players, Greedy and Smart obtain the same result: each gets half the square.

Continuing the Greedy algorithm, P₃ marks on the line joining the first two, arbitrarily close to mark₂.

That makes A₃ = 1/2 and shrinks A₂ to 0.

P₄ does the same, making A₄ = 1/2 and A₃ = 0.

Note that P₃ and P₄ can choose which preceding area to annihilate; only P₄ is assured of 1/2 the area.

Using the Greedy strategy, it's best to play last. [Question 2]

Using the Smart strategy, you worry about how the succeeding players will mark.

Between two moves, you choose the better of their worst outcomes.

To begin, let's suppose the first two marks are "vertically adjacent", splitting the square into upper and lower halves.

P₃ now might mark 90^o away so that he grabs 1/2 the area [say the left half] and leaves A₁ = 1/4 and A₂ = 1/4 to share the right half.

This is still futile for P₃, since P₄ can still reduce A₃ to a strip of zero width and claim A₄ = 1/2 to win.

So P₃ must mark an arbitrarily small but nonzero distance [say .001] to the left [say] of the first two marks.

Why does that matter?

Because P₄ will be better off [garnering 1/2 the area] marking adjacent to the right of the first two marks, leaving A₃ just short of 1/2.

Thus

A1 = .0005

A2 = .0005

A3 = .499

A4 = .5

So if P₁ and P₂ are Greedy, they lose essentially everything to P₃ and P₄.

If P₃ is smart, he comes arbitrarily close to winning.

A Greedy or Smart P₄ [the final player is Smart to be Greedy!] wins, with half the square.

Clearly P₁ and P₂ must not play Greedy.

suggests P₁ should mark at 1/3 diagonal from a corner. Let's analyze that case.

If P₂ is greedy he will mark adjacent, toward the center.

Then

A₁ = 2/9

A₂ = 7/9

P₁ knows that 2/9, being less than 1/4 and incapable of increasing, cannot win.

But he knows that P₂ [knows that he] can be wiped out by marking "adjacent", so it's worth analyzing this opening.

P₂ must mark some distance away [or risk being wiped out]. Say he marks center.

Then

A₁ = 25/72 = .347222... now capable of winning

A₂ = 47/72 = .652777... will be attacked in favor of A₁.

Suppose P₃ marks 2/3 diagonal from same corner [mark 2 lies directly between marks 1 and 3]

Then

A₁ = 25/72 = .347222 ...

A₂ = 11/36 = .305555 ...

A₃ = 25/72 = .347222 ...

So far, P₁ and P₃ have played wisely, while P₂ might have played better; we'll see.

Can P₄ win from this position? No!

If P₄ marks on the same diagonal, he at best shares some of A₁, letting P₃ win [or v.v.]

Suppose he marks 1/3 diagonal from a different corner; this yields

A₁ = 20/72 = .27777 ...

A₂ = 13/72 = .18055 ...

A₃ = 20/72 = .27777 ...

A₄ = 17/72 = .23611 ...

That's the best P₄ can do, so he cannot win this scenario.

But we can improve P₃'s mark by moving it slightly toward center.

This leaves A₁ unchanged, but increases A₃ at the expense of A₂, still leaving P₄ powerless to win.

In this scenario, P₃ wins.

That suggests P1 should mark closer to center.

It can't be on center, because then P₂ marks 1/3 diagonal from corner, exchanging their roles, making P₁ lose.

P₂ is squeezed by P₁ and P₃ if they mark equal distances from center along a common diagonal.

This suggests P₂'s best move is not center, but farther along the diagonal.

There's more work to finish this analysis, but it does seem clear, using Smart strategy,

that the first three players can cover the square well enough to make it impossible for P₄ to win.

P4 wins with Greedy play, but who wins with Smart play?

I would choose to mark third.

P₁ and P₄ seems to be a tossup for next favorable, although P₁ is perhaps better off.

P₂ seems doomed to lose in all cases.

[bushindo]

1) Suppose that you are playing this game, and you have to go first.

Where would you mark your point?

On a diagonal, slightly more than 1/3 from a corner.

2) suppose that you are playing this game, and you're offered the choice to go first, second, third, or last

which would you pick to ensure the highest expected winning?

Assuming smart play, 3^rd.

Assuming greedy play, 4^th.

Note that the area you own after playing can only decrease as the game goes on.

Player 1 (P₁) begins by marking at (x, y).

P₂ maximizes his area, temporarily, by playing arbitrarily close to [x, y], toward the center,

in such a way that their boundary line has slope m = y/x.

Then

A₁ = 1/2 [mx² + 2xy + y²/m] If P₁ marks center then A₁ = 1/2.

A₂ = 1 - A₁.

There are two ways to optimize strategy: [1] Greedy, maximizing your temporary area or [2] Smart, maximizing your final area.

In the case of two players, Greedy and Smart obtain the same result: each gets half the square.

Continuing the Greedy algorithm, P₃ marks on the line joining the first two, arbitrarily close to mark₂.

That makes A₃ = 1/2 and shrinks A₂ to 0.

P₄ does the same, making A₄ = 1/2 and A₃ = 0.

Note that P₃ and P₄ can choose which preceding area to annihilate; only P₄ is assured of 1/2 the area.

Using the Greedy strategy, it's best to play last. [Question 2]

Using the Smart strategy, you worry about how the succeeding players will mark.

Between two moves, you choose the better of their worst outcomes.

To begin, let's suppose the first two marks are "vertically adjacent", splitting the square into upper and lower halves.

P₃ now might mark 90^o away so that he grabs 1/2 the area [say the left half] and leaves A₁ = 1/4 and A₂ = 1/4 to share the right half.

This is still futile for P₃, since P₄ can still reduce A₃ to a strip of zero width and claim A₄ = 1/2 to win.

So P₃ must mark an arbitrarily small but nonzero distance [say .001] to the left [say] of the first two marks.

Why does that matter?

Because P₄ will be better off [garnering 1/2 the area] marking adjacent to the right of the first two marks, leaving A₃ just short of 1/2.

Thus

A1 = .0005

A2 = .0005

A3 = .499

A4 = .5

So if P₁ and P₂ are Greedy, they lose essentially everything to P₃ and P₄.

If P₃ is smart, he comes arbitrarily close to winning.

A Greedy or Smart P₄ [the final player is Smart to be Greedy!] wins, with half the square.

Clearly P₁ and P₂ must not play Greedy.

suggests P₁ should mark at 1/3 diagonal from a corner. Let's analyze that case.

If P₂ is greedy he will mark adjacent, toward the center.

Then

A₁ = 2/9

A₂ = 7/9

P₁ knows that 2/9, being less than 1/4 and incapable of increasing, cannot win.

But he knows that P₂ [knows that he] can be wiped out by marking "adjacent", so it's worth analyzing this opening.

P₂ must mark some distance away [or risk being wiped out]. Say he marks center.

Then

A₁ = 25/72 = .347222... now capable of winning

A₂ = 47/72 = .652777... will be attacked in favor of A₁.

Suppose P₃ marks 2/3 diagonal from same corner [mark 2 lies directly between marks 1 and 3]

Then

A₁ = 25/72 = .347222 ...

A₂ = 11/36 = .305555 ...

A₃ = 25/72 = .347222 ...

So far, P₁ and P₃ have played wisely, while P₂ might have played better; we'll see.

Can P₄ win from this position? No!

If P₄ marks on the same diagonal, he at best shares some of A₁, letting P₃ win [or v.v.]

Suppose he marks 1/3 diagonal from a different corner; this yields

A₁ = 20/72 = .27777 ...

A₂ = 13/72 = .18055 ...

A₃ = 20/72 = .27777 ...

A₄ = 17/72 = .23611 ...

That's the best P₄ can do, so he cannot win this scenario.

But we can improve P₃'s mark by moving it slightly toward center.

This leaves A₁ unchanged, but increases A₃ at the expense of A₂, still leaving P₄ powerless to win.

In this scenario, P₃ wins.

That suggests P1 should mark closer to center.

It can't be on center, because then P₂ marks 1/3 diagonal from corner, exchanging their roles, making P₁ lose.

P₂ is squeezed by P₁ and P₃ if they mark equal distances from center along a common diagonal.

This suggests P₂'s best move is not center, but farther along the diagonal.

There's more work to finish this analysis, but it does seem clear, using Smart strategy,

that the first three players can cover the square well enough to make it impossible for P₄ to win.

P4 wins with Greedy play, but who wins with Smart play?

I would choose to mark third.

P₁ and P₄ seems to be a tossup for next favorable, although P₁ is perhaps better off.

P₂ seems doomed to lose in all cases.

This applet really helps. Make sure that you overlaid a grid on the applet, and drag the points around to see how the area varies. Put your mouse over a point until the icon changes into a cross-hair, then you can click and hold to drag the point around.

http://www.voronoigame.com/VoronoiGameApplet.html

Bonanova's analysis i think makes the assumptions that P2 will make a mark that is immediately next to P1 (almost right on top of each other). While that gives P2 an immidiate edge, over the long run it is not a smart play, as bonanova observed that P2 is bound to do worst with that strategy. P2 is better off making a move that is in another corner of the square, either directly opposite P1 on the diagonal, or claim a point on the other perpendicular diagonal. In general, no player wants to play a mark so that it has a chance of being completely enclosed in a small triangle made up of the other 3 points.

I agree that P1 should claim a point off-center on some diagonal. If he claim the center, the other 3 can surround him (completely enclose him inside the triangle made up by P2-P4's markers), and he would have the smallest area. He should play a distance of about .3-.33 of the diagonal away from the vertex though.

Now, after playing with the applet a couple of times, I think that P1 and P2 does not have the chance to win. P3 and P4, depending on how they play, can get up to 28% of the area, regardless of how optimal P1 and P2 plays. P4,i think, is the best position to be. P4, by playing arbitrarily close to one of the 3 earlier points, can get an area above 25%.

it's early, and I need to go somewhere, I'll elaborate more later.

Edited July 12, 2009 by bushindo

[Guest]

1) Any point on a circle centered at the center whose radius is a bit bigger than 1/4 the square's side length.

2) Third?