This paper introduces a novel framework for modeling diversity using the theory of majorization and applies it to school choice problems. We consider a school with limited capacity that must select students from an applicant pool, where each student is classified into types (e.g., by race, gender, or socioeconomic status). Within this setting, we ask: How should we compare the diversity of student groups? And what admissions procedure balance the school's goal of admitting students with the highest priority (e.g., academic merit, proximity to the school) and achieving a diverse student body?

We study matching markets with aligned preferences and establish a connection between common design objectives---stability, efficiency, and fairness---and the theory of optimal transport. Optimal transport gives new insights into the structural properties of matchings obtained from pursuing these objectives, and into the trade-offs between different objectives. Matching markets with aligned preferences provide a tractable stylized model capturing supply-demand imbalances in a range of settings such as partnership formation, school choice, organ donor exchange, and markets with transferable utility where bargaining over transfers happens after a match is formed.

We study the complexity of closure operators, with applications to machine learning and decision theory. In machine learning, closure operators emerge naturally in data classification and clustering. In decision theory, they can model equivalence of choice menus, and therefore situations with a preference for flexibility. Our contribution is to formulate a notion of complexity of closure operators, which translate into the complexity of a classifier in ML, or of a utility function in decision theory.

We show that adding noise to data before making data public is effective at screening p-hacked findings: spurious explanations of the outcome variable produced by attempting multiple econometric specifications. Noise creates "baits'' that affect two types of researchers differently. Uninformed p-hackers who engage in data mining with no prior information about the true causal mechanism often fall for baits and report verifiably wrong results when evaluated with the original data. But informed researchers who start with an ex-ante hypothesis about the causal mechanism before seeing any data are minimally affected by noise. We characterize the optimal level of dissemination noise and highlight the relevant trade-offs in a simple theoretical model. Dissemination noise is a tool that statistical agencies (e.g., the US Census Bureau) currently use to protect privacy, and we show this existing practice can be repurposed to improve research credibility.

We consider active learning under incentive compatibility constraints. The main application of our results is to economic experiments, in which a learner seeks to infer the parameters of a subject’s preferences: for example their attitudes towards risk, or their beliefs over uncertain events. By cleverly adapting the experimental design, one can save on the time spent by subjects in the laboratory, or maximize the information obtained from each subject in a given laboratory session; but the resulting adaptive design raises complications due to incentive compatibility. A subject in the lab may answer questions strategically, and not truthfully, so as to steer subsequent questions in a profitable direction. We analyze two standard economic problems: inference of preferences over risk from multiple price lists, and belief elicitation in experiments on choice over uncertainty. In the first setting, we tune a simple and fast learning algorithm to retain certain incentive compatibility properties. In the second setting, we provide an incentive compatible learning algorithm based on scoring rules with query complexity that differs from obvious methods of achieving fast learning rates only by subpolynomial factors. Thus, for these areas of application, incentive compatibility may be achieved without paying a large sample complexity price.

We revisit the connection between bargaining and equilibrium in exchange economies, and study its algorithmic implications. We consider bargaining outcomes to be allocations that cannot be blocked (i.e., profitably re-traded) by coalitions of small size and show that these allocations must be approximate Walrasian equilibria. Our results imply that deciding whether an allocation is approximately Walrasian can be done in polynomial time, even in economies for which finding an equilibrium is known to be computationally hard.

We study whether some of the most important models of decision-making under uncertainty are uniformly learnable, in the sense of PAC (probably approximately correct) learnability. Many studies in economics rely on Savage's model of (subjective) expected utility. The expected utility model is known to predict behavior that runs counter to how many agents actually make decisions (the contradiction usually takes the form of agents' choices in the Ellsberg paradox). As a consequence, economists have developed models of choice under uncertainty that seek to generalize the basic expected utility model. The resulting models are more general and therefore more flexible, and more prone to overfitting. The purpose of our paper is to understand this added flexibility better. We focus on the classical expected utility (EU) model, and its two most important generalizations: Choquet expected utility (CEU) and Max-min Expected Utility (MEU).

This paper initiates the study of the testable implications of choice data in settings where agents have privacy preferences. We adapt the standard conceptualization of consumer choice theory to a situation where the consumer is aware of, and has preferences over, the information revealed by her choices. The main message of the paper is that little can be inferred about consumers' preferences once we introduce the possibility that the consumer has concerns about privacy. This holds even when consumers' privacy preferences are assumed to be monotonic and separable. This motivates the consideration of stronger assumptions and, to that end, we introduce an additive model for privacy preferences that does have testable implications.

We study the structural complexity of bimatrix games, formalized via rank, from an empirical perspective. We consider a setting where we have data on player behavior in diverse strategic situations, but where we do not observe the relevant payoff functions. We prove that high complexity (high rank) has empirical consequences when arbitrary data is considered. Additionally, we prove that, in more restrictive classes of data (termed laminar), any observation is rationalizable using a low-rank game: specifically a zero-sum game. Hence complexity as a structural property of a game is not always testable. Finally, we prove a general result connecting the structure of the feasible data sets with the highest rank that may be needed to rationalize a set of observations.

In this work, we study the complexity of finding a Walrasian equilibrium. Our main result gives an algorithm which can compute an approximate Walrasian equilibrium in an exchange economy with general, but well-behaved, utility functions in time that is polynomial in the number of goods when the number of agents is held constant. This result has applications to macroeconomics and finance, where applications of Walrasian equilibrium theory tend to deal with many goods but a fixed number of agents.

Recent results in complexity theory suggest that various economic theories require agents to solve computationally intractable problems. However, such results assume the agents are optimizing explicit utility functions, whereas the economic theories merely assume the agents behave rationally, where rational behavior is defined via some optimization problem. Might making rational choices be easier than solving the corresponding optimization problem? For at least one major economic theory, the theory of the consumer (which simply postulates that consumers are utility maximizing), we find this is indeed the case. In other words, we prove the possibly surprising result that computational constraints have no empirical consequences for consumer choice theory.