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/

Copyright © 1994 John Conover, john@email.johncon.com. All Rights Reserved. Last modified: Fri Mar 26 18:58:39 PST 1999 $Id: 940503035344.8302.html,v 1.0 2001/11/17 23:05:50 conover Exp $