The purpose of this thesis is to study algorithmic questions that arise in the context of game theory and microeconomics. In particular, we investigate the computational complexity of various economic solution concepts by using and advancing methodologies from the fields of combinatorial optimization and approximation algorithms. We first study the problem of allocating a set of indivisible goods to a set of agents, who express preferences over combinations of items through their utility functions. Several objectives have been considered in the economic literature in different contexts. In fair division theory, a desirable outcome is to minimize the envy or the envy-ratio between any pair of players. We use tools from the theory of linear and integer programming as well as combinatorics to derive new approximation algorithms and hardness results for various types of utility functions. A different objective that has been considered in the context of auctions, is to find an allocation that maximizes the social welfare, i.e., the total utility derived by the agents. We construct reductions from multi-prover proof systems to obtain inapproximability results, given standard assumptions for the utility functions of the agents. We then consider equilibrium concepts in games. We derive the first subexponential algorithm for computing approximate Nash equilibria in $2$-player noncooperative games and extend our result to multi-player games. We further propose a second algorithm based on solving polynomial equations over the reals. Both algorithms improve the previously known upper bounds on the complexity of the problem. Finally, we study game theoretic models that have been introduced recently to address incentive issues in Internet routing. A polynomial time algorithm is obtained for computing equilibria in such games, i.e., routing schemes and payoff allocations from which no subset of agents has an incentive to deviate. Our algorithm is based on linear programming duality theory. We also obtain generalizations when the agents have nonlinear utility functions.

My dissertation uses game theoretic techniques to explain the existence of two economic institutions which are ignored by the Arrow-Debreu-McKenzie general equilibrium model of an economy. The first institution that I consider is the gated structure of some professional service industries. Two very similar explanations for the existence of such a structure are provided in Chapter 2 and Chapter 3 of this dissertation. The second institution that I consider is the presence of self-enforcing social conventions that can allow a small, isolated village to successfully manage common property resources in the absence of private property rights or some other form of explicit regulation. An explanation for the existence of this institution is provided in Chapter 4 of this dissertation. Many service industries, including the medical and legal professions in some countries, display a gated structure. Rather than approaching a final producer directly, a consumer will first seek a referral from an intermediary. Chapter 2 provides one possible explanation for such an industry structure. If the outcome of a transaction depends on producer effort, which is unobservable and unverifiable, then the market may fail to generate a Pareto optimal outcome. This is the standard moral hazard problem. If consumers had a long-run relationship with producers, this type of market failure might be avoided. However, in some industries, consumers will only have a short-run relationship with producers. A gatekeeping intermediary may provide an opportunity for reputation effects to apply in such a setting. By aggregating many potential consumers, gatekeeping intermediaries can create an artificial long-run relationship between a consumer and a producer. This long-run relationship reduces the incidence of shirking on the part of the producer. Chapter 3 provides another possible explanation for the gated structure of some professional service industries. Such an industry structure might help to alleviate adverse selection problems between parties that interact infrequently. Intermediaries aggregate many short-run transactions between various consumers and a particular producer. As such, they might be able to learn a producer's level of proficiency more rapidly than an individual consumer. However, the presence of a positive information externality means that too few consumers will seek a referral. As such, some form of regulation to encourage consumers to seek a referral might be warranted. Chapter 4 provides a model in which small and relatively isolated communities can successfully manage local commons informally in circumstances where larger or less isolated communities could not do so. The reason for this is the non-anonymous nature of many interactions between the members of a small and isolated community. Such communities may be able to use these multiple interactions to enforce informal restrictions on the usage of local commons. To the extent that the process of economic development reduces the number of non-anonymous interactions among community members, it will reduce the ability of the community to successfully manage the local commons informally. The resulting need for either explicit regulation or the introduction of private property rights represents a hidden cost of development.

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

Based in part on the author's thesis, (Ph.D.) in the M.I.T. Dept. of Economics, 1977.

Thesis (D.A.)--Illinois State University, 1993. / Title from title page screen, viewed March 6, 2006. Dissertation Committee: Tony Ostrosky, Mark Walbert (co-chairs), Mathew Moray, David D. Ramsey, Patricia Klass. Includes bibliographical references (leaves 99-111) and abstract. Also available in print.

The effects of endogenously generated information on decision making is studied within three economic institutions. A non-market institution, (voluntary contributions for the provision of a public good), and a market institution, (sealed bid auctions), which both have been extensively studied as non dynamic institutions were used to examine the effects of dynamically generated information. A third institution, the double auction, which has been studied as a dynamic institution, was used to develop prototype methodology for the simulation and estimation of decision strategies with dynamic environments. Experimental results are presented showing the effects of allowing real time revisions of voluntary contributions for the provision of a public good. Four public good payoff functions are examined, each of which generates specific equilibria. Evidence of increased provision of the public good is demonstrated for: (i) the case in which revisions are limited to increases and a provision point exists, and also (ii) the case in which there is a high initial marginal return from the public good. An experimental investigation of sequential first and second price sealed bid auctions is conducted examining the effects of known capacity constraints on bidding behavior. Results are presented and compared to a Nash equilibrium model developed by Robert Weber. These naturally occurring inter-auction limitations are shown to significantly affect revenue generation capabilities of sealed bid auctions. Bidding and price behavior is presented and is found to be inconsistent with the model. A methodology is proposed as a means for attempting to identify and estimate strategies utilized by participants within dynamic institutions. The methodology was used on the double auction. Computer automata are used to examine the contracting behavior of a variety of decision rules. Simulations of the decision model are run using parameters common to past experiments. The resulting contracts are compared to corresponding experiment contracts and are found to follow similar patterns. Two double auction experiments, each with ten subjects were used to generate actual contracting data. The parameters of the proposed decision model are estimated from data on the individual decisions of the subjects.

No description available.

No description available.

No description available.

Thesis (Ph. D.)--University of Chicago, Dept. of Sociology, August 2001. / Includes bibliographical references. Also available on the Internet.