From: John Conover <john@email.johncon.com>
Subject: Re: Re[4]: Hi
Date: Mon, 2 May 1994 20:53:30 -0700 (PDT)
Raymond Werner writes:
>
> But JOhn, what is a "computable criterion"? What if I want my thinking
> companion to discern the next most fundamental underlying principle and then
> apply it to resolve the conflict, rather than having programmed it into the
> system in advance?
"Computable criterion," means that it could be "calculated." Or more
precisely, computable, in a finite number of steps. It really means
that it could be figured out in a systematic, or mechanical (ie.,
procedural) fashion. For example, voting and priorities can not.
This follows from the "theory of computability." In a nut shell, there
are different types of computability:
1) Polynomial (P), that can be accomplished in polynomial
time, (including linear time) like multiplication of two
integers. Doubling the precision of the integers only results
in doubling the amount of time to do the multiplication. DES,
etc. operates in polynomial time.
2) Non-deterministic polynomial (NP) which can only be figured
out in "exponential time," supposedly, (ie., increasing the
size of the problem by one unit, doubles the execution time.)
Linear programming is an example. These are generally a
combinatoric exhaustive search problem, like given a number of
cities that a salesman has to visit, find the shortest path to
do so (ie., the "traveling salesman problem.") The key here is
that the search time is proportional to the number of
combinations, but I can definitely tell which path is best,
(because I can simply compare the length of one path against
another, numerically.)
3) "NP hard" problems. This is like 2), but there is no way to
determine which solution is "better." (So obviously, you can't
find the optimum.) Auto-place software would be an
example. You generally have to have a "heuristic" algorithm to
make things work-like some AI, or expert system/fuzzy
logic. Note that these problems are not "computable." Voting
and priorities fall into this class of problems. (Although you
can compute "approximately good" solutions using heuristics.")
It should be pointed out that it is not clear whether NP problems are
ALWAYS exponential-although most theoreticians believe so
(epistemologically,) it has NOT been proven and remains one of the
nagging "core" issues of computer science. Further, there seems to be
no solution on the horizon, but information theoretic methods are
generally considered to be the best avenue of approach-although most
of the heavy duty thinkers of CS have attempted to address the issue,
no one has yet succeeded. (It is worth a Nobel to prove that P is
really NP.)
>
> Also the system would need a provision for accepting many different value
> parameters. The ability to discern the next most fundamental underlying
> principle, I think, at least in the legal thought model, relies on determining
> what is acceptable to legal consumers.
>
What game theory does is to provide a probabilistic solution to those
problems where the payoff matrix can be defined for a group of
players, all of whom have choices that interact. Probably the most
famous is termed the "prisoner's dilemma." It is one of the classic
"social problems."
Consider two opposing players, A and B. Each has a choice of c or d. A
payoff matrix might look like:
A
c d
-----------
c |3,3 | 4,1|
B |---------|
d |1,4 | 2,2|
-----------
(payoff in dollars = dollars to a,dollars to b)
Thus if B picks c, and A picks d, then A would get 4 dollars, and B
gets one dollar. Note that it is not a zero-sum game (the worst you
can get is one dollar,) so there is an incentive to play. Note that
there is a "conflict of interest." Both players would do best and take
3 dollars each if they both play c. But the conflict is that if you
think your opponent is going to play c, you should pick d and let him
get 1 dollar while you get 4. But, your opponent, being just as
rational, also picks d, so you both get 2 dollars, instead of 3.
Note that no matter what B does A should pick d, since if B picks c, A
makes the largest amount possible, and if B picks d, A would make 2
dollars instead of the 1 dollar if A had picked c. This is the optimal
solution as per game theory.
Where the terms c and d come from is "cooperate" and "defect." In the
original game, two prisoners are separated by police who are
interrogating the prisoners about an alleged crime. Does a prisoner
"snitch" on his buddy (eg, "defect",) or remain loyal (ie.,
"cooperate" with his buddy.) Obviously, the prisoner's best solution
is to defect.
A slightly more complicated version is called the "iterated prisoner's
dilemma," in which successive games are played. It also has the
distinction of being the model, used by RAND corporation, to model the
nuclear arms race. In this case, the "tit for tat" solution is the
best solution found (but not the only solution.) A will play whatever
B played in the last game, ie., if B defected (d) the last game, then
A will defect this game. Likewise, if B cooperated the last game, then
A will cooperate this game. (Note that when B plays d, the next game A
will "punish him" by defecting-A's strategy is to force B to
cooperate.) Thus, although B will have a "conflict of interest" in
wanting to defect, he will be "punished" later when A defects, and it
will have cost B one dollar. It is an important concept that the "tit
for tat" solution forces your opponent into a "coalition" strategy.
The problem has a rich historical perspective, BTW. J. von Neumann
once made the statement that "the reason that we find no life in the
universe is that they probably existed, could not solve the prisoner's
dilemma, and destroyed their self." He was working for RAND at the
time, and was doing theoretical research on the nuclear arms race.
Note that it is also similar to corporate politics, (ie., the
functional heads of departments can cooperate, or defect and hate each
other.)
There are several other related social games. One is the "Mexican
Standoff." Your best game scenario is to shoot first, (obviously, this
game can not be iterated.) Another related game is a nice parlor game
(DO NOT EVER DO THIS WITH PEOPLE YOU LIKE) and is called the "dollar
bill auction" (which was also used as a game theoretic model in the
cold war.) The rules are that you, as the game moderator, are going to
auction a dollar bill to the highest bidder, who will pay whatever the
highest bid is for the dollar bill-all bids must be higher than the
last, and the game ends when there are no more bidders. It is like any
other auction, except that the next to the last bidder must pay you
what he bid, and get nothing.
You will find, that like arms races, the bidding escalates well past
the value of the dollar, and married couples go home in separate cars.
This has been used to model economic conditions, like being put on
hold-do you hang up, risking to loose the money you have invested in
the call, or stay on, with no guarantee that anyone will answer. A
similar scenario is standing in line at an amusement park. Also,
labor/management disputes (after a walk out/strike) are the same
thing. The Persian gulf war was also rich in "dollar auction"
rhetoric.
The game theoretic solution, BTW, if you MUST play (it is better not
to,) is to assume you have a "stake." Suppose it is $1.58. You must
bid first, and you subtract the payoff ($1) from your stake, and bid
the remainder, $.58. As crazy as that seems, if you MUST play, and
work through the logic you can see it is the best bet.
>
> In order for people to submit, willingly, to a legal system, the system must
> provide an adequate amount of "justice", otherwise the system will be tossed
> out. Typically, the purpose of the legal system is viewed as being dispute
> resolution/conflict suppression. In other words, somebody wins and somebody
> loses but the dispute is resolved, the conflict is over and people get on with
> their lives and businesses. If the reuslts of the dispute resolution process
> are right sufficiently more than they are wrong, people will accept the process
> as providing "justice". In other words, legal process does not provide the
> "right" result, it provides a procedure which produces the "right" result often
> enough not to provoke legal consumers to the extent that they want to toss out
> the system.
>
> Therefore, the thinking companion would need to be able to model different
> population mixes wherein each mix had different expectations. How does this fit
> in to the game theory world?
>
Probably a better example is the game of Mora. (The game is very old,
being mentioned in Sanskrit-the modern version is
"paper/scissor/rock.")
The game is played between two players and, in its simplest version,
goes as follows: The two players move simultaneously. Each shows
either one or two fingers, and at the same time guesses whether his
opponent is showing one or two fingers. If both players guess right,
or both guess wrong, no one pays. If only one player guesses right, he
wins from the other as many chips as the two players together showed
fingers.
If you construct the payoff matrix, you will find (the game is simple
enough that you can reason your way to the answer):
COLUMN
|--|---------------|--------
| |1 1 2 2 | Fingers
| |1 2 1 2 | Guess
|--|---------------|--------
R|11| 0 2 -3 0 |
O|12|-2 0 0 3 |
W|21| 3 0 0 -4 |
|22| 0 -3 4 0 |
|--|---------------|
|FG|
|iu|
|ne|
|gs|
|es|
|r |
|s |
The optimal strategy is that:
Row one and row four strategy should never be selected, and that row
two strategy should be selected, randomly, 60% of the time, and row
three strategy should be selected the remaining 40% of the time.
Likewise for the column player. The optimal value to the row strategy
is zero, so the game is fair, with no advantage to either the column
or row player.
This scenario has been used to model court room drama, between two
attorneys. Note that it gives a probabilistic solution, where the row
strategy would be pitted against the column strategy. The outcome is
determined by the which of the 4 strategies were picked by both of the
attorneys. Note that each attorney must keep his strategy secret, and
if they are to face off in different cases, they must mix up their
strategies so that the opponent can not detect a "pattern." In real
scenarios, the matrix size becomes very large (often in excess of 10K
elements-note that it is also exponential execution time on matrix
size.)
-JCC
--
John Conover, john@email.johncon.com, http://www.johncon.com/