On Thur, 23 May 2002 08:37:30 GMT, "Jim-dars" <jim-dars@attbi.com>

(Message-ID: <eT1H8.77003$071.32230303@typhoon1.we.ipsvc.net>)

wrote on the newsgroup: alt.recreational.math:

>1) N players.

>2) Each player chooses an integer between 1 and 100, inclusive. Each

>player chooses the number he wants, it is unknown to the other players.

>3) If two or more players choose the same number they are eliminated from

>the contest. The players know this.

>4) Once the eliminated players are removed then the remaining player who

>has the closest number to 100 wins the prize. The players know this.

>

>If you were in the contest what number would you choose if there were 100

>players and all the players knew there were 100 players?

To which I posted this reply on Tue, 20 Aug 2002 14:41:52 GMT,

(Message-ID: <3d625421.242129196@news-server.rochester.rr.com>):

john_bailey@rochester.rr.com (john_bailey) wrote:

Any number greater than 66 can be selected. If the other 99 players play optimally, my payoff will be 1/100. If they do not play optimally, my expectation is not computable.

Here is the general solution to pick a number.

Assume the players cannot collaborate but do use the same probability distribution from which to select their picks. Finding this distribution is the key to optimal play. It can be demonstrated that the optimal distribution results if each player's probability of selecting the i_th value is proportional to his expectation of winning with that selection. Note that by symmetry, all players will have the same expectations and hence the same probability of selecting the i_th pick. If the players follow this strategy, even if a player defects, any choice that player makes has an expectation value of 1/n where n is the number of players (and number of available choices)

This (partial)

table will illustrate:

Let q(i) represent the individual probability which every cooperating (but not collaborating) member of the group uses for the i_th selection.

Let r(i) be the remaining expectation value a successful selection can yield.

r(i) is the running tally of remaining expectation--if no selection greater than i (closer to 100)paid off, r(i) is the remaining expectation.

Let E_group(i) be the expectation of the group that one of the players will win with the i_th selection.

E_group(i) = n*r(i)*q*(1-q)^(n-1), it is the probability that one and only one player will have chosen that selection AND that no higher selection has been successfully made. (An unsuccessful selection is made when a higher selection was chosen by a player but one or more other players also selected it and hence the selection did not pay off.)

E_solo(i) is the expectation that a solo player would have of winning with a given selection. It is simply r(i)*(1-q(i))^(n-1) or in words, the probability of the game surviving to the i_th selection AND no other player (besides the solo or defecting player) choosing that selection.

Making E_solo(i) is a constant value in the table is because q(i) was forced equal to E_group(i)

This result is based on the following math:

E_group(i) = n*r(i)*q*(1-q)^(n-1) One of the players wins if no other player selects i.

E_group(i) = q The strategy requires q to be selected to make this equality true.

E_solo(i)= r(i)*(1-q(i))^(n-1) A single choice will win only if no other player selects it.

Making the appropriate substitutions:

E_solo(i) = E_group(i)/(n*q)

or

E_solo(i) = 1/n Which is of course, a fair return for the selection.

Solving for a q(i) so that q(i) = E_group(i):

q(i) = 1-(100*r(i)^(-1/(n - 1))

Now, using this equation and the iterative relationship: r(i -1)= r(i) - q(i) and iterating down from n, a complete set of values for q(i) can be obtained.

The complete set of q(i) values is as follows:

For i > 60, q(i) = 0

Some comments on the problem and my effort to solve it.

Of many problems which have caught my interest, this one sets a record in several categories for me personally. It has required the longest sustained effort. It has had the most dead ends. It has held my interest in spite of multiple dead ends. It has led to a variety of breakthrough solutions which turned out to be wrong. In all, it has been maddening but at the same time, and ultimately fruitful.

As a prelude, let me remark that since my exchange with JimDars earlier in the

month, I have been looking entirely at the question of what distribution of P(k)

would make it attractive for all players (100) to stick to the distribution and

not defect. In other words, if all players used for example, a completely even

distribution of choices over some range--say 100 to 66, but in the event a

player drew the value 66, what would prevent him from deciding to defect and

select 65 instead?

After several seemingly clever but wrong attempts to find a solution, I had reached a structure which seemed to me would either yield a solution or be the basis for proving there was no solution. It involved constructing a pdf which would be the basis for all players selecting randomly a choice, but which if any player found their randomized choice was unattractive, they could choose any selection they pleased BUT the math would require their selection be less than fair. Constructed by the rules such a distribution, every attempt produced a distribution which ultimately violated one of the constraints. A proof that a distribution that met all constraints was impossible seemed to be a possibility.

Even so, it seemed to me there had to be a common sense answer. Even if there was no mathematically correct solution, what should a player do in the pragmatic situation? At that point, I thought that at minimum a genetic algorithm should provide a pragmatic answer. I then conceived of a

half-baked genetic algorithm approach that was based on the idea that if a very large number of players (call them agents or demons in the GA parlance)played many games and tried various number selections, they would re-use winning ones.? This led to the idea that a simple fly-off of competing choices would find support in proportion to the return that choice gave.

As a first attempt, why not make the probability of a selection proportional to the return that selection gave. BINGO. When I tried this--using a brute force iteration

to make a P(k) = P(C wins k if no one else bids k) the surprising result was that the expectation for any choice that a defecting player made was 0.01. A fair return. No cheating!

After recovering from this shock I started looking at the underlying math and

came to understand that E_solo(k) the expectation for any choice k of a

defecting player is always related to P(C wins k if no one else bids k) by the

relationship E_solo(k) = nP(k)P(C wins k if no one else bids k) and under the

conditions being met by the forced equality results in E_solo(k) = 1/n. This

answers your question. 0.01 is built into the math.

The next turn of the page was made by web2k who posted the observation that:

P(k) = 1 - (n*r(k)^(-1/(n-1)) where r(k) is the remaining expectation not

already won by someone who bid higher than k. This insight eliminates the need

to make a brute force determination of P(k) and allows it to be calculated

directly.