사용자:내용있음/작업장/팃포탯

In Western business cultures, a handshake when meeting someone is an example of initial cooperation

원문

Tit for tat is an English saying meaning "equivalent retaliation". It is also a highly effective strategy in game theory for the iterated prisoner's dilemma. It was first introduced by in Robert Axelrod's two tournaments, held around 1980. An agent using this strategy will initially cooperate, then respond in kind to an opponent's previous action. If the opponent previously was cooperative, the agent is cooperative. If not, the agent is not. This is similar to superrationality and reciprocal altruism in biology.

Tit for tat은 같은 수준의 보복을 의미하는 영어 속담이다. 이것은 또한 게임 이론 반복되는 죄수의 딜레마의 강력한 전략이기도 하다. 이 전략은 1980년대에 열린 Robert Axelrod의 두 토너먼트 경기에서 Anatol Rapoport에 의해 최초로 제안되었다. 이 전략을 사용하는 경기자는 처음에는 협력하고, 그 이후에는 상대의 바로 전 전략에 반응한다. 만약 상대가 이전에 협력을 했다면, 경기자는 협력하고, 만약 배반했다면, 경기자는 배반할 것이다. 이것은 생물학에서의 superrationality 이나 상호이타성하고도 비슷하다.

개요

이 전략은 반복되는 죄수의 딜레마:에서의 가장 성공적인 전략이라고 입증된 4개의 원칙에 의존한다.

1. 배반하기 전까지 경기자는 항상 협력한다.
2. 만약 배반했다면, 경기자는 복수할 것이다.
3. 경기자는 빠르개 관용을 배푼다.
4. 경기자는 반드시 상대와 한번 이상 경쟁할 "좋은 기회"를 가지고 있어야 한다.

마지막 조건에서, "좋은 기회"의 정의는 죄수의 딜래마의 payoff matrix에 의존한다. 중요한 점은 경쟁이 충분히 길어서 처벌과 관용의 반복이 지속되는 협력보다 장기적으로 더 적은 점수를 받아야 한다는 것이다.

게임을 의미있개 만드는 다섯번째 원칙: 만약 한 경기자가 다음 경기가 마지막이 될 것이라는 사실을 안다면, 자연히 더 높은 점수를 위해 배반할 것이다. 비슷하게 지금이 마지막에서 두 번째 남은 경기라는 사실을 알개 된다면 그는 두번 배신할 것이다. 이러한 이유로 경기자들은 경기가 지속되는 횟수를 모르고 있어야만 한다.

게임 이론에서 일반적으로 전략의 유효성은 각각의 경기자가 자기 자신에 대해서만 관심을 가진다는 전재 아래에서 측정된다.(그러함으로, 게임이론에서의 유효성은 각 경기자들이 다른 경기자에 대한 기득권이나 동정을 가지는 많은 실제 상황과는 관계가 없다.) 또한, 게임이론에서의 유효성이란 보통 경기자가 절대로 다른 경기자의 의도에 대해서 잘못 해석하지 않는 완전한 소통을 한다는 가정 하에서 측정되어진다.

이러한 게임 이론의 팃포탯의 유효성에 대한 정의 하에서는 팃포탯 전략은 몇번의 토너먼트에서 컴퓨터 과학자, 경재학자나 심리학자들의 팀이 만든 (보통 훨씬 더 복잡한)전략들보다 우수하였습니다. 어떤 게임 이론가들은 비공식적으로 비록 증거는 제시되지 않았지만 팃포탯 전략이 최선의 전략이라고 믿습니다.

