Title: Discovering Theorems in Game Theory: Two-Person Games with Unique Nash Equilibria
Abstract:In this paper we provide a logical framework for using com- puters to discover theorems in (two-person finite) games in strategic form, and apply it to discover classes of games that have unique (pure...In this paper we provide a logical framework for using com- puters to discover theorems in (two-person finite) games in strategic form, and apply it to discover classes of games that have unique (pure-strategy) Nash equilibria. We consider all possible classes of games that can be expressed by a conjunc- tion of two binary clauses, and our program re-discovered Kats and Thisse's class of weakly unilaterally two-person games, and came up with several other classes of games that have unique Nash equilibria. It also came up with new classes of strict games that have unique Nash equilibria, where a game is strict if for each player different profiles have different payoffs. Partly motivated by these findings, we also (manually) prove a result that says that a strict game has a unique Nash equilibrium iff it is best-response equivalent to a strictly game. class of games with unique Nash equilibria. We did not ex- pect much as these conditions are rather simple, but to our surprise, our program returned a condition that is more gen- eral than the strict competitiveness condition. As it turned out, it exactly corresponds to Kats and Thisse's (1992) class of weakly unilaterally competitivetwo-person games. Our program also returned some other conditions. Two of them capture a class of games where one player has ad- vantage over the other. The remaining ones capture games where everyone gets what he wants - each receives his max- imum payoff in every equilibrium state, thus there is no real competition among the players. Thus one conclusion that we can draw from this experiment is that among all classes of games that can be expressed by a conjunction of two binary clauses, the class of weakly unilaterally games is the most general class of competitive and fair games that have unique Nash equilibria. Of course, this does not mean that the other conditions are not worth investigating. For instance, sometimes one may be forced to play an unfair game. For the same set of conditions, we also consider strict two- person games where different profiles have different payoffs for each player. Among the results returned by our pro- gram, two of them are exactly the two conjuncts in Kats and Thisse's weakly unilaterally condition, but the others all turn out to be special cases of games with domi- nant strategies. Motivated by these results, we consider cer- tain equivalent classes of games, and show that a strict game has a unique Nash equilibrium iff it is best-response equiva- lent (Rosenthal, 1974) to a strictly game. The rest of the paper is organized as follows. We first review some basic concepts in two-person games in strate- gic form, and then reformulate them in first-order logic. We then show that for a class of conditions, whether any of them entails the uniqueness of Nash equilibria needs only to be checked on games up to certain size. We then describe a computer program based on this result, and report our ex- perimental results.Read More
Publication Year: 2007
Publication Date: 2007-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot