From: Marc.Ringuette@GS80.SP.CS.CMU.EDU
Subject: Re: New game: Think Small
Originator: mnr@GS80.SP.CS.CMU.EDU
Organization: School of Computer Science, Carnegie Mellon
Date: Sat, 21 Nov 1992 06:42:00 GMT

Daniel Shoham's reasoning (backwards from assuming a 1/N
probability of winning for any choice by the Nth player) is
interesting, but isn't quite correct.  You see, it might be the case
that _no one_ wins the contest.  In fact, for 40 people using optimal
strategy, the probability of a 41st player winning is uniformly 1/44.2
for any x he chooses....and the chance of nobody winning is 1/44.2 .

I took a different approach in computing the optimal strategy:
assuming all N players use a probabilistic strategy s(x) which
specifies a fixed probability of choosing each x, I compute the
probability that an N+1th player can win by choosing a number y.
Rather than reformat the equation, here's the code: (input is y and the
function s(x):

	sum=0.0;
	for (x=1; x<y; ++x) {
		sum+= (s[x]/norm)*N*pow(1.0-(s[x]/norm),N-1.0) * (1-sum);
	}
	return (1-sum)*pow(1-(s[y]/norm),N*1.0);

I implemented a simple iterative search for the best function s(x) by
taking an initial s, finding the number w with maximum probability of
winning, and increasing s(w) for the next iteration.

Just for your interest, here's a histogram of s(x) for N=40:

s(x) =    0.00                       0.05                             0.10
          ---------------------------------------------------------------
  x =  1: ************************************************************
       2: ***********************************************************
       3: *********************************************************
       4: ********************************************************
       5: *****************************************************
       6: ****************************************************
       7: **************************************************
       8: ***********************************************
       9: ********************************************
      10: *****************************************
      11: **************************************
      12: **********************************
      13: *****************************
      14: ***********************
      15: ****************
      16: ********
      17: **
      18: *
      19: 
      20: 


It sure looks like a binomial distribution, but I still haven't worked
out the closed form.

Here's the C code for my iterative solver - have fun!


-- Marc Ringuette (mnr@cs.cmu.edu)



#include <stdio.h>
#include <math.h>

#define MAX 40
#define N 40
#define ITERS 2000
#define delta 0.01
double s[MAX],norm;

double win(y)
	int y;
{
	int x;
	double sum;

	sum=0.0;
	for (x=1; x<y; ++x) {
		sum+= (s[x]/norm)*N*pow(1.0-(s[x]/norm),N-1.0) * (1-sum);
	}
	return (1-sum)*pow(1-(s[y]/norm),N*1.0);
}

main()
{
	int i,j,maxj;
	double w,maxwin;

	norm = 1.0;

	for (i=1;i<MAX;++i) s[i]=0.0;
	s[1]=1.0;

	for (i=0;i<ITERS;++i) {
		maxwin= -1.0;
		maxj= -1;
		for (j=1;j<MAX;++j) {
			w=win(j);
			if (w>maxwin) {
				maxwin=w;
				maxj=j;
			}
		}
		s[maxj]+=delta;
		norm = norm + delta;
	}

	for (i=1; i<MAX-1;++i) {
		printf("s[%2d] = %.6f, win[%2d]=%.6f\n",i,s[i]/norm,i,win(i));
	}
	printf("\n\n");
	for (i=1; i<MAX-1;++i) {
		printf("%2d: ",i);
		for (j=0;j<(60/s[1]*norm)*s[i]/norm;++j) printf("*");
		printf("\n");
	}
}