어떤 대회에서는 팃포텟은 최선의 전략이 아니었으며, 심지어는 게임이론의 유효성에 대한 정의 보다도 낮았다. 그러나, 팃포탯은 각각의 전략들이 비교되왔던 경우에는 가장 효과적인 전략이었다. 최근에 나온 순수한 팃포탯 전략보다 더 나은 전략들은 주종관계를 가진 여러개의 전략들의 쌍(한 전략이 스스로 을 가정한 In some competitions tit for tat was not the most effective strategy, even under the game-theory definition of effectiveness. However, tit for tat would have been the most effective strategy if the average performance of each competing team were compared. The team which recently won over a pure tit for tat team outperformed it with some of their algorithms because they submitted multiple algorithms which would recognize each other and assume a master and slave relationship (one algorithm would "sacrifice" itself and obtain a very poor result for the other algorithm to be able to outperform tit for tat on an individual basis, but not as a pair or group). 같은 문단.. 이러한 혼합 전략의 승리는 죄수의 딜레마의 사회적 현실에서의 중요한 한계중에 하나입니다. This "group" victory illustrates one of the important limitations of the Prisoner's Dilemma in representing social reality, namely, that it does not include any natural equivalent for friendship or alliances. The advantage of tit for tat thus pertains only to a Hobbesian world of so-called rational solutions (with perfect communication), not to a world in which humans are inherently social. However, that this winning solution does not work effectively against groups of agents running tit for tat illustrates the strengths of tit for tat when employed in a team (that the team does better overall, and all the agents on the team do well individually, when every agent cooperates).

전략 사용의 예

죄수의 딜레마

	침묵	배신
침묵	3, 3	0, 5
배신	5, 0	1, 1

여기 4명의 경기자가 있다고 가정하자. 두 경기자는 팃포탯 전략을 사용하고, 다른 두명은 자신들의 이득을 최대화하기 위해 항상 비협조하는 배반자이다. 각각의 경기자가 다른 3명의 경기자들과 각각 6번의 경기를 한다고 해 보자. 만약 한 경기자가 만약 침묵한 상대를 배신한다면, 배신자는 5점을 얻고 침묵을 지킨 사람은 점수를 얻지 못한다. 만약 두명 모두 침묵을 지킨다면, 두명 모두 3점을 얻는다. 만약 두명 모두 서로를 배반한다면, 두명 모두 1점을 얻개 된다.

만약 한 팃포탯 전략을 사용하는 경기자 A가 배반자 B를 상대하게 되면, 첫 경기에서 배반자는 상대를 배신하고 팃포탯 경기자는 침묵을 지켜 배신자가 5점을 얻개 될 것이다. 나머지 5번의 경기에서는 두 경기자 모두 서로를 배반하게 됨으로, 각 경기마다 둘 모두 1점을 얻게 된다. 배신자는 총 합해서 10점을 얻게 되고, 팃포탯 전략을 사용하는 경기자는 다해서 5점을 얻게 될 것이다.

만약 팃포탯 경기자들이 서로 상대하게 된다면, 6경기 모두 둘 다 침묵을 지키개 될 것이다. 두 경기자들은 경기마다 3점씩을 얻게 되고, 다해서 18점을 얻게 된다.

만약 배반자들이 서로를 상대하게 된다면 6경기 모두 서로를 배반할 것이다. 두 배반자 모두 경기마다 1점씩을 얻어 다해서 6점을 얻게 될 것이다.

각각의 팃포탯 경기자들은 18경기동안 다해서 28점(서로를 상대할떄 18점과 두명의 배반자를 상대할떄 각각 얻은 5점)을 얻게 된다. 그리고 각각의 배반자들은 26점(배반자들끼리의 6점과 두명의 팃포탯 경기자를 상대할때 얻은 10점).

팃포탯 경기자들이 경기에서 이긴적이 없고 배반자들이 상대에게 진 적이 없지만, 최종 점수는 얼마나 많은 경기를 이겼는지가 아닌 얻은 총 점수에 관련되기 때문에 팃포탯 전략은 선두를 유지하고 있다. 간단히 말해서, 팃포탯 경기자들은 서로 경기를 할때 배반자들에게 잃은 것보다 더 많은 점수를 얻었다

The more tit-for-tat agents that there are in the described game, the more advantageous it is to use the tit-for-tat strategy. The fewer tit-for-tat agents that there are in the described game, the less advantageous it is to use the tit-for-tat strategy.

Implications

The success of the tit for tat strategy, which is largely cooperative despite that its name emphasizes an adversarial nature, took many by surprise. In successive competitions various teams produced complex strategies which attempted to "cheat" in a variety of cunning ways, but tit for tat eventually prevailed in every competition.

This result may give insight into how groups of animals (and particularly human societies) have come to live in largely (or entirely) cooperative societies, rather than the individualistic "red in tooth and claw" way that might be expected from individuals engaged in a Hobbesian state of nature. This, and particularly its application to human society and politics, is the subject of Robert Axelrod's book The Evolution of Cooperation.

Problems

While Axelrod 가 경험적으로 팃포탯 전략이 최선이라는 것을 보여주었지만, 팃포탯 전략를 사용하는 두명의 경기자는 아직 문재점을 가지고 있다. 한 경기자의 단 한번의 실수가 경기자를 "끝나지 않는 복수"로 이끌수 있다. A one-time, single-bit error in either player's interpretation of events can lead to an unending "death spiral". 이러한 상황에서, 각각의 경기자들은 상대가 협력한다면 협력할 준비를 하고 있다. 그러나 각각은 바로 상대에게 복수하는 전략을 사용해 매 경기마다 복수와 협력을 반복하게 된다. 두 경기자는 자기 자신들은 무고하고 자기방어를 하지만, 상대는 협력을 배우기에는 악하거나 너무 멍청하다고 생각한다. In this symmetric situation, each side perceives itself as preferring to cooperate, if only the other side would. But each is forced by the strategy into repeatedly punishing an opponent who continues to attack despite being punished in every game cycle. Both sides come to think of themselves as innocent and acting in self-defense, and their opponent as either evil or too stupid to learn to cooperate.

This situation frequently arises in real world conflicts, ranging from schoolyard fights to civil and regional wars. Tit for two tats could be used to avoid this problem

"Tit for tat with forgiveness" is sometimes superior. When the opponent defects, the player will occasionally cooperate on the next move anyway. This allows for recovery from getting trapped in a cycle of defections. The exact probability that a player will respond with cooperation depends on the line-up of opponents.

The reason for these issues is that tit for tat is not a subgame perfect equilibrium. If one agent defects and the opponent cooperates, then both agents will end up alternating cooperate and defect, yielding a lower payoff than if both agents were to continually cooperate. While this subgame is not directly reachable by two agents playing tit for tat strategies, a strategy must be a Nash equilibrium in all subgames to be subgame perfect. Further, this subgame may be reached if any noise is allowed in the agents' signaling. A subgame perfect variant of tit for tat known as "contrite tit for tat" may be created by employing a basic reputation mechanism.

Tit for two tats

Tit for two tats is similar to tit for tat in that it is nice, retaliating, forgiving and non-envious, the only difference between the two being how nice the strategy is.

In a tit for tat strategy, once an opponent defects, the tit for tat player immediately responds by defecting on the next move. This has the unfortunate consequence of causing two retaliatory strategies to continuously defect against one another resulting in a poor outcome for both players. A tit for two tats player will let the first defection go unchallenged as a means to avoid the "death spiral" of the previous example. If the opponent defects twice in a row, the tit for two tats player will respond by defecting.

This strategy was put forward by Robert Axelrod during his second round of computer simulations at RAND. After analyzing the results of the first experiment, he determined that had a participant entered the tit for two tats strategy it would have emerged with a higher cumulative score than any other program. As a result, he himself entered it with high expectations in the second tournament. Unfortunately, owing to the more aggressive nature of the programs entered in the second round, which were able to take advantage of its highly forgiving nature, tit for two tats did significantly worse (in the game-theory sense) than tit for tat.

Real world use

Peer-to-peer file sharing

 BitTorrent_(protocol) § Downloading torrents and sharing files 문서를 참고하십시오.

비트토렌트 의 사용자들은 그들의 다운로드 속도를 최대화하기 위해 팃포탯 전략을 사용하고 있다. 더 자세하게는, 대부분의 비트토렌드 사용자들은 비트토렌트 기술에서 regular unchoking이라고 불리는 Tit for two Tats 전략을 사용한다. 비트토랜트 peer들은 다른 peer들에게 제한된 게수의 조각들만을 전송할수 있다. 그래서, 한 peer의 업로드 대역폭이 포화되었을 때, 그 peer는 팃포탯 전략을 사용할 것이다. Cooperation is achieved when upload bandwidth is exchanged for download bandwidth. Therefore, when a peer is not uploading in return to our own peer uploading, the BitTorrent program will choke the connection with the uncooperative peer and allocate this upload slot to a hopefully more cooperating peer. regular unchoking corresponds very strongly to always cooperating on the first move in prisoner’s dilemma. Periodically, a peer will allocate an upload slot to a randomly chosen uncooperative peer (unchoke). This is called optimistic unchoking. 이러한 행위는 더 협력적인 peer들을 찾을수 있게 하면서 이전의 비협조적인 peer들에게 두번째 기회를 준다.optimal threshold values of this strategy are still the subject of research.

Explaining reciprocal altruism in animal communities

Studies in the prosocial behaviour of animals, have led many ethologists and evolutionary psychologists to apply tit-for-tat strategies to explain why altruism evolves in many animal communities. Evolutionary game theory, derived from the mathematical theories formalised by von Neumann and Morgenstern (1953), was first devised by Maynard Smith (1972) and explored further in bird behaviour by Robert Hinde. Their application of game theory to the evolution of animal strategies launched an entirely new way of analysing animal behaviour.

Reciprocal altruism works in animal communities where the cost to the benefactor in any transaction of food, mating rights, nesting or territory is less than the gains to the beneficiary. The theory also holds that the act of altruism should be reciprocated if the balance of needs reverse. Mechanisms to identify and punish "cheaters" who fail to reciprocate, in effect a form of tit for tat, is an important mechanism to regulate reciprocal altruism.

War

The tit for tat strategy has been detected by analysts in the spontaneous non-violent behaviour, called "live and let live" that arose during trench warfare in the First World War. Troops dug in only a few hundred feet from each other would evolve an unspoken understanding. If a sniper killed a soldier on one side, the other could expect an equal retaliation. Conversely, if no one was killed for a time, the other side would acknowledge this implied "truce" and act accordingly. This created a "separate peace" between the trenches.

Popular culture

This approach to interactions can be seen as a parallel to the eye for an eye approach from Judeo-Christian-Islamic tradition, where the penalty for taking someone's eye is to lose one's own.

See also

• An eye for an eye
• Attitude polarization
• Chicken (game)
• Christmas truce
• Deterrence theory
• Golden Rule
• Mutual assured destruction
• Nice Guys Finish First, a documentary by Richard Dawkins that discusses tit for tat
• Quid pro quo
• Trigger strategy (a set of strategies of which tit for tat is a member)
• Virtuous circle and vicious circle
• Zero-sum game

External links

• Wired magazine story about tit for tat being 'defeated' by a group of collaborating programs
• Explanation of Tit for tat on Australian Broadcasting Corporation
• Article on tit for tat and its success in evolutionary cooperation