The third of my responses to Hal. Also included at the end is a discussion of a "crypto simulation environment," as it comes up in the context of Hal's comments about game theory and the need to simulate iterated prisoner's dilemma types of problems in a crypto context.
Another argument sometimes advanced in favor of trustworthy escrow agents is the "iterated prisoner's dilemma". This refers to Axelrod's simulations of computer program agents which repeatedly interacted in a simple "prisoner's dilemma" game which captures much of the essence of the trust relationship (see his book "The Evolution of Cooperation").
I agree that evolutionary game theory has rich implications for real world cryptography, especially as it involves trading, interactions, cooperation, etc.
again). It has been argued that interacting pseudonymous entities satisfy the basic requirements for Axelrod's analysis because their pseudonyms have continuity over time, and people can use past history as a basis for future predictions (as in the escrow agency example).
There are some significant differences, though, between Axelrod's scenario and the anonymous agents we are talking about. One is the issue of pseudonym continuity. Although it is true that pseudonyms can have continuity, they are not forced to, unlike in Axelrod's experiments. One of the main reasons why cheating is a bad idea in
I think they are. Agents in an IPD (Iterated Prisoner's Dilemma) game can change their strategy...that is itself a strategy (e.g., "cooperate for the first 10 rounds, then nuke opponent"). Is this a change of strategy or a change in the agent? Maybe this is a semantic misunderstanding, but I don't see how "Pr0duct Cypher" or "Thoth" is not an Axelrodian agent?
Axelrod's runs is that the cheating is punished in future interactions (generally, by being cheated on in return). But of course in real life situations, cheaters don't hang around to receive their punishment. Implicit in the escrow cheating scenario above was that the agent vanishes. He isn't forced to stay in business to be cheated repeatedly by customers until they get even. He is able to opt out of the system. Axelrod's programs don't have that option.
Because Axelrod and his contributors [well-described, by the way, in Hofstadter's "Metamagical Themas" book] barely scratched the surface of how real ecologies, real economies work. Reputations do matter, as shown by another classic game theory result, the "game of chicken." An escrow agent that defects faces some repercussions (who trusts whom in such disputes is another issue, possibly handled by selective disclosure, a la Chaum, by reputation rating services, etc.).
Worse, a pseudonymous cheater has other options which allow him to continue to benefit from interactions with others while cheating. He can use multiple identities to, in effect, wipe the slate clean when he has cheated. This plays havoc with the crucial assumption in
Not in a "positive reputation" system. In a negative reputation system, it is true that an agent can alway flee and "start over" ("a fresh start'). But in a positive rep. system, each reputation only fairly slowly builds up a rep. [There are scams, such as the "brilliant penny" scam, to use collusive reputation setups to "inflate" a rep...nobody claimed it would be easy.] ...
know that they are reaching the end of their interaction period. In particular, on the last interaction, it is hard to avoid cheating since one knows that the other player will have no opportunity to apply punishment. But then, if it is a foregone conclusion that the last round will result in cheating, then it is hard to justify not cheating on the next-to-last round, since the results of the last round are foreordained and hence don't really provide feedback for what is done this time. This leads to a disastrous regress in which one finds that the stable cooperative solution collapses into a string of cheating interactions.
It's best that it never be known how many rounds there are to be. Sort of like not saying whether one is a source or sink of remailed messages...leave them guessing. (Or more mundanely, keeping the number of characters in a password a secret...the opponent doesn't have any "terminal" states or nodes.) I don't claim to know what the results are, this experiment not having been done that I know of, but looking around me I see people who interact with other people and who generally act as though "the game" will go on without limit. While they certainly don't act purely in a tit-for-tat way, they also interact as if their reputation for truthfulness, intelligence, etc. matters to them. (This is true even for most of the pseudonyms we have here, who give evidence of wanting whatever postivive reputations that have accrued to them to continue. Financial matters are not necessarily the same, granted.)
Although in real life it will not frequently happen that both parties know that a particular interaction is the last, it may be that one party will know. If a business has suffered reversals and is doing poorly, it may know that time is running out. In that case it will be
This is a good point, and needs more analysis. It may be that using a set of escrow agents will lessen the risk that any one of them is about exit, stage left. But bear also in mind that many escrow functions can be set up so as to have almost no benefits to the escrow agent if he defects and attempts to welch on the deal (kind of a "zero incentive" system). (This is how IOU systems often work.) ...
Based on these comments, it would be interesting to consider a variation of Axelrod's game, one modelled more on what we feel are the properties of a system of interacting pseudonyms. We might include the possiblity for competing programs to "quit" by retiring old pseudonyms and to create new ones. We might also simulate bankruptcy by having a rule that if the cumulative score of an agent ever became negative, it was out of the game. It would be interesting to see whether these changed rules again promoted the development of "nice" strategies or whether they tipped the balance in favor of cheating.
This might actually be a doable project for an interested programmer. It would be interesting to see whether others agree that it could shed light on the problem.
Here I agree most strongly with Hal. I have described my interest in this area to several Cypherpunks and their friends, including Nick Szabo, Eric Hughes, and Ted Kaehler (one of the developers of Smalltalk). The "protocol ecologies" idea I talked about here a month or so ago is related to this. To wit, building ecologies of interacting "cryptoids" which can scheme, game, apply various crypto protocols, etc. (I don't mean any high-falutin artificial intelligence, just a "testbed" for exploring agents that implement crypto methods as, well, as _methods_.) Toward this eventual end, if I can pull it off, I'm evaluating "SmalltalkAgents," a programming environment for the Mac (soon for Windows/Chicago, then Unix, etc.) which supports several interesting features, including run-time dynamic typing, multiple threads, agent-oriented methods (similar to Dylan, and maybe to the elusive Telescript), and a persistent object store (so that the evolved agents "remember" what they've learned and don't start from scratch each time). For you Perl and C fans, why Smalltalk? First, because I get to pick whatever environment I want. Second, because I enjoyed Lisp programming at Intel (and a bit since, in Scheme) more than C programming. Third, while I think the C++ class libraries are a powerful tool, I'm not interested in using them right now. Fourth, the advent of 50-100 MIPS processors for not much money places more premium on powerful prgramming environments and not on runtime efficiency. Fifth, SmalltalkAgents can do external calls of C, or whatever, code, so the the programming environment of Smalltalk can be coupled with specific C code fragments. Sixth, the focus on CORBA, OpenDoc, OLE, and other object protocols. (I wrote down some of my thoughts on tools for crypto, beyond subroutine libraries, a few months ago. "Crypto compilers," "intermediate design languages" (IDLs for crypto anyone?), provably correct synthesis, etc.) I think Hal is right that ecologies of interacting agents implementing various crypto protocols (spending digital money, trying to collude with others, etc.) is a ripe area for study. We learned a lot two years ago with the "Crypto Anarchy Game" we played with paper and pencil, but we quickly realized that humans are poor at remembering and enforcing complicated, multi-stage, multi-party protocols, and that someday these would have to be programmed into "crypto simulation" tools. When, if ever, will I have results on this? I don't know. Do I want to spend the next several years of my life on this? (As surely it's a thesis-complexity job, or a several man-year job for a small group of programmers...) I haven't decided. I haven't decided even if it's the most important--and interesting, since I'm working for myself, as most of us are--thing to work on. Enough writing for now. --Tim May .......................................................................... Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@netcom.com | anonymous networks, digital pseudonyms, zero 408-688-5409 | knowledge, reputations, information markets, W.A.S.T.E.: Aptos, CA | black markets, collapse of governments. Higher Power: 2^859433 | Public Key: PGP and MailSafe available. "National borders are just speed bumps on the information superhighway."