SEMINAR REPORT On

Manipulation in Games

Submitted By:RAMEEZ MOHAMMED. A
Department of Computer Science
Cochin University of Science and Technology
Cochin-22, Kerala
ABSTRACT
Games are strategic situations which involves a number of participating players termed agents. Each agent makes decisions, called moves during the course of the game. Rational logic dictates that players make moves aimed at maximising their welfare, given the available information. The choices made by the individual agents depend on the choices of others agents as well. The branch of mathematics which studies such interactions among the agents in a game is termed Game Theory. Under normal conditions, the players in a game are expected to act as rational beings. The choices they make during the game are guided by a common interest to sway the outcome of the game in their favour. However, an external agent, interested in altering the outcome of a game, can influence the participating agents to give up rational play by offering additional benefits. This seminar attempts to demonstrate how the outcome of a game can be manipulated by a non-participating external entity. 5
1. Game Theory “ An Overview
Game Theory is a branch of applied mathematics which studies the rational interactions among the players of a game. Game theory attempts to mathematically capture behavior in strategic situations, in which an individual's success in making choices depends on the choices of others. While initially developed to analyze competitions in which one individual does better at another's expense (zero sum games), it has been expanded to treat a wide class of interactions, which are classified according to several criteria. Game Theory finds applications in fields as diverse as Biology, Social Sciences, Computer Science etc.
Although some developments occurred before it, the field of game theory came into being with the 1944 book Theory of Games and Economic Behaviour by John von Neumann and Oskar Morgenstern. This theory was developed extensively in the 1950s by many scholars. Game theory was later explicitly applied to biology in the 1970s, although similar developments go back at least as far as the 1930s. Game theory has been widely recognized as an important tool in many fields.
1.1. What is a Game?
A game consists of a set of players or agents, a set of moves (or strategies) available to those players, and a specification of payoffs for each combination of strategies.The participating agents are assumed to be rational. A rational player will choose the action which he or she expects to give the best consequences, where best is according to the agent™s personal set of preferences. For example, people typically prefer more money to less money, or pleasure to pain. A decision maker is assumed to have a fixed range of alternatives to choose from, and the choice adopted influences the outcome of the situation. Each possible outcome is associated with a real number“ its utility. A payoff function associates the combination of This can be subjective (how much the outcome is desired) or objective (how good the outcome actually is for the player).
2. Representation of Games
2.1 Normal Form or Strategic Form representation
A normal form representation of a game is a specification of players' strategy spaces and payoff functions. A strategy space for a player is the set of all strategies available to that player, where a strategy is a complete plan of action for every stage of the game, regardless of whether that stage actually arises in play. A payoff function for a player is a mapping from the cross-product of players' strategy spaces to that player's set of payoffs of a player, i.e. the payoff function of a player takes as its input a strategy profile and yields a representation of payoff as its output. The normal representation of a game G specifies:
- a finite set of players {1, 2, ..., n}, - players™ strategy spaces S 1 , S 2 ... S n and - their payoff functions u 1 , u 2 ... u n where u i : S 1 × S 2 × ...× S n ?R The set (s 1 , s 2 , ¦ , s n ) representing the strategies adopted by all the players is called a strategy profile.
The normal (or strategic form) game is usually represented by a matrix which shows the players, strategies, and payoffs (see the example to the right). More generally it can be represented by any function that associates a payoff for each player with every possible combination of actions. In the below figure, there are two players; one chooses the row and the other chooses the column. Each player has two strategies, which are specified by the number of rows and the number of columns. The payoffs are provided in the interior. The first number is the payoff received by the row player (Player 1 in our example); the second is the payoff for the column player (Player 2 in our example). Suppose that Player 1 plays Up and that Player 2 plays Left. Then Player 1 gets a payoff of 4, and Player 2 gets 3.
Player 2 chooses Player 2 chooses Left Right Player 1 chooses Up
Player 1 chooses Down
When a game is presented in normal form, it is presumed that each player acts simultaneously or, at least, without knowing the actions of the other. If players have some information about the choices of other players, the game is usually presented in extensive form.
2.2 Extensive form representation
The extensive form can be used to formalize games with some important order. Games here are often presented as trees. Here each vertex (or node) represents a point of choice for a player. The player is specified by a number listed by the vertex. The lines out of the vertex represent a possible action for that player. The payoffs are specified at the bottom of the tree.
1 F U 2 2 A R A R 5;5 0;0 8;2 0;0 Fig. Extensive form representation of a game
In the game pictured here, there are two players. Player 1 moves first and chooses either F or U. Player 2 sees Player 1's move and then chooses A or R. Suppose that
4, 3 -1, -1 0, 0 3, 4 9 9 Player 1 chooses U and then Player 2 chooses A, then Player 1 gets 8 and Player 2 gets 2. Unlike the normal form, the extensive form allows explicit modeling of interactions in which a player makes more than one move during the game, and moves contingent upon varying states.
3. Types of Games
3.1 Cooperative or noncooperative Games
A game is cooperative if the players are able to form binding commitments. For instance the legal system requires them to adhere to their promises. In noncooperative games this is not possible. Often it is assumed that communication among players is allowed in cooperative games, but not in noncooperative ones. This classification on two binary criteria has been rejected A non-cooperative game is a one in which players can cooperate, but any cooperation must be self-enforcing. Of the two types of games, noncooperative games are able to model situations to the finest details, producing accurate results. Cooperative games focus on the game at large. Considerable efforts have been made to page link the two approaches. The so-called Nash-programme has already established many of the cooperative solutions as noncooperative equilibria. Hybrid games contain cooperative and non-cooperative elements. For instance, coalitions of players are formed in a cooperative game, but these play in a non- cooperative fashion.
3.2 Symmetric and asymmetric Games
A symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If the identities of the players can be changed without changing the payoff to the strategies, then a game is symmetric. Many of the commonly studied 2×2 games are symmetric. The standard representations of chicken, the prisoner's dilemma, and the stag hunt are all symmetric games. Some scholars would consider certain asymmetric games as examples of these games as well. However, the most common payoffs for each of these games are symmetric. Most commonly studied asymmetric games are games where there are not identical strategy sets for both players. For instance, the ultimatum game and similarly the dictator game have different strategies for each player. It is possible, however, for a game to have identical strategies for both players, yet be asymmetric. For example, the game pictured below is asymmetric despite having identical strategy sets for both players.
3.3 Zero sum and non-zero sum
Zero sum games are a special case of constant sum games, in which choices by players can neither increase nor decrease the available resources. In zero-sum games the total benefit to all players in the game, for every combination of strategies, always adds to zero (more informally, a player benefits only at the equal expense of others). Poker exemplifies a zero-sum game (ignoring the possibility of the house's cut), because one wins exactly the amount one's opponents lose. Other zero sum games include matching pennies and most classical board games including Go and chess. Many games studied by game theorists (including the famous prisoner's dilemma) are non-zero-sum games, because some outcomes have net results greater or less than zero. Informally, in non-zero-sum games, a gain by one player does not necessarily correspond with a loss by another.
Constant sum games correspond to activities like theft and gambling, but not to the fundamental economic situation in which there are potential gains from trade. It is possible to transform any game into a (possibly asymmetric) zero-sum game by adding an additional dummy player (often called "the board"), whose losses compensate the players' net winnings.
3.4 Simultaneous and sequential
Simultaneous games are games where both players move simultaneously, or if they do not move simultaneously, the later players are unaware of the earlier players' actions (making them effectively simultaneous). Sequential games (or dynamic games) are games where later players have some knowledge about earlier actions. This need not be perfect information about every action of earlier players; it might be very little knowledge. For instance, a player may know that an earlier player did not perform one particular action, while he does not know which of the other available actions the first player actually performed.
The difference between simultaneous and sequential games is captured in the different representations discussed above. Often, normal form is used to represent simultaneous games, and extensive form is used to represent sequential ones; although this isn't a strict rule in a technical sense.
3.5 Perfect information and imperfect information
An important subset of sequential games consists of games of perfect information. A game is one of perfect information if all players know the moves previously made by all other players. Thus, only sequential games can be games of perfect information, since in simultaneous games not every player knows the actions of the others. Most games studied in game theory are imperfect information games, although there are some interesting examples of perfect information games, including the ultimatum game and centipede game. Perfect information games include also chess, go, mancala, and arimaa. Perfect information is often confused with complete information, which is a similar concept. Complete information requires that every player know the strategies and payoffs of the other players but not necessarily the actions.
3.6 Infinitely long games
Games, as studied by economists and real-world game players, are generally finished in a finite number of moves. Pure mathematicians are not so constrained, and set theorists in particular study games that last for an infinite number of moves, with the winner (or other payoff) not known until after all those moves are completed.
The focus of attention is usually not so much on what is the best way to play such a game, but simply on whether one or the other player has a winning strategy. (It can be proven, using the axiom of choice, that there are games”even with perfect information, and where the only outcomes are "win" or "lose"”for which neither player has a winning strategy.) The existence of such strategies, for cleverly designed games, has important consequences in descriptive set theory.
3.7 Discrete and continuous games
Much of game theory is concerned with finite, discrete games, that have a finite number of players, moves, events, outcomes, etc. Many concepts can be extended, however. Continuous games allow players to choose a strategy from a continuous strategy set. For instance, Cournot competition is typically modeled with players' strategies being any non-negative quantities, including fractional quantities. Differential games such as the continuous pursuit and evasion game are continuous games. 4. Dominance In game theory, dominance (also called strategic dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance. The opposite, intransitivity, occurs in games where one strategy may be better or worse than another strategy for one player, depending on how the player's opponents may play. In the normal-form game {S 1 , S 2 , ..., S n , u 1 , u 2 , ..., u n }, let s i , s iâ„¢ ? S i be feasible strategies for player i. Strategy s i is strictly dominated by strategy s
iâ„¢ if u i (s i , s -i ) < u i (s iâ„¢ , s -i ), where s -i
is the strategy profile of all players except i. s iâ„¢ is strictly better than s i regardless of other playersâ„¢ choices. In the normal-form game {S
1 , S 2 , ..., S n , u 1 , u 2 , ..., u n }, let s i , s iâ„¢ ? S i be feasible
strategies for player i. Strategy s i is weakly dominated by strategy s
iâ„¢ if u i (s i , s -i ) = u i (s iâ„¢ , s -i ), with at least one strict inequality s iâ„¢ is at least as good as s i .
A rational player will never choose a strictly dominated strategy during the course of a game. The player may, however, choose a weakly dominated strategy depending on circumstances.
5. Nash Equilibrium
In game theory, a solution concept is a formal rule for predicting how the game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players, therefore predicting the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.
The Nash equilibrium (named after John Forbes Nash, who proposed it) is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his or her own strategy (i.e., by changing unilaterally). If each player has chosen a strategy and no player can benefit by changing his or her strategy while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitute a Nash equilibrium. . As a heuristic, suppose that each player is told the strategies of the other players. If any player would want to do something different after being informed about the others' strategies, then that set of strategies is not a Nash equilibrium. If, however, the player does not want to switch (or is indifferent between switching and not) then the set of strategies is a Nash equilibrium.
A strategy profile s* = (s* 1 , ...., s* n ) constitutes a Nash Equilibrium if for every i,
ui(s* i, s* -i ) = u i (s i' , s* -i ) for all s i' ? S i The players in a game are in Nash equilibrium if each one is making the best decision that they can, taking into account the decisions of the others. However, Nash equilibrium does not necessarily mean the best cumulative payoff for all the players involved; in many cases all the players might improve their payoffs if they could somehow agree on strategies different from the Nash equilibrium.
5.1 Dominance and Nash Equilibria
If a strictly dominant strategy exists for one player in a game, that player will play that strategy in each of the game's Nash equilibria. If both players have a strictly dominant strategy, the game has only one unique Nash equilibrium. However, that Nash equilibrium is not necessarily Pareto optimal, meaning that there may be non-equilibrium outcomes of the game that would be better for both players. The classic game used to illustrate this is the Prisoner's Dilemma. Strictly dominated strategies cannot be a part of a Nash equilibrium, and as such, it is irrational for any player to play them. On the other hand, weakly dominated strategies may be part of Nash equilibria.
5.2 Iterated Elimination of Dominated Strategies (IED)
The iterated elimination (or deletion) of dominated strategies is one common technique for solving games that involves iteratively removing dominated strategies. In the first step, all dominated strategies of the game are removed, since rational players will not play them. This results in a new, smaller game. Some strategies”that were not dominated before”may be dominated in the smaller game. These are removed, creating a new even smaller game, and so on. This process is valid since it is assumed that rationality among players is common knowledge, that is, each player know that the rest of the players are rational, and each player know that the rest of the players know that he knows that the rest of the players are rational, and so on ad infinitum. There are two versions of this process. One version involves only eliminating strictly dominated strategies. If, after completing this process, there is only one strategy for each player remaining, that strategy set is the unique Nash equilibrium. Another version involves eliminating both strictly and weakly dominated strategies. If, at the end of the process, there is a single strategy for each player, this strategy set is also a Nash equilibrium. However, unlike the first process, elimination of weakly dominated strategies may eliminate some Nash equilibria. As a result, the Nash equilibrium found by eliminating weakly dominated strategies may not be the only Nash equilibrium. For example, consider the normal form game as given by the payoff matrix 1 shown below. Initially, the strategy Right strictly dominates the strategy Middle for player 2. Hence, it can be eliminated giving the modified payoff matrix 2. In this case, the strategy Left is strictly dominated by strategy Middle for player 2. Also, the strategy Up strictly dominates strategy Down for player 1. Hence, both these rows can be eliminated, giving the Nash Equilibrium for the game which is namely the strategy (Up, Middle).
Player 2
Left Middle Right Up Player 1 Down Fig. Payoff Matrix 1 Player 2 Left Middle Up Player 1 Down Fig. Payoff Matrix 2 1, 0 1, 2 0, 1 0, 0 0, 1 2, 0 1, 0 1, 2 Nash Equilibrium 0, 0 0, 1
5.3 Prisonerâ„¢s Dilemma
The Prisoner's Dilemma constitutes a problem in game theory. It was originally framed by Merrill Flood and Melvin Dresher working at RAND in 1950. In its "classical" form, the prisoner's dilemma (PD) is presented as follows: Two suspects are arrested by the police. The police have insufficient evidence for a conviction, and, having separated both prisoners, visit each of them to offer the same deal. If one testifies ("defects") for the prosecution against the other and the other remains silent, the betrayer goes free and the silent accomplice receives the full 10-year sentence. If both remain silent, both prisoners are sentenced to only six months in jail for a minor charge. If each betrays the other, each receives a five-year sentence. Each prisoner must choose to betray the other or to remain silent. Each one is assured that the other would not know about the betrayal before the end of the investigation. How should the prisoners act?
If it is assumed that each player prefers shorter sentences to longer ones, and that each gets no utility out of lowering the other player's sentence, and that there are no reputation effects from a player's decision, then the prisoner's dilemma forms a non-zero- sum game in which two players may each "cooperate" with or "defect" from (i.e., betray) the other player. In this game, as in all game theory, the only concern of each individual player ("prisoner") is maximizing his/her own payoff, without any concern for the other player's payoff. The unique equilibrium for this game is a Pareto-suboptimal solution” that is, rational choice leads the two players to both play defectly even though each player's individual reward would be greater if they both played cooperately. In the classic form of this game, cooperating is strictly dominated by defecting, so that the only possible equilibrium for the game is for all players to defect. In simpler terms, no matter what the other player does, one player will always gain a greater payoff by playing defect. Since in any situation playing defect is more beneficial than cooperating, all rational players will play defect, all things being equal.
The payoff matrix for Prisonerâ„¢s Dilemma is as shown below:
In this game, regardless of what the opponent chooses, each player always
receives a higher payoff (lesser sentence) by betraying; that is to say that betraying is the
strictly dominant strategy. For instance, Prisoner A can accurately say, "No matter what
Prisoner B does, I personally am better off betraying than staying silent. Therefore, for
my own sake, I should betray." However, if the other player acts similarly, then they both betray and both get a lower payoff than they would get by staying silent. Rational self- interested decisions result in each prisoner's being worse off than if each chose to lessen the sentence of the accomplice at the cost of staying a little longer in jail himself. Hence a seeming dilemma. In game theory, this demonstrates very elegantly that in a non-zero sum game a Nash Equilibrium need not be a Pareto optimum.
6. Manipulating Games - Mechanism Design
In economics and game theory, mechanism design is the study of designing rules of a game or system to achieve a specific outcome, even though each agent may be self- interested. This is done by setting up a structure in which agents have an incentive to behave according to the rules. The resulting mechanism is then said to implement the desired outcome. The strength of such a result depends on the solution concept used in
-0.5, -0.5
-10, 0
0, 10
-5, -5
Nash Equilibrium
the rules. It is related to metagame analysis, which uses the techniques of game theory to develop rules for a game. The rules implemented by the mechanism designers may often contradict with the rational intents of the participating players in the game. However, the incentives promised can influence the players to deter from rational play, leading to the outcome desired by the mechanism designers. Mechanism designers belong to two classes: benevolent and malicious. Benevolent mechanism designers are interested in increasing the welfare of the players in the game. On the other hand, malicious mechanism designers aim to worsen the welfare of the players in the game. Mechanism designers commonly try to achieve the following basic outcomes: truthfulness, individual rationality, budget balance, and social welfare. However, it is impossible to guarantee optimal results for all four outcomes simultaneously in many situations, particularly in markets where buyers can also be sellers, thus significant research in mechanism design involves making trade-offs between these qualities. Other desirable criteria that may be achieved include fairness (minimizing variance between participants' utilities), maximizing the auction holder's revenue, and Pareto efficiency. More advanced mechanisms sometimes attempt to resist harmful coalitions of players. A common exercise in mechanism design is to achieve the desired outcome according to a specific solution concept. One branch of mechanism design is the creation of markets, auctions, and combinatorial auctions. Another is the design of matching algorithms, such as the one used to pair medical school graduates with internships. A third application is to the provision of public goods and to the optimal design of taxation schemes by governments.
6.1 Influencing rational play
As described earlier, incentives are to be provided to the players in a game by the mechanism designers if they intend to manipulate the outcome of the game. These incentives are often referred to as payments. These payments are described by a tuple of non-negative payoff functions
V = (V 1 , V 2 ,¦ , V n ) where V i : S->R + Payments depend on the strategy that player i selects as well as the choices of others. As a result of the payments, the original game
G = (N, S, U) is modified to G(V) = (N, S, [U + V]), where [U + V] i (s) = U i (s) + V i (s) Each player i obtains a payoff of V i in addition to U i . The mechanism designer's main objective is to force the players to choose a certain strategy profile or a set of strategy profiles, without spending too much.
6.2 Leverage
Mechanism designers can implement desired outcomes in games at certain costs. This raises the question for which games it makes sense to take influence at all. There exists two diametrically opposed kinds of interested parties, the first one being benevolent towards the participants of the game, and the other being malicious. While the former is interested in increasing a game's social gain, the latter seeks to minimize the players' welfare. It is required to define a measure indicating whether the mechanism of implementation enables them to modify a game in a favorable way such that their gain exceeds the manipulation's cost. These measures are called leverage and malicious leverage, respectively. The concept of leverage is used to measure the change of playersâ„¢ behaviour a mechanism design can inflict, taking into account the social gain and the implementation cost. Regarding the payments offered by the mechanism designer as some form of insurance, it seems natural that outcomes of a game can be improved at no costs. A malicious mechanism designer can in some cases even reduce the social welfare at no costs. Several optimization problems related to the leverage are NP-hard. As the concept of leverage depends on the implementation costs, there exists worst-case and uniform leverage. The worst-case leverage is a lower bound on the mechanism designer's influence: it is assumed that without the additional payments, the players choose a strategy profile in the original game where the social gain is maximal, while in the modified game, they select a strategy profile among the newly non- dominated profiles where the difference between the social gain and the mechanism designer's cost is minimized. The value of the leverage is given by the net social gain achieved by this implementation minus the amount of money the mechanism designer had to spend. For malicious mechanism designers it is needed to invert signs and swap max and min. Moreover, the payments made by the mechanism designer have to be subtracted twice, because for a malicious mechanism designer, the money received by the players are considered a loss. The concept of leverage is illustrated by the Extended Prisonerâ„¢s Dilemma as follows.
6.3 Extended Prisonerâ„¢s Dilemma
In the context of manipulating games by providing incentives, the classic example of Prisonerâ„¢s Dilemma is analyzed as follows. The rules of the game remain the same as earlier with slight modifications. The Extended Prisonerâ„¢s Dilemma is as follows: Two suspects are arrested by the police. The police have insufficient evidence for a conviction, but they have sufficient evidence to convict them for a minor crime. Having separated both prisoners, the police visit each of them to offer the same deal. If one testifies for the prosecution against the other and the other remains silent, the betrayer goes free and the silent accomplice receives 3 years in prison and an additonal year for the minor crime. If both remain silent, both prisoners are sentenced to only one year for the minor crime. If each betrays the other, each receives a three year sentence. However, if either one of the prisoners confess their crime, both get four years in prison. How should the prisoners act? The payoff matrix for the above game in its unmodified form is as shown in the figure below. The entries in each cell indicates the number of years saved by the individual prisoners for that particular combination of strategies.
In the above payoff matrix, it can be observed that the strategy silent is dominated by testify for both prisoners. Also the strategy confess is dominated by both silent and testify for either of the prisoners. As such, they can be eliminated, leaving behind the strategies (testify, testify) which is the Nash Equilibrium for the game. Hence, both prisoners choose to betray each other. However, this combination of strategies is not the most optimum solution for the game, as the prisoners would be much better off if both remain silent. Now let us consider two third parties who are interested in the choices made by the prisoners and eventually, the outcome of the game. The first is the Crime Boss, who wants his gang members to spend as little time as possible in prison. The second is the Police Chief, who wants the convicts to spend maximum time in prison. To realize their personal objectives, both the individuals attempt to alter the mechanism of the game by
3, 3 0, 4 0, 0 4, 0 1, 1 Nash Equilibrium 0, 0 0, 0 0, 0 0, 0
offering rewards to the prisoners to overlook rational play. The incentives prompt the prisoners to make choices that cause the outcome of the game to sway in favor of the interested party. The manipulation implemented by each of the interested outsiders is as follows:
i. Mechanism Design by the Crime Boss: The crime boss wants the prisoners to spend minimum time in prison. As seen earlier, the choice made by the prisoners namely, to betray each other, is not the best solution in terms of years spent in prison. The best strategy for the prisoners is to cooperate and remain silent which buys them minimum time in prison. The crime boss, therefore wants to shift the equilibrium of the game to this combination of choices. To this end, he offers the prisoners monetary rewards which are as below:
1. If both prisoners remain silent, they will each be rewarded with monetary benefits amounting to one year in prison.
2. If one prisoner remains silent, and the other betrays him, the former will be paid benefits worth two years in prison
The above incentives cause the mechanism of the game to be modified as below silent testify confess silent
As depicted above, the incentives promised by the crime boss prompt the prisoners to remain silent and thus cooperate with each other. The equilibrium of the game shifts to (silent, silent) which ensures that both the prisoners spend minimum time
1, 1 2, 0 0, 2 4, 4 Nash Equilibrium 2, 4 0, 0 4, 2 1, 1 0, 0 0, 0 0, 0 0, 0
in prison. The crime boss needs to pay money worth two years in prison to the convicts. Each prisoner saves two years in prison by adopting the new strategy. The net gain for the crime boss is thus, 2 years. The crime boss is a benevolent mechanism designer, who is interested in improving the welfare of the prisoners. ii. Mechanism Design by the Police: The police want the prisoners to spend the maximum time in prison. Under the original rules, each prisoner spends three years in prison, which is one year less than the maximum possible sentence of four years. This is realized if either of the prisoners confesses the crime. Therefore, the police chief changes the mechanism design of the game by offering the prisoners incentives as follows:
1. If one prisoner remains silent, and the other betrays him, the formerâ„¢s sentence will be reduced by two years.
2. If one prisoner confesses and the other remains silent, the former will be allowed to go free and rewarded with money worth one year in prison the modification in the game brought about by the above incentives is illustrated below. Silent testify confess
As depicted above the promises made by the police chief prompt the prisoners to confess to the crime. The equilibrium of the game shifts to the strategy combination (confess, confess) thereby ensuring that the prisoners spend maximum time in prison. The modified design is implemented at no cost to the police. The prisoners, on the other hand, has to spend one year in prison in addition to the maximum sentence of four years. The net gain for the police, is therefore 2 years. The police chief is a malicious mechanism designer, who is interested in worsening the welfare of the prisoners. The above example shows that a game can be influenced by the mechanism designer to yield a particular outcome. The designer incurs some cost in bringing about the desired outcome. In certain conditions, a particular result can be realized at no cost at all to the designer. The problem of finding a strategy profileâ„¢s exact uniform implementation cost is NP-Hard.
CONCLUSION
Games are common occurrence in every day world. Games involve a set of agents with a common interest to maximize their benefits. Game theory studies the patterns that arise when multiple agents compete with each other. It attempts to predict the behavior of participating agents in conflict scenarios. Games being omnipresent in almost every conceivable aspect of this world, Game theory are a comprehensive field transcending a number of diverse disciplines. Games assume the participation of rational players. It is possible for to influence the players of the game to give up rational play, by altering the mechanism design. In my paper, I have sought to demonstrate how games can be manipulated by interested non-participating outsiders.



REFERENCES
1. Manipulation in Games - Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid,
and Roger Wattenhofer, Computer Engineering and Networks Laboratory, ETH Zurich,
Switzerland
2. http://en.wikipediawiki/Game_theory
3. http://cse.iitd.ernetrahul/cs905/
4. http://gametheory.net