This paper derives polynomial-time approximation schemes for several NP-hard stochastic optimization problems from the algorithmic mechanism design and operations research literatures. The problems we consider involve a principal or seller optimizing with respect to a subsequent choice by an agent or buyer. These include posted pricing for a unit-demand buyer with independent values (Chawla et al. [19], Cai and Daskalakis [16]), assortment optimization with independent utilities (Talluri and van Ryzin [53]), and delegated choice (Khodabakhsh et al. [36]). Our results advance the state of the art for each of these problems. For unit-demand pricing with discrete distributions, our multiplicative PTAS improves on the additive PTAS of Cai and Daskalakis [16], and we additionally give a PTAS for the unbounded regular case, improving on the latter paper’s QPTAS. For assortment optimization, no constant approximation was previously known. For delegated choice, we improve on both the 3 -approximation for the case with no outside option and the super-constant-approximation with an outside option.A key technical insight driving our results is an economically meaningful property we term utility alignment. Informally, a problem is utility aligned if, at optimality, the principal derives most of their utility from realizations where the agent’s utility is also high. Utility alignment allows the algorithm designer to focus on maximizing performance on realizations with high agent utility, which is often an algorithmically simpler task. We prove utility alignment results for all the problems mentioned above, including strong results for unit-demand pricing and delegation, as well as a weaker but very broad guarantee that holds for many other problems under very mild conditions.

This paper studies delegation in a model of discrete choice. In the delegation problem, an uninformed principal must consult an informed agent to make a decision. Both the agent and principal have preferences over the decided-upon action which vary based on the state of the world, and which may not be aligned. The principal may commit to a mechanism, which maps reports of the agent to actions. When this mechanism is deterministic, it can take the form of a menu of actions, from which the agent simply chooses upon observing the state. In this case, the principal is said to have delegated the choice of action to the agent.

We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al.

In a decentralized system with m machines, we study the selfish scheduling problem where each user strategically chooses which machine to use. Each machine incurs a cost, which is a function of the total load assigned to it, and some cost-sharing mechanism distributes this cost among the machine's users. The users choose a machine aiming to minimize their own share of the cost, so the cost-sharing mechanism induces a game among them. We approach this problem from the perspective of a designer who can select which cost-sharing mechanism to use, aiming to minimize the price of anarchy (PoA) of the induced games. Recent work introduced the class of resource-aware cost-sharing mechanisms, whose decisions can depend on the set of machines in the system, but are oblivious to the total number of users. These mechanisms can guarantee low PoA bounds for instances where the cost functions of the machines are all convex or concave, but can suffer from very high PoA for cost functions that deviate from these families.

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.

In a market with repeated sales of a single item to a single buyer, prior work has established the existence of a zero revenue perfect Bayesian equilibrium in the absence of a commitment device for the seller. This counter-intuitive outcome is the result of strategic purchasing decisions, where the buyer worries that the seller will update future prices in response to past purchasing behavior. We first show that in fact almost any revenue can be achieved in equilibrium, but the zero revenue equilibrium uniquely survives natural refinements. This establishes that single buyer markets without commitment are subject to market failure. However, our main result shows that this market failure depends crucially on the assumption of a single buyer. If there are multiple buyers, the seller can approximate the revenue that is possible with commitment. We construct an intuitive equilibrium for multiple buyers that survives our refinements, in which the seller learns from past purchasing behavior and obtains a constant factor of the per-round Myerson optimal revenue. The seller's pricing policy has a natural explore-exploit structure, where the seller starts with low prices that gradually ascend to learn buyers' values, and in later rounds exploits the surviving high-valued buyers. The result resembles an ascending-price auction, implemented over time. This relates to the intuition from the Coase conjecture in the durable goods literature [Coase 1972] which states that in the absence of commitment, one should expect the VCG outcome (which, for multiple buyers, yields non-trivial revenue for the seller).

Individuals working towards a goal often exhibit time inconsistent behavior, making plans and then failing to follow through. One well-known model of such behavioral anomalies is present-bias discounting: individuals over-weight present costs by a bias factor. This model explains many time-inconsistent behaviors, but can make stark predictions in many settings: individuals either follow the most efficient plan for reaching their goal or procrastinate indefinitely. We propose a modification in which the present-bias parameter can vary over time, drawn independently each step from a fixed distribution. Following Kleinberg and Oren (2014), we use a weighted {\it task graph} to model task planning, and measure the cost of procrastination as the relative expected cost of the chosen path versus the optimal path. We use a novel connection to optimal pricing theory to describe the structure of the worst-case task graph for any present-bias distribution. We then leverage this structure to derive conditions on the bias distribution under which the worst-case ratio is exponential (in time) or constant. We also examine conditions on the task graph that lead to improved procrastination ratios: graphs with a uniformly bounded distance to the goal, and graphs in which the distance to the goal monotonically decreases on any path.

For selling a single item to agents with independent but non-identically distributed values, the revenue optimal auction is complex. With respect to it, Hartline and Rough garden showed that the approximation factor of the second-price auction with an anonymous reserve is between two and four. We consider the more demanding problem of approximating the revenue of the ex ante relaxation of the auction problem by posting an anonymous price (while supplies last) and prove that their worst-case ratio is e. As a corollary, the upper-bound of anonymous pricing or anonymous reserves versus the optimal auction improves from four to e. We conclude that, up to an e factor, discrimination and simultaneity are unimportant for driving revenue in single-item auctions.