Bayesian Persuasion: Reduced Form Approach, 2022 (with Juuso Toikka and Akhil Vohra)

We introduce reduced form representations of Bayesian persuasion problems where the variables are the probabilities that the receiver takes each of her actions. These are simpler objects than, say, the joint distribution over states and actions in the obedience formulation of the persuasion problem. This can make a difference in computational and analytical tractability which we illustrate with two applications. The first shows that with quadratic receiver payoffs, the worst-case complexity scales with the number of actions and not the number of states. If |A | and |S | denote the number of actions and states respectively, the worst case complexity of the obedience formulation is O(|A |^{2.5} max{|A | ^{2.5} ,|S | ^{2.5}). The worst case complexity of the reduced form representation is O(|A |^{3} ). In the second application, the reduced form leads to a simple greedy algorithm to determine the maximum value a sender can achieve in any cheap talk equilibrium

Contagion and Equilibria in Diversified Financial Networks, 2021 (with Victor Amelkin and Santosh Venkatesh)

Diversified cross-shareholding networks are thought to be more resilient to shocks, but diversification also increases the channels by which a shock can spread. To resolve these competing intuitions we introduce a stochastic model of a diversified cross-shareholding network in which a firm’s valuation depends on its cash endowment and the shares it owns in other firms. We show that a concentration of measure phenomenon emerges: almost all realized network instances drawn from any probability distribution in a wide class are resilient to contagion if endowments are sufficiently large. Furthermore, the size of a shock needed to trigger widespread default increases with the exposure of firms to each other. Distributions in this class are characterized by the property that a firm’s equity shares owned by others are weakly dependent yet lack “dominant” shareholders.

On inner independence systems, 2021 (with Sven de Vries and Stepen Raach)

A classic result of Korte (1978) and Jenkyns (1976) bounds the quality of the greedy solution to the problem of finding a maximum weight basis of an independence system $\I$ in terms of the rank quotient of $\I$. We extend this result in two ways. First, we apply the greedy algorithm to an inner independence system contained in $\I$. Additionally, following an idea of Milgrom (2017), we extend this result in two ways. First, we apply the greedy algorithm to an inner independence system contained in $\I$. Additionally, following an idea of Milgrom (2017), we incorporate exogenously given prior information about the set of likely candidates for an optimal basis in terms of a set $\Oh\subseteq \I$. We provide a generalization of the rank quotient that yields a tight bound on the worst case performance of the greedy algorithm applied to the inner independence system relative to the optimal solution in $\Oh$. Furthermore, we show that the inner independence system approximation may outperform not only the standard greedy algorithm but also the inner matroid approximation proposed by Milgrom (2017).

Second, we generalize the inner approximation framework to inner approximation of packing instances in $\Z^n_+$ by inner polymatroids and inner packing instances. We consider the problem of maximizing a separable discrete concave function and show that our inner approximation can be better than the greedy algorithm applied to the original packing instance. Our result provides a lower bound to the generalized rank-quotient of a greedy algorithm to the optimal solution in this more general setting and subsumes Malinov (1980).

Moment Multicalibration for Uncertainty Estimation, 2020 (with Christopher Jung, Changhwa Lee, Mallesh M. Pai & Aaron Roth)

We show how to achieve the notion of ``multicalibration'' from Hebert-Johnson, Kim, Reingold & Rothblum (2018) not just for means, but also for variances and other higher moments. Informally, it means that we can find regression functions which, given a data point, can make point predictions not just for the expectation of its label, but for higher moments of its label distribution as well---and those predictions match the true distribution quantities when averaged not just over the population as a whole, but also when averaged over an enormous number of finely defined subgroups. It yields a principled way to estimate the uncertainty of predictions on many different subgroups---and to diagnose potential sources of unfairness in the predictive power of features across subgroups. As an application, we show that our moment estimates can be used to derive marginal prediction intervals that are simultaneously valid as averaged over all of the (sufficiently large) subgroups for which moment multicalibration has been obtained.

Near Substitute Preferences and Equilibria with Indivisibilities, 2020 (with Thanh Nguyen)

The single improvement property for quasi-linear preferences over indivisible goods says an agent can improve upon a suboptimal bundle by adding a single item, dropping a single item, or both. We extend the notion of single improvement to non-quasi-linear preferences which allows us to generalize the existence of competitive equilibrium to non-quasi linear preferences. If one allows for improvements that involve the exchange of up to $\Delta$ items we derive prices at which the excess demand for each good is bounded by $\Delta-1$, a quantity independent of the size of the economy. We also give applications of this result to pseudo-markets for the allocation of collectively owned resources.

Testing Alone Is Insufficient, 2020 (with Rahul Deb, Mallesh Pai and Akhil Vohra)

Fear of infection will limit economic activity. Widespread testing alone will not solve this problem. Targeted testing in concert with targeted subsidies will be essential. We propose a model in which both testing and transfers are targeted. We use it to jointly determine where agents should be tested and how they should be incentivized. We find that in settings where agents earn a low wage, have a high risk of becoming infected, and bear a large cost of falling ill, testing should be conducted at work only. On the other hand, when testing is very costly, agents that have high wages and low expected costs associated with falling ill should be tested at home.

Constrained Trading Networks, 2020 (with Can Kizilkale)

Trades based on bilateral (indivisible) contracts can be represented by a network. Vertices correspond to agents while arcs represent the non-price elements of a bilateral contract. Given prices for each arc, agents choose the incident arcs that maximize their utility. We enlarge the model to allow for polymatroidal constraints on the set of contracts that may be traded which can be interpreted as modeling limited one-for-one substitution. We show that for two-sided markets there exists a competitive equilibrium however for multi-sided markets this may not be possible.

Fair Prediction with Endogenous Behavior, 2020 (with Christopher Jung, Sampath Kannan, ChangHwa Lee, Mallesh Pai & Aaron Roth)

There is increasing regulatory interest in whether machine learning algorithms deployed in consequential domains (e.g. in criminal justice) treat different demographic groups ?fairly.? However, there are several proposed notions of fairness, typically mutually incompatible. Using criminal justice as an example, we study a model in which society chooses an incarceration rule. Agents of different demographic groups differ in their outside options (e.g. opportunity for legal employment) and decide whether to commit crimes. We show that equalizing type I and type II errors across groups is consistent with the goal of minimizing the overall crime rate; other popular notions of fairness are not.

Optimal On-line Allocation Rules with Costly Verification, 2019 (with Markos Epitropou)

We consider a principal who allocates an indivisible object among a finite number of agents who arrive on-line, each of whom prefers to have the object than not. Each agent has access to private information about the principal's payoff if he receives the object. The decision to allocate the object to an agent must be made upon arrival of an agent and is irreversible. There are no monetary transfers but the principal can inspect agents' reports at a cost and punish them. A novelty of this paper is a reformulation of this on-line problem as a compact linear program. Using the formulation we characterize the form of the optimal mechanism and reduce the on-line version of the inspection problem with identical distributions to an instance of the secretary problem with one fewer secretary and a modified value distribution. This reduction also allows us to derive a prophet inequality for the on-line version of the inspection problem.

Strategic Formation and Reliability of Supply Chain Networks, 2019 (with Victor Amelkin)

Supply chains are the backbone of the global economy. Disruptions to them can be costly. Centrally managed supply chains invest in ensuring their resilience. Decentralized supply chains, however, must rely upon the self-interest of their individual components to maintain the resilience of the entire chain. We examine the incentives that independent self-interested agents have in forming a resilient supply chain network in the face of production disruptions and competition. In our model, competing suppliers are subject to yield uncertainty (they deliver less than ordered) and congestion (lead time uncertainty or, "soft" supply caps). Competing retailers must decide which suppliers to link to based on both price and reliability. In the presence of yield uncertainty only, the resulting supply chain networks are sparse. Retailers concentrate their links on a single supplier, counter to the idea that they should mitigate yield uncertainty by diversifying their supply base. This happens because retailers benefit from supply variance. It suggests that competition will amplify output uncertainty. When congestion is included as well, the resulting networks are denser and resemble the bipartite expander graphs that have been proposed in the supply chain literature, thereby, providing the first example of endogenous formation of resilient supply chain networks, without resilience being explicitly encoded in payoffs. Finally, we show that a supplier's investments in improved yield can make it worse off. This happens because high production output saturates the market, which, in turn lowers prices and profits for participants.

The Network Effect of Agency Conflicts, 2019 (with Yiqing Xing and Wu Zhu).

We argue that the nature of firm-level agency conflicts counters the role of network structure in the propagation of shocks. These conflicts can have an effect on system-wide behavior that is both significant and different from those predicted based on network structure alone. This implies that corporate governance can play an important role in macro fluctuations. We consider a collection of firms linked through equity cross-holdings whose managers can take investment decisions in response to an exogenous shock. Prior work concludes that more integrated networks amplify shocks. We find that if managers are subject to default costs or limited liability, this effect is reversed because their investment decisions mitigate the spread of an initial shock. In the face of moral hazard, however, their investment choices amplify an initial shock. In particular, when the network is fully diversified the aggregate effect of idiosyncratic shocks is not small as received wisdom would suggest.