Re: Nash games theory

On Wed, 14 Jan 2009 05:46:08 -0800 (PST), pauldepstein@xxxxxxx wrote:

On Jan 14, 1:42 pm, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Tue, 13 Jan 2009 18:54:07 -0800 (PST), pauldepst...@xxxxxxx wrote:
A game is being played by more than 1 person.  This game has an
associated integer, N > 1.
The game consists as follows:  Each player secretly writes down a
number between 1 and N inclusive.
After these numbers have been written and all numbers are known to all
players, each player receives a monetary payout from the banker or
makes a payment to the banker.  [In other words, there are no
restrictions on the set of payouts.]  This payout depends, by a well-
defined set of rules, on which numbers have been written by each
player. [In other words, I am speaking of a class of games].
All the players are treated in the same way.  For example, if two
players have written down the same number, they will receive the same
payout.

Each player has the aim of maximising the expected value of the payout
she receives.

There's no such thing as the expected value of the payout unless
you assume that the other players are acting at random.

Honest. "maximize the expected value" is certainly not the
standard definition of "optimal strategy". Exactly what
"optimal strategy" even means when there's more than
two players is not at all clear to me, not that I know
any game theory.

_Given_ strategies for all the players there is an
expected payoff for each player.

In a two-person zero-sum game you can show
(possibly you need other assumptions) that
there exists a strategy S which is optimal in
this sense: Say E(S1, S2) is the expected payoff to
the first player assuming that player 1 uses strategy
S1 and player 2 uses strategy S2. Now define
m(S1) to be the _minimum_ of E(S1, S2)
over all strategies S2. Then m(S) is the
_maximum_ of m(S1).

That makes S "optimal" in the sense that no matter
what strategy player 2 uses the expected payoff to
player 1 will be at least some number O, and if
player 1 uses any other strategy then player 2 has
a strategy making player 1's expected payoff
less than or equal to O.

The reason the condition in the last paragraph
is a reasonable definition of "optimal" has to
do with the fact that it's a zero-sum game:
in trying to maximize _his_ payoff, player 2
is simulataneously trying to minimize
player 1's payoff. In a non-zero-sum game
the above is no longer a reasonable definition
of "optimal" as far as I can see. I don't know
what the right definition would be, nor how
to prove that an optimal strategy exists once
we settle on the definition.

Also in games with more than two players
things get much more complicated, because
strategies involving cooperation can come
in.

You're asking yourself why I don't just answer
the question. It seems to me that the question
simply _is_ much less well defined than you think.

Often the optimal strategy will be probabilistic -- write i with
probability a_i  where 1 <= i <= N.

If we can assume that there is a unique optimal strategy, such
problems can sometimes be solved by Lagrange multipliers -- the
constraint is that the sum of a_i = 1, and the function to be maxed is
derived from the set of rules.

_How_ is this function derived from those rules?

Not just being pedantic, it's an actual question.

It is assumed that each player uses this unique optimal strategy.

However, I have two questions:
When is there an optimal strategy?  When is the optimal strategy
unique?

Paul Epstein

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)

Thanks, David.
As usual, your posting is very helpful. I agree that the notion of
"optimal strategy" may be problematic.

Here's an illustration of what I meant by the method of Lagrange
multipliers. Here, the problem is trivial, and Lagrange multipliers
are completely unnecessary but hopefully it will illustrate my point.
Take the following game for two players. Each player writes down an
integer which can either be 1 or 2 (no other choices). Any player who
writes down 1 is paid 1 dollar, and any player who writes down 2 is
paid 2 dollars.
My strategy is to write down 1 with probability a1 and 2 with
probability a2. It remains to solve for a1 and a2.
Then the constraint is a1 + a2 = 1, and the function to be maximised
is a1 + 2*a2.
This can (but shouldn't because common sense is more appropriate) be
treated as a Lagrange multiplier problem, and the solution is to write
down 2 100% of the time.

Yes. But in this "game" what you win has nothing to do
with the strategy of the other players.

For more complex examples, the strategies of all the players need to
be considered but, in some simple examples, we still get a Lagrange
multiplier problem.

For example?

After replying to your post I looked at the wikipedia article
on Nash equilibria to make certain I wasn't the only one
confused. Search google for "Nash game wiki" (without
the quotes), click on the first link, look at the various
games there. They're all games that fit into the general
format you're talking about here. Pick _one_ of them and
tell me what function f you're talking about that we should
maximize using Lagrange multipliers.

If there is such a thing as a "unique optimal
strategy", then we can assume that all players use this strategy.

??? That makes no sense. Surely you meant "if there is a unique
optimal strategy then...".

My point being that "There is such a thing as a uop" and
"there is a uop" are very different. Yes, if there is a uop
then we can assume all the players use it. But before
it makes _sense_ to assume that there is a uop we need
to know what the phrase "optimal strategy" _means_!
And in the general situation I have no idea what
"optimal strategy" even _means_ Honest.

Before asking or saying any more about optimal strategies
you should _define_ "optimal strategy". I know what we
mean by a strategy here - exactly what criterion makes
a strategy "optimal"?

Actually, the above is wrong because the constraints a1 >= 0 and a2
= 0 need to be considered. I need to research this. I believe this
theory has been named after Tucker if I remember correctly.

For the two-person zero-sum theory you outline, when is the optimal
strategy unique?

I don't know, but surely there are answers to this out there.

Thanks,

Paul Epstein


David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
.

Relevant Pages

  • Re: Nash games theory
    ... Each player secretly writes down a ... If we can assume that there is a unique optimal strategy, ... Consider the following three people game. ... better than the "optimal" move which only had expectation zero. ...
    (sci.math)
  • Re: Nash games theory
    ... Each player secretly writes down a ... If we can assume that there is a unique optimal strategy, ... Consider the following three people game. ... No move can have an expectation greater than zero, as that move would be better than the "optimal" move which only had expectation zero. ...
    (sci.math)
  • Poker Strategies Teil 1 Author Selzer-McKenzie
    ... Texas Hold’m Poker Secrets and Strategy ... deals around until each player has two cards face down. ... If there is more than one player left in the game at the end, ... The second round of betting (after the flop) is in units ...
    (de.etc.finanz.misc)
  • Re: Play to Win - counter-intuitive example
    ... activities...Collusion to alter the results of a game". ... Since I really don't see what function it serves, given PTW, I'd say it should ... the rulebook when they're in conflict with the goals written in the rulebook." ... except to make sure no single player gains a second one to get a game win. ...
    (rec.games.trading-cards.jyhad)
  • Federer blog - February/March 2007 ...
    ... it's the greatest player of all time here". ... Pete, how's it going?" ... a huge weakness in my game as I always piss ... to play tight matches, due to ...
    (rec.sport.tennis)