I am a graduate student in the theory of computing group at UW–Madison, where I am grateful to be advised by Shuchi Chawla. I received my B.S. in Computer Science and Engineering Physics from Cornell University.
In 2016-17 and 2017-18 I was supported by a Cisco graduate fellowship.
In 2018, I was a Core Data Science Intern at Facebook, where my manager was Eric Sodomka.
My CV can be found here.
I work in the design and analysis of algorithms, especially algorithmic mechanism design. I am particularly interested in "simple" mechanisms which perform well under models of boundedly rational participants.
Consider the revenue maximization problem of a risk-neutral seller with \(m\) items for sale to a single additive buyer, whose values for the items are drawn from known distributions. If the buyer is also risk-neutral, it is known that a simple and natural mechanism gives a constant-factor approximation to the optimal revenue. In this paper we study revenue maximization when buyers may be optimistic or pessimistic. Specifically, we adopt cumulative prospect theory, a well established generalization of expected utility theory. Informally, given an event that occurs with probability \(q < 1\), a pessimistic buyer values that event less than \(q\) times the value of the outcome when it occurs with certainty, and an optimistic buyer values it more.
Our starting observation is that such nonlinear preferences give rise to a very rich space of mechanisms, allowing the seller to extract arbitrary revenue. Specifically, a seller can construct extreme lotteries that look attractive to a mildly optimistic buyer, but have arbitrarily negative true expectation. Therefore, giving the seller absolute freedom over the design space makes competing with the optimal mechanism hopeless.
Instead, we study three broad classes of mechanisms, each characterized by a distinct use of randomness. Our goal is twofold: to explore the power of randomness when the buyer is not risk-neutral, and to design simple and attitude-agnostic mechanisms—mechanisms that do not depend on details of the buyer's risk attitude—which are good approximations of the optimal mechanism, tailored to a specific risk attitude. Our main result is that a single simple and risk-agnostic mechanism—namely the same fixed-price mechanism which gives a good approximation for risk-neutral buyers—gives a good approximation to the revenue extracted by the optimal non-agnostic mechanism within each class we study.
We present pricing mechanisms for several online resource allocation problems which obtain tight or nearly tight approximations to social welfare. In our settings, buyers arrive online and purchase bundles of items; buyers' values for the bundles are drawn from known distributions. This problem is closely related to the so-called prophet-inequality of Krengel and Sucheston and its extensions in recent literature. Motivated by applications to cloud economics, we consider two kinds of buyer preferences. In the first, items correspond to different units of time at which a resource is available; the items are arranged in a total order and buyers desire intervals of items. The second corresponds to bandwidth allocation over a tree network; the items are edges in the network and buyers desire paths.
Because buyers' preferences have complementarities in the settings we consider, recent constant-factor approximations via item prices do not apply, and indeed strong negative results are known. We develop static, anonymous bundle pricing mechanisms.
For the interval preferences setting, we show that static, anonymous bundle pricings achieve a sublogarithmic competitive ratio, which is optimal (within constant factors) over the class of all online allocation algorithms, truthful or not. For the path preferences setting, we obtain a nearly-tight logarithmic competitive ratio. Both of these results exhibit an exponential improvement over item pricings for these settings. Our results extend to settings where the seller has multiple copies of each item, with the competitive ratio decreasing linearly with supply. Such a gradual tradeoff between supply and the competitive ratio for welfare was previously known only for the single item prophet inequality.
Most work in mechanism design assumes that buyers are risk neutral; some considers risk aversion arising due to a non-linear utility for money. Yet behavioral studies have established that real agents exhibit risk attitudes which cannot be captured by any expected utility model. We initiate the study of revenue-optimal mechanisms under behavioral models beyond expected utility theory. We adopt a model from prospect theory which arose to explain these discrepancies and incorporates agents under-weighting uncertain outcomes. In our model, an event occurring with probability x < 1 is worth strictly less to the agent than x times the value of the event when it occurs with certainty.
We present three main results. First, we characterize optimal mechanisms as menus of two-outcome lotteries. Second, we show that under a reasonable bounded-risk-aversion assumption, posted pricing obtains a constant approximation to the optimal revenue. Notably, this result is "risk-robust" in that it does not depend on the details of the buyer’s risk attitude. Third, we consider dynamic settings in which the buyer’s uncertainty about his future value may allow the seller to extract more revenue. In contrast to the positive result above, here we show it is not possible to achieve any constant-factor approximation to revenue using deterministic mechanisms in a risk-robust manner.
We consider the problem of maximizing revenue for a monopolist offering multiple items to multiple heterogeneous buyers. We develop a simple mechanism that obtains a constant factor approximation under the assumption that the buyers' values are additive subject to a feasibility constraint and independent across items. Importantly, different buyers in our setting can have different constraints on the sets of items they desire. Our mechanism is a sequential variant of two-part tariffs. Prior to our work, simple approximation mechanisms for such multi-buyer problems were known only for the special cases of all unit-demand or all additive value buyers.
Our work expands upon and unifies long lines of work on unit-demand settings and additive settings. We employ the ex ante relaxation approach developed by Alaei (2011) for reducing a multiple-buyer mechanism design problem with an ex post supply constraint into single-buyer ones with ex ante supply constraints. Solving the single-agent problems requires us to significantly extend techniques developed in the context of additive values by Li and Yao (2013) and their extension to subadditive values by Rubinstein and Weinberg (2015).
Office: CS 4397
Email: bmiller at cs wisc edu