A stochastic mapping from states to signals induces a distribution over possible posteriors. For a variety of purposes one is interested in parameters of these posteriors, possibly multi-dimensional, such as their quartiles or whether they first-order stochastically dominate some given distribution. Many parameters of interest can be encoded by requiring the posterior at each signal lie point-wise between two given distributions. Given a collection of these bounding pairs, one for each signal, we characterize the set of posteriors that can be realized by some stochastic mapping of states to signals. We provide applications of this result to, among others, the design of securities, price, and statistical discrimination.

Abstract To understand how supply uncertainty affects the structure of supply chain networks we consider a setting where retailers and suppliers must establish a costly relationship with each other prior too engaging in trade. Suppliers, with uncertain yield, announce wholesale prices, while retailers must decide which suppliers to link to based on their wholesale prices. Subsequently, retailers compete with each other in Cournot fashion to sell the acquired supply to consumers. We find that in equilibrium retailers concentrate their links among too few suppliers, that is, there is insufficient diversification of the supply base. We find that either reduction in supply variance or increase in mean supply, increases a supplier's profit. However, these two ways of improving service have qualitatively different effects on welfare: improvement of the expected yield by a supplier makes everyone better off, whereas change in the variance of the yield impacts system members differently.

We show how to achieve the notion of "multicalibration" from Hebert-Johnson et al. (2018) not just for means, but also for variances and other higher moments. Informally, this 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.

Gross substitutes for quasi-linear preferences is characterized by the single improvement property, which says an agent can improve upon a sub-optimal bundle by adding or dropping a single item, or exchanging one item for another. We extend this notion in two ways: by allowing for non-quasi-linear preferences and the exchange of up to Delta items. Our results connect the improvement property with the geometry of the choice correspondence. We derive prices at which the excess demand for each good is at most Delta-1 and provide applications to the design of pseudo-markets for allocating indivisible resources.

We study the incentives that independent self-interested agents have in forming a resilient supply chain network in the face of disruptions and competition. Competing suppliers are subject to yield uncertainty and congestion. Competing retailers make sourcing decisions based on price and reliability. Under yield uncertainty only, retailers---benefiting from supply variance---concentrate their links on a single supplier, counter to the idea that they should mitigate yield uncertainty by multi-sourcing. When congestion is added, the resulting networks resemble bipartite expanders known to be resilient, thus, providing the first example of endogenously formed resilient supply chains.

There is great 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.

We consider settings in which we wish to incentivize myopic agents (such as Airbnb landlords, who may emphasize short-term profits and property safety) to treat arriving clients fairly, in order to prevent overall discrimination against individuals or groups. We model such settings in both classical and contextual bandit models in which the myopic agents maximize rewards according to current empirical averages, but are also amenable to exogenous payments that may cause them to alter their choices. Our notion of fairness asks that more qualified individuals are never (probabilistically) preferred over less qualifie ones [8].

The problem of finding stable matches that meet distributional concerns is usually formulated by imposing various side constraints. Prior work has focused on constraints whose "right hand sides" are absolute numbers specified before the preferences or number of agents on the "proposing" side are known. In many cases it is more natural to express the relevant constraints as proportions. We treat such constraints as soft, but provide ex-post guarantees on how well the constraints are satisfied while preserving stability. We violate the proportions by an amount proportional to the reciprocal of the number of students assigned to the school. For example, if a school is assigned 100 students, then the actual proportion will differ from the desired proportion by at most 2%. Our technique requires an extension of Scarf's lemma, which is of independent interest.

Under full substitutability of preferences, it has been shown that a competitive equilibrium exists in trading networks, and is equivalent (after a restriction to equilibrium trades) to (chain) stable outcomes. In this paper, we formulate the problem of finding an efficient outcome as a generalized submodular flow problem on a suitable network. Equivalence with seemingly weaker notions of stability follows directly from the optimality conditions, in particular the absence of improvement cycles in the flow problem. Our formulation yields strongly polynomial algorithms for finding competitive equilibria in trading networks, and testing (chain) stability.

