I am a graduate student in the theory of computing group at UW–Madison, where I am 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 am supported by a Cisco graduate fellowship.
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.
We study an online resource allocation problem where a seller has many items with multiplicities to offer and the items are arranged in a total order. Buyers are interested in buying intervals of items, and have different values for different intervals, drawn from a known distribution. The seller's goal is to design an online allocation mechanism that maximizes social welfare. Importantly, buyers' preferences have complementarities, so that recently-developed constant-factor approximations via item prices do not apply, and indeed strong negative results are known.
We consider a static, anonymous bundle pricing mechanism—the seller partitions his supply into bundles of items and determines a price for each bundle. The buyers arrive in arbitrary order and purchase their favorite bundles while supply lasts. We show that when buyers value intervals up to length \(L\), bundle pricing achieves an \(O\left(\frac{\log L}{\log\log L}\right)\) approximation to the optimal social welfare. This result is tight by a known lower bound on any online algorithm for this problem, even one that does not respect incentive constraints. Bundle pricing is therefore an optimal mechanism, and incentive constraints impose at most an additional constant-factor loss in approximation.
We also extend our result to settings in which the seller has multiple copies of each item. When \(B \ge 1\) denotes the minimum multiplicity of any item, we show that the approximation factor decays like \(\frac1B\), and this is tight. Finally, we show that our bounds continue to hold (within constant factors) when the seller faces convex production costs.
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