Andy McLennan's Recent Unpublished Papers


[A.] "Imitation Games and Computation"


(Joint with Rabee Tourky)
Abstract: An imitation game is a finite two person normal form game in which the two players have the same set of pure strategies and the goal of the second player is to choose the same pure strategy as the first player. Gale et. al. (1950) gave a way of passing from a given two person game to a symmetric game whose symmetric Nash equilibria are in one-to-one correspondence with the Nash equilibria of the given game. We give a way of passing from a given symmetric two person game to an imitation game whose Nash equilibria are in one-to-one correspondence with the symmetric Nash equilibria of the given symmetric game. Lemke (1965) portrayed the Lemke-Howson algorithm as a special case of the Lemke paths algorithm. Using imitation games, we show how Lemke paths may be obtained by projecting Lemke-Howson paths.

[B.] "Manipulation in Elections with Uncertain Preferences"

Abstract: A decision scheme (Gibbard (1977)) is a function mapping profiles of strict preferences over a set of social alternatives to lotteries over the social alternatives. Motivated by conditions typically prevailing in elections with many voters, we say that a decision scheme is weakly strategy-proof if it is never possible for a voter to increase expected utility (for some vNM utility function consistent with her true preferences) by misrepresenting her preferences when her belief about the preferences of other voters is generated by a model in which the other voters are i.i.d. draws from a distribution over possible preferences. We show that if there are at least three alternatives, a decision scheme is necessarily a random dictatorship if it is weakly strategy-proof, never assigns positive probability to Pareto dominated alternatives, and is anonymous in the sense of being unaffected by permutations of the components of the profile. This result is established in two settings: a) a model with a fixed set of voters; b) the Poisson voting model of Meyerson (1998a, 1998b, 2000, 2002).

[C.] "Games in Oriented Matroids"


(Joint with Rabee Tourky)
Abstract: We introduce a combinatorial abstraction of two person finite games in an oriented matroid. We also define a combinatorial version of Nash equilibrium and prove that an odd number of equilibria exists. The proof is a purely combinatorial rendition of the Lemke-Howson algorithm.

[D.] "Uniqueness of Stationary Equilibrium Payoffs in Coalitional Bargaining"


(Joint with Hulya Eraslan)
Abstract: We study a model of sequential bargaining in which, in each period before an agreement is reached, a proposer is randomly selected, the proposer suggests a division of a pie of size one, each other agent either approves or rejects the proposal, and the proposal is implemented if the set of approving agents is a winning coalition for the proposer. The theory of the fixed point index is used to show that stationary equilibrium outcomes of a coalitional bargaining game are unique. This generalizes Eraslan (2002) insofar as: (a) there are no restrictions on the structure of sets of winning coalitions; (b) different proposers may have different sets of winning coalitions; (c) there may be a positive probability that no proposer is selected.

[E.] "Fixed Point Theorems"

Abstract: This draft of an entry in The New Palgrave Dictionary of Economics (Second Edition) gives statements of the Tarski fixed point theorem and the main versions of the topological fixed point principle that have been applied in economic theory. Pointers are given to literature concerned with proofs of Brouwer's theorem, and with algorithms for computing approximate fixed points. The topological results are all consequences of a slightly weakened version of the Eilenberg-Montgomery (1946) fixed point theorem. The axiomatic characterization of the Leray-Schauder fixed point index (which is even more powerful) is also stated, and its application to issues concerning robustness of sets of equilibria is explained.

This brief piece should be accessible (and, I hope, enjoyable) if you've taken an undergraduate course in real analysis, but it gives a much more complete view of the subject than you'll find in any economics text, at essentially maximal generality.

[F.] "Simple Complexity from Imitation Games"


(Joint with Rabee Tourky)
Abstract: We give simple proofs of refinements of the complexity results of Gilboa and Zemel (1989), and we derive additional results of this sort. Our constructions employ imitation games, which are two person games in which both players have the same sets of pure strategies and the second player wishes to play the same pure strategy as the first player.

[G.] "From Imitation Games to Kakutani"


