From: Gary Wong <gary@cs.arizona.edu>
Subject: Re: many players' bug?
Date: 13 Apr 2000 22:11:40 -0700
Newsgroups: rec.games.abstract
Summary: [missing]

Claude Chaunier <chaunier@handy.univ-lyon1.fr> writes:
> Roger Carbol wrote:
> > Although two-player games are also multi-player games, I
> > get the impression you're discussing games where
> > N > 2 and possibly N >> 2.
> 
> Right, multi isn't a happy name. So, N>2, but not necessarily
> very big, I'm even especially interested in N=3 players. The
> gap is already blatant from N=2, most surprising, and maybe
> free from possible more complex phenomenas at higher orders.

Quite right; n=3 is an entirely different problem than n=2.
Unfortunately, the problem doesn't seem to be much simpler for n=3
than n>3; there is a huge gulf between existing theory for 2-person
games and the general n-person case.  The possibility of collusion
(and all the associated cans of worms it opens up) seems to be the
culprit, rather than any quantitative complexity.

> > There's a fairly well-known phenomenon in N > 2 games
> > called "King-Making" (at least, that's what I've heard it
> > called -- I'm not sure I've ever seen anything very formal
> > on this)
>
> It's a pity there isn't anything formal on it yet. It's not what I
> have in mind but it's connected.

Actually I believe there is a great deal of theory on n-person games.
John Nash contributed many results in the early 50s; perhaps the most
important is the existence of (at least one) "Nash equilibrium" in
certain non-cooperative n-person games.  Unfortunately the
non-cooperative criterion is very restrictive.

There are two bibliographies on the WWW which will hopefully prove
useful:

  David Levine's <http://levine.sscnet.ucla.edu/General/more.htm>
and
  Paul Walker's <http://william-king.www.drexel.edu/top/class/histf.html>

Cheers,
Gary.
-- 
        Gary Wong, Department of Computer Science, University of Arizona
            gary@cs.arizona.edu     http://www.cs.arizona.edu/~gary/