Walrasian equilibrium prices have a remarkable property: they allow each buyer to purchase a bundle of goods that she finds the most desirable, while guaranteeing that the induced allocation over all buyers will globally maximize social welfare. However, this clean story has two caveats. * First, the prices may induce indifferences. In fact, the minimal equilibrium prices necessarily induce indifferences. Accordingly, buyers may need to coordinate with one another to arrive at a socially optimal outcome---the prices alone are not sufficient to coordinate the market. * Second, although natural procedures converge to Walrasian equilibrium prices on a fixed population, in practice buyers typically observe prices without participating in a price computation process. These prices cannot be perfect Walrasian equilibrium prices, but instead somehow reflect distributional information about the market. To better understand the performance of Walrasian prices when facing these two problems, we give two results. First, we propose a mild genericity condition on valuations under which the minimal Walrasian equilibrium prices induce allocations which result in low over-demand, no matter how the buyers break ties. In fact, under genericity the over-demand of any good can be bounded by 1, which is the best possible at the minimal prices. We demonstrate our results for unit demand valuations and give an extension to matroid based valuations (MBV), conjectured to be equivalent to gross substitute valuations (GS). Second, we use techniques from learning theory to argue that the over-demand and welfare induced by a price vector converge to their expectations uniformly over the class of all price vectors, with respective sample complexity linear and quadratic in the number of goods in the market. These results make no assumption on the form of the valuation functions. These two results imply that under a mild genericity condition, the exact Walrasian equilibrium prices computed in a market are guaranteed to induce both low over-demand and high welfare when used in a new market where agents are sampled independently from the same distribution, whenever the number of agents is larger than the number of commodities in the market.

The National Resident Matching program strives for a stable matching of medical students to teaching hospitals. With the presence of couples, stable matchings need not exist. For any student preferences, we show that each instance of a stable matching problem has a 'nearby' instance with a stable matching. The nearby instance is obtained by perturbing the capacities of the hospitals. Our approach is general and applies to other type of complementarities, as well as matchings with side constraints and contracts.

A classical trading experiment consists of a set of unit demand buyers and unit supply sellers with identical items. Each agent’s value or opportunity cost for the item is their private information and preferences are quasi-linear. Trade between agents employs a double oral auction (DOA) in which both buyers and sellers call out bids or offers which an auctioneer recognizes. Transactions resulting from accepted bids and offers are recorded. This continues until there are no more acceptable bids or offers. Remarkably, the experiment consistently terminates in a Walrasian price. The main result of this paper is a mechanism in the spirit of the DOA that converges to a Walrasian equilibrium in a polynomial number of steps, thus providing a theoretical basis for the above-described empirical phenomenon. It is well-known that computation of a Walrasian equilibrium for this market corresponds to solving a maximum weight bipartite matching problem. The uncoordinated but rational responses of agents thus solve in a distributed fashion a maximum weight bipartite matching problem that is encoded by their private valuations. We show, furthermore, that every Walrasian equilibrium is reachable by some sequence of responses. This is in contrast to the well known auction algorithms for this problem which only allow one side to make offers and thus essentially choose an equilibrium that maximizes the surplus for the side making offers. Our results extend to the setting where not every agent pair is allowed to trade with each other. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

In a limited form cellular providers have long shared spectrum in the form of roaming agreements. The primary motivation for this has been to extend the coverage of a wireless carrier's network into regions where it has no infrastructure. As devices and infrastructure become more agile, such sharing could be done on a much faster time-scale and have advantages even when two providers both have coverage in a given area, e.g., by enabling one provider to acquire “overflow” capacity from another provider during periods of high demand. This may provide carriers with an attractive means to better meet their rapidly increasing bandwidth demands. On the other hand, the presence of such a sharing agreement could encourage providers to underinvest in their networks, resulting in poorer performance. We adapt the newsvendor model from the operations management literature to model such a situation and to gain insight into these trade-offs. In particular, we analyze the structure of revenue-sharing contracts that incentivize both capacity sharing and increased access for end-users.

Markets are often viewed as a key ingredient in facilitating more efficient dynamic spectrum access. In this paper we consider how such spectrum markets are influenced by a key property of the wireless medium: interference. Interference can result in "complementarities" among the "spectrum goods" being traded, which complicates the design of an efficient market mechanism. We consider several alternative models for defining such spectrum goods, and explore the impact of these choices on the complexity of the resulting market.

Extensive spectrum markets have the potential to enable more efficient use of this limited resource. Such markets must account for particular properties of the underlying wireless medium. In this paper we focus on one such aspect: the role of interference created among different agents who may purchase the right to use the same spectrum at nearby locations. Such interference can result in “complementarities” among the spectrum goods being traded, which complicates the design of an efficient market. We begin with a simple linear model for these complementarities that was shown to be computationally difficult in earlier work. We give several approximation algorithms for this model. We then consider several alternative models in which the spectrum goods are defined in different ways and explore the impact of these choices on the complexity of the resulting market.

Consider a weather forecaster predicting the probability of rain for the next day. We consider tests that given a finite sequence of forecast predictions and outcomes will either pass or fail the forecaster. It is known that any test which passes a forecaster who knows the distribution of nature can also be probabilistically passed by a forecaster with no knowledge of future events. This note summarizes and examines the computational complexity of such forecasters.

We study the Cost-Per-Action or Cost-Per-Acquisition (CPA) charging scheme in online advertising. In this scheme, instead of paying per click, the advertisers pay only when a user takes a specific action (e.g. fills out a form) or completes a transaction on their websites.

