Andy McLennan's Recent Unpublished Papers


[A.] "Samuelson's Correspondence Principle Clarified"

Abstract: A theorem of Krasnosel'ski and Zabreiko (1984) implies that an equilibrium of an abstract economic model cannot be asymptotically stable, for natural adjustment dynamics, unless its fixed point index is +1. This result provides a precise and general formulation, and proof, of Samuelson's correspondence principle, which is commonly understood as a consequence of the 1-dimensional case.

[B.] "Some People Never Learn, Rationally" (Joint with Simon Loertscher)

Abstract: A Bayesian decision maker does not know which of several parameters is true. In each period she chooses an action from an open subset of $\Re^n$, observes an outcome, and updates her beliefs. There is an action $a^*$ that is uninformative in the sense that when it is chosen all parameters give the same distribution over outcomes, and consequently beliefs do not change. We give conditions under which a policy specifying an action as a function of the current belief can result in a positive probability that the sequence of beliefs converge to a belief at which $a^*$ is chosen, so that learning is asymptotically incomplete. Such a policy can be optimal even when the decision maker is not myopic and values experimentation.

[C.] "The Computational Complexity of Games and Markets: An Introduction for Economists"

Abstract: This is an expository survey of recent results in computer science related to the computation of fixed points, with the central one being that the problem of finding an approximate Nash equilibrium of a bimatrix game is PPAD-complete. This means that this problem is, in a certain sense, as hard as any fixed point problem. Subsequently many other problems have been shown to be PPAD-complete, including finding Walrasian equilibria in certain simple exchange economies. We also comment on the scientific consequences of complexity as a barrier to equilibration, and other sorts of complexity, for our understanding of how markets operate. It is argued that trading in complex systems of markets should be analogized to games such as chess, go, bridge, and poker, in which the very best players are much better than all but a small number of competitors. These traders make positive rents, and their presence is a marker of complexity. Consequences for the efficient markets hypothesis are sketched.

[D.] "On the Mean Number of Facets of a Gaussian Polytope"

Abstract: A Gaussian polytope is the convex hull of normally distributed random points in a Euclidean space. We give an improved error bound for the expected number of facets of a Gaussian polytope when the dimension of the space is fixed and the number of points tends to infinity. The proof applies the theory of the asymptotic distribution of the top order statistic of a collection of independently distributed $N(0,1)$ random variables.

[E.] "Truthful Implementation and Aggregation in Restricted Domains" (Joint with JC Carbajal and Rabee Tourky)

Abstract: We consider a social choice setting where agents have quasi-linear utilities over social alternatives and a transferable commodity, and study three properties that a social choice function may possess: truthful implementation (in dominant strategies); monotonicity in differences; and affine maximization, which has weak and strong forms. We introduce the notion of a flexible domain of preferences and study which of these conditions implies which others when the domain is flexible. We give examples showing that the result stated by Roberts (1979) is flawed; our main result is a strict generalization of the corrected version of that result. Flexibility holds, and the theorem is not vacuous, if the domain of valuation profiles is restricted to the space of continuous functions defined on a topological space, or the space of piecewise linear functions defined on an affine space, or the space of smooth functions defined on a compact differentiable manifold. Some illustrative economic applications are provided.

[F.] "Games with Discontinuous Payoffs: a Strengthening of Reny's Existence Theorem" (Joint with Rabee Tourky and Paulo Klinger Monteiro)

Abstract: We provide a pure Nash equilibrium existence theorem for games with discontinuous payoffs whose hypotheses are in a number of ways weaker than those of the theorem of Reny (1999). In comparison with Reny's argument, our proof is brief. Our result subsumes a prior existence result of Nichimura and Friedman (1981) that is not covered by his theorem. We use the main result to prove existence of pure Nash equilibrium in a class of finite games in which agents' pure strategies are subsets of a given set, and in turn use this to prove the existence of stable configurations for games, similar to those used by Schelling (1971, 1972) to study residential segregation, in which agents choose locations.

[G.] "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.

[H.] "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).

[I.] "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.

[J.] "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.

[K.] "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.

[L.] "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.

[M.] "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.

[N.] "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!

[O.] "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 November 15, 2012.