Limited Randomness in Games, and Computational Perspectives in Revealed Preference

Citation

Kalyanaraman, Shankar (2009) Limited Randomness in Games, and Computational Perspectives in Revealed Preference. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/KH85-HJ73. https://resolver.caltech.edu/CaltechETD:etd-06042009-233839

Abstract

In this dissertation, we explore two particular themes in connection with the study of games and general economic interactions: bounded resources and rationality. The rapidly maturing field of algorithmic game theory concerns itself with looking at the computational limits and effects when agents in such an interaction make choices in their "self-interest." The solution concepts that have been studied in this regard, and which we shall focus on in this dissertation, assume that agents are capable of randomizing over their set of choices. We posit that agents are randomness-limited in addition to being computationally bounded, and determine how this affects their equilibrium strategies in different scenarios.

In particular, we study three interpretations of what it means for agents to be randomness-limited, and offer results on finding (approximately) optimal strategies that are randomness-efficient:
1. One-shot games with access to the support of the optimal strategies: for this case, our results are obtained by sampling strategies from the optimal support by performing a random walk on an expander graph.
2. Multiple-round games where agents have no a priori knowledge of their payoffs: we significantly improve the randomness-efficiency of known online algorithms for such games by utilizing distributions based on almost pairwise independent random variables.
3. Low-rank games: for games in which agents' payoff matrices have low rank, we devise "fixed-parameter" algorithms that compute strategies yielding approximately optimal payoffs for agents, and are polynomial-time in the size of the input and the rank of the payoff tensors.

In regard to rationality, we look at some computational questions in a related line of work known as revealed preference theory, with the purpose of understanding the computational limits of inferring agents' payoffs and motives when they reveal their preferences by way of how they act. We investigate two problem settings as applications of this theory and obtain results about their intractability:
1. Rationalizability of matchings: we consider the problem of rationalizing a given collection of bipartite matchings and show that it is NP-hard to determine agent preferences for which matchings would be stable. Further, we show, assuming P ≠ NP, that this problem does not admit polynomial-time approximation schemes under two suitably defined notions of optimization.
2. Rationalizability of network formation games: in the case of network formation games, we take up a particular model of connections known as the Jackson-Wolinsky model in which nodes in a graph have valuations for each other and take their valuations into consideration when they choose to build edges. We show that under a notion of stability, known as pairwise stability, the problem of finding valuations that rationalize a collection of networks as pairwise stable is NP-hard. More significantly, we show that this problem is hard even to approximate to within a factor 1/2 and that this is tight.

Our results on hardness and inapproximability of these problems use well-known techniques from complexity theory, and particularly in the case of the inapproximability of rationalizing network formation games, PCPs for the problem of satisfying the optimal number of linear equations in positive integers, building on recent results of Guruswami and Raghavendra.

Thesis Files