We study a sequential auction for sharing a wireless resource (bandwidth or power) among competing transmitters. The resource is assumed to be managed by a spectrum broker (auctioneer), who collects bids and allocates discrete units of the resource via a sequential second-price auction. It is well known that a second price auction for a single indivisible good has an efficient dominant strategy equilibrium; this is no longer the case when multiple units of a homogeneous good are sold in repeated iterations. For two users with full information, we show that such an auction has a unique equilibrium allocation. The worst-case efficiency of this allocation is characterized under the following cases: (i) both bidders have a concave valuation for the spectrum resource, and (ii) one bidder has a concave valuation and the other bidder has a convex valuation (e.g., for the other useriquests power). Although the worst-case efficiency loss can be significant, numerical results are presented, which show that for randomly placed transmitter-receiver pairs with rate utility functions, the sequential second-price auction typically achieves the efficient allocation. For more than two users it is shown that this mechanism always has a pure strategy equilibrium, but in general there may be multiple equilibria. We give a constructive procedure for finding one equilibrium; numerical results show that when all users have concave valuations the efficiency loss decreases with an increase in the number of users.

A sequence of prices and demands are rationalizable if there exists a concave, continuous and monotone utility function such that the demands are the maximizers of the utility function over the budget set corresponding to the price. Afriat [1] presented necessary and sufficient conditions for a finite sequence to be rationalizable. Varian [20] and later Blundell et al. [3, 4] continued this line of work studying nonparametric methods to forecasts demand. Their results essentially characterize learnability of degenerate classes of demand functions and therefore fall short of giving a general degree of confidence in the forecast. The present paper complements this line of research by introducing a statistical model and a measure of complexity through which we are able to study the learnability of classes of demand functions and derive a degree of confidence in the forecasts.Our results show that the class of all demand functions has unbounded complexity and therefore is not learnable, but that there exist interesting and potentially useful classes that are learnable from finite samples. We also present a learning algorithm that is an adaptation of a new proof of Afriat's theorem due to Teo and Vohra [17].

Many auctions involve the sale of a variety of distinct assets. Examples are airport time slots, delivery routes, network routing, and furniture. Because of complementarities or substitution effects between the different assets, bidders have preferences not just for particular items but for sets of items. For this reason, economic efficiency is enhanced if bidders are allowed to bid on bundles or combinations of different assets. This paper surveys the state of knowledge about the design of combinatorial auctions and presents some new insights. Periodic updates of portions of this survey will be posted to this journal's Online Supplements web page at http://joc.pubs.informs.org/OnlineSupplements.html

We introduce in this paper an exact nonlinear formulation of the multiway cut problem. By simple linearizations of this formulation, we derive several well-known and new formulations for the problem. We further establish a connection between the multiway cut and the maximum-weighted independent set problem. This leads to the study of several instances of the multiway cut problem through the theory of perfect graphs. We also introduce a new randomized rounding argument to study the sharpness of these formulations. © 1999 John Wiley & Sons, Inc. Networks 34: 102–114, 1999

Under a variety of different random models of the maximal covering location problem, we show that the relative error of a randomly generated solution converges to zero in expectation as problem size grows. We prove similar results for the relative error between the optimal integer and fractional solutions to the problem. Suppose that randomly generated instances of this problem are used to test heuristics. One consequence of our results is that we should expect the mean relative error of a heuristic to be better than that of randomly generated solutions, if the heuristic is to be considered useful.

We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the make span, the completion time of the last job. In the on-line version, as soon as job j arrives, it must be assigned immediately to one of the m machines.

Review of F.S. Hillier and G.J. Lieberman (1990) Introduction to Mathematical Programming, 5th Edition, and Introduction to Stochastic Models in Operations Research, 5th Edition, McGraw-Hill Publishing Company, Hightstown, NJ. Reviewed by Rakesh V. Vohra, Faculty of Management Sciences, Ohio State University, Columbus, Ohio 43210, USA. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

In this note, an $O ( | V |k )$ algorithm is described for determining whether an interval graph on $| V |$ vertices has a bandwidth less than or equal to a given integer k. While the algorithm is not the first to resolve this problem, it does admit a shorter proof of its correctness than a previous algorithm of the same complexity due to Kratsch (Information and Computation, 74 (1987), pp. 140–158).

Abstract In this paper we study the probabilistic behavior of the farthest neighbor heuristic for finding the longest Hamiltonian tour in a graph. We assume the edge weights are independent random variables uniformly distributed in [0,1]. If F, is the length of the heuristic tour and L, the optimal tour then Fn/Ln → 1 a.s. as n → α. We also show that Ln/n → 1 a.s. as n → ∞.