(Joint with Rabee Tourky)
Abstract: We give a full proof of the Kakutani fixed point theorem that is brief, elementary, and based on game theoretic concepts. This proof points to a new family of algorithms for computing approximate fixed points. An imitation game is a finite two person normal form game in which the strategy spaces for the two agents are the same and the goal of the second player is to choose the same strategy as the first player. These appear in our proof, but are also interesting from other points of view.

[H.] "The Market for Liars: Reputation and Auditor Honesty"


(Joint with In-Uck Park)
Abstract: In the model there are two types of financial auditors with identical technology, one of which is endowed with a prior reputation for honesty. We characterize conditions under which there exists a ``two-tier equilibrium'' in which ``reputable'' auditors refuse bribes offered by clients for fear of losing reputation, while ``disreputable'' auditors accept bribes because even persistent refusal does not create a good reputation. The main findings are: (a) honest auditors charge higher fees, and have economic profits accruing to reputation; (b) as the fraction of auditors who are honest increases, the premium charged by reputable auditors eventually decreases, which diminishes the incentive to refuse bribes; (c) if the fraction of honest auditors exceeds an upper bound, there does not exist a two-tier equilibrium; (d) thus the reputation mechanism may be undermined by entry into the honest segment of the industry, if it is possible; (e) increasing auditor independence increases the upper bound.

In March 2005 "Liars" got a brief writeup in the Times of London!

[I.] "The Erdos-Sos Conjecture for Trees of Diameter Four"

Abstract: The Erdos-Sos conjecture is that a finite graph G with average degree greater than k - 2 contains every tree with k vertices. Theorem 1 is a special case: every k-vertex tree of diameter 4 can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. (Forthcoming in the Journal of Graph Theory.)

[J.] "The Asymptotic Expected Number of Nash Equilibria of Two Player Normal Form Games"


(Joint with Johannes Berg)
Abstract: The formula given by McLennan (2002) for the mean number of Nash equilibria of a normal form game, for a particular support, is applied to investigate the expected number of Nash equilibria of two player normal form games. Holding $M$ fixed while $N \to \infty$, the expected number of Nash equilibria is approximately $\left(\sqrt{\pi \log N}/2 \right)^{M-1}/\sqrt{M}$. The expected number of Nash equilibria when both players have $N$ pure strategies is $\exp(N[B + O(\log N/N)])$, where $B \approx 0.281644$ is a constant. When both players have $N$ pure strategies, as $N$ becomes large almost all equilibria have each player assigning positive probability to approximately $31.5915$ percent of her pure strategies. (Forthcoming in Games and Economic Behavior.)

[K.] "The Expected Number of Nash Equilibria of a Normal Form Game"

Abstract: Fix finite pure strategy sets S_1,.., S_n, and let S = S_1 x..x S_n. We consider the model of a random game given by assuming that the agents' payoffs are statistically independent, with each agent's payoff uniformly distributed on the unit sphere of the dual of |S|-dimensional Euclidean space. For i = 1,..,n fix T_i, a nonempty subset of S_i. Our main result is a computationally implementable formula for the mean number of Nash equilibria in which each agent i's mixed strategy has support T_i. This formula is the product of expressions representing the expected number of totally mixed equilibria for the truncated game obtained by eliminating pure strategies outside the sets T_i, and the ``probability'' that such an equilibrium remains an equilibrium when the strategies in the sets S_i \ T_i are available. Numerical results suggest that the expected number of equilibria is increasing in the number of strategies of each agent, and that the rate of increase is exponential when there are sufficiently many players. (January 2005 Econometrica.)

[L.] "Selected Topics in the Theory of Fixed Points"

Abstract: We present a treatment for mathematical economists of three topics in the theory of fixed points: (a) the Lefschetz fixed point index; (b) the Lefschetz fixed point theorem; (c) the theory of essential sets of fixed points. Our treatment is geometric, based on elementary techniques, and largely self-contained. In particular there is no essential reference to algebraic topology. Within the chosen scope of the paper the results are at the level of generality of the mathematical literature. The development of these theories for correspondences is emphasized. It emerges that the solution concepts of Kohlberg and Mertens (1986) have a definite, though somewhat obscure, place in this theory.

Last updated on March 12, 2008.