Ice-cream vendors arrive one after another at a beach of length 1 and each chooses a spot; customers are...

In article <CpA9JF.JzE@and.nl>, Erik Buitenhuis <erik@and.nl> wrote:
>A question that came up in relation to the elections that were held in
>Holland yesterday.
>
>There is a theory that relates ice-cream vendors to politics. Suppose
>you have two ice-cream vendors on a beach of length `1'. The beach is
>loaded with customers who will buy their ice-cream from the vendor
>nearest to them. The two salesmen arrive at the beach in the morning
>(not at the same time) and choose their spot. Both salesmen will end up
>in the middle (call this spot `0.5') of the beach and will each have
>half of the sales. When the first vendor chooses a spot at e.g. `0.6',
>the other will choose spot `0.599999' and have 60% of the sales.
>
>Now what will happen when there are 3 vendors. What is the optimal
>strategy and what will be the market share for each one of them. Suppose
>they all know there have 2 competitors and they arrive one after each
>other.

What happens if the beach is a 1x1 square (still 3 vendors)?

-- Ren Maddox <lhmaddox@bnr.ca>

Making simplifying assumptions (in particular that equally desirable
choices are taken with equal probability), I think the optimal strategies
and winrates are:

Three players:
        #1 = 1/4                wins 3/8 on average
        #2 = 3/4                wins 3/8 on average
        #3                        wins 1/4

Four players
        #1 = 1/6                wins 7/24 on average
        #2 = 5/6 + epsilon        wins 7/24 on average
        #3 = 1/2                wins 6/24
        #4                        wins 4/24

Five players
        #1 = 1/8                wins 15/64 on average
        #2 = 7/8 + epsilon        wins 15/64 on average
        #3 = 3/8 or 5/8                wins 14/64 on average
        #4 = 5/8 or 3/8                wins 12/64
        #5                        wins  8/64

From these examples it appears that best first move may be 1/(2M-2)
where M is the number of players.

-- James Allen <james@crc.ricoh.com>

Consider a beach of length 1 and a number of ice cream vendors
A,B,C,... about to set up their stalls on the beach in turn.  There are
customers uniformly distributed across the beach, and each customer buys
ice-cream from the closest vendor.  I'm going to assume that each vendor
tries to maximise the minimum number of customers he can get.

I'll use the notation p+ to refer to the position just to the right of p
and p- to refer to the position just to the left of p.

Two vendors
-----------

If A chooses a <= 1/2 then B chooses a+.
A scores a, B scores 1-a
Therefore A chooses 1/2, B chooses (1/2)+, each scores 1/2.

Three vendors
-------------

If A chooses 2/5 <= a <= 1/2, then B chooses a- and C at a+.
Hence A scores 0, B scores a and C scores 1-a.

If A chooses 1/4 <= a < 2/5 [Editor: was "1/4 <= 2/5 < 1/2"], then B
chooses (2+a)/3 and C chooses a-.
Hence A scores (1-a)/3, B scores 2(1-a)/3, C scores a.

If A chooses a <= 1/4, then B chooses b=(2+a)/3 and C either chooses
a < c < b  or chooses b+.
Hence A scores at least a, B scores at least (1-a)/3 and C scores (1-a)/3
(there's an additional (1-a)/3 that will be divided between A and B
according to the whim of C).

So in order to maximise the minimum, A chooses 1/4; then B chooses 3/4
and C plays anywhere.  C scores 1/4, and A and B each score at least
1/4, with an additional 1/4 distributed between A and B according to the
choice of C.

Four vendors
------------

Too hard for me.

-- Gareth Rees <gdr11@cl.cam.ac.uk>

[ Editor: no answer for the square beach was collected. ]