In this work, we introduce and study contextual search in general principal-agent games, where a principal repeatedly interacts with agents by offering contracts based on contextual information and historical feedback, without knowing the agents’ true costs or rewards. Our model generalizes classical contextual pricing by accommodating richer agent action spaces. Over \(T\) rounds with \(d\)-dimensional contexts, we establish an asymptotically tight exponential \(T^{1-\Theta(1/d)}\) bound in terms of the pessimistic Stackelberg regret, benchmarked against the best utility for the principal that is consistent with the observed feedback.

We introduce and study the persuasive calibration problem, where a principal aims to provide trustworthy predictions about underlying events to a downstream agent to make desired decisions. We adopt the standard calibration framework that regulates predictions to be unbiased conditional on their own value, and thus, they can reliably be interpreted at face value by the agent. Allowing a small calibration error budget, we aim to answer the following question: what the optimal predictor is and how to compute it under this calibration error budget, especially when there exists incentive misalignment between the principal and the agent? We focus on the standard \(\ell_t\)-norm Expected Calibration Error (ECE) metric.

A large proportion of the Bayesian mechanism design literature is restricted to the family of regular distributions $\mathbb{F}_{\text {reg }}$ [Mye81] or the family of monotone hazard rate (MHR) distributions $\mathbb{F}_{M H R}$ [BMP63], which has overshadowed this rich and well-developed theory. We (re-)introduce two generalized families: quasi-regular distributions $\mathbb{F}_{Q-r e g}$ and quasi-MHR distributions $\mathbb{F}_{Q-M H R}$. Altogether, these four families form the following hierarchy: $\mathbb{F}_{\mathrm{MHR}} \subsetneq\left(\mathbb{F}_{\mathrm{reg}} \cap \mathbb{F}_{Q-\mathrm{MHR}}\right) \subsetneq \mathbb{F}_{\mathrm{reg}}, \mathbb{F}_{Q-\mathrm{MHR}} \subsetneq\left(\mathbb{F}_{\mathrm{reg}} \cup \mathbb{F}_{Q-\mathrm{MHR}}\right) \subsetneq \mathbb{F}_{Q-\mathrm{reg}}$ Likewise, the parameterized families of $\lambda$-regular (a.k.a. $\alpha$ strongly regular) distributions [CR14], [SS19], which smoothly interpolate $\mathbb{F}_{\text {reg }}$ and $\mathbb{F}_{\text {MHR }}$, generalize to $\lambda$-quasi-regular distributions. The significance of our new families is manifold. Firstly, their defining conditions are immediate “economic” relaxations of the original defining conditions (e.g., regularity as monotonicity of the virtual value functions), capturing key economic intuitions. Secondly, they satisfy natural mathematical properties (about order statistics) failed for the original families, thus technically more tractable. Thirdly, numerous results (by [BK96], [HR09a], [CD15], [DRY15], [HR14], [AHN ${ }^{+}$19], [JLTX20], [JLQ ${ }^{+}$19b], [FLR19], [GHZ19b], [JLX23], [LM24] etc) known merely for the original families now can extend to our new families. Many of these extensions incur no quantitative loss, or even improve the state of the art for the original families. Finally, beyond the third point, our new families guide us to entirely new perspectives and thus entirely unknown results. For example, regarding revenue maximization for symmetric versus asymmetric regular buyers, we acquire $\frac{1}{2}$ - versus 0.1908 -approximations for the (less-than-)one-sample prophet inequalities, respectively. To the best of our knowledge, such results are blank in the literature, despite their widely-studied welfare maximization counterparts [CDFS22], [RWW20], [CCES20], [CDF ${ }^{+}$21], [CCES24].

We consider the impact of fairness requirements on the social efficiency of truthful mechanisms for trade, focusing on Bayesian bilateral-trade settings. Unlike the full information case in which all gains-from-trade can be realized and equally split between the two parties, in the private information setting, equitability has devastating welfare implications (even if only required to hold ex-ante). We thus search for an alternative fairness notion and suggest requiring the mechanism to be KS-fair: it must ex-ante equalize the fraction of the ideal utilities of the two traders. We show that there is always a KS-fair (simple) truthful mechanism with expected gains-from-trade that are half the optimum, but always ensuring any better fraction is impossible (even when the seller value is zero). We then restrict our attention to trade settings with a zero-value seller and a buyer with valuation distribution that is Regular or MHR, proving that much better fractions can be obtained under these conditions, with simple posted-price mechanisms.

We quantify the value of the monopoly's bargaining power in terms of competition complexity—that is, the number of additional bidders the monopoly must attract in simple auctions to match the expected revenue of the optimal mechanisms —within the setting of multi-item auctions. We show that for simple auctions that sell items separately, the competition complexity is Θ(n/α) in an environment with n original bidders under the slightly stronger assumption of α-strong regularity, in contrast to the standard regularity assumption in the literature, which requires Ω (n · ln m/n) additional bidders. This significantly reduces the value of learning the distribution to design the optimal mechanisms, especially in large markets with many items for sale. For simple auctions that sell items as a grand bundle, we establish a constant competition complexity bound in a single-bidder environment when the number of items is small or when the value distribution has a monotone hazard rate. Some of our competition complexity results also hold when we compete against the first best benchmark (i.e., optimal social welfare).

Motivated by the challenges in last-mile delivery operations, we consider a natural dynamic staffing problem in which a decision-maker sequentially hires staff over a finite time horizon to meet an unknown target demand at the end. The decision-maker also receives a sequence of predictions about the demand that become increasingly more accurate over time. Consequently, the decision-maker prefers to delay hiring decisions to avoid overstaffing. However, workers' availability decreases over time, resulting in a fundamental trade-off between securing staff early (thus risking overstaffing) versus hiring later based on more accurate predictions (but risking understaffing).

Individual mobility patterns have a first-order impact on many operational decisions, ranging from facility location decisions to the optimization of transit systems. In the past, obtaining data on individual mobility patterns was a challenging task. However, in recent years, such data have been extensively collected via mobile phones. Moreover, various data providers have made these data available at scale, enabling decision makers to leverage them for large-scale analysis.

Classic mechanism/information design imposes the assumption that agents are fully rational, meaning each of them always selects the action that maximizes her expected utility. Yet many empirical evidence suggests that human decisions may deviate from this full rationality assumption. In this work, we attempt to relax the full rationality assumption with bounded rationality. Specifically, we formulate the bounded rationality of an agent by adopting the quantal response model (McKelvey and Palfrey, 1995).

We study a game played between advertisers in an online ad platform. The platform sells ad impressions by first-price auction and provides autobidding algorithms that optimize bids on each advertiser's behalf, subject to advertiser constraints such as budgets. Crucially, these constraints are strategically chosen by the advertisers. The chosen constraints define an "inner" budget-pacing game for the autobidders. Advertiser payoffs in the constraint-choosing "metagame" are determined by the equilibrium reached by the autobidders. Advertiser preferences can be more general than what is implied by their constraints: we assume only that they have weakly decreasing marginal value for clicks and weakly increasing marginal disutility for spending money. Nevertheless, we show that at any pure Nash equilibrium of the metagame, the resulting allocation obtains at least half of the liquid welfare of any allocation and this bound is tight. We also obtain a 4-approximation for any mixed Nash equilibrium or Bayes-Nash equilibria. These results rely on the power to declare budgets: if advertisers can specify only a (linear) value per click or an ROI target but not a budget constraint, the approximation factor at equilibrium can be as bad as linear in the number of advertisers.

We consider a novel dynamic pricing and learning setting where in addition to setting prices of products in sequential rounds, the seller also ex-ante commits to ‘advertising schemes’. That is, in the beginning of each round the seller can decide what kind of signal they will provide to the buyer about the product’s quality upon realization. Using the popular Bayesian persuasion framework to model the effect of these signals on the buyers’ valuation and purchase responses, we formulate the problem of finding an optimal design of the advertising scheme along with a pricing scheme that maximizes the seller’s expected revenue. Without any apriori knowledge of the buyers’ demand function, our goal is to design an online algorithm that can use past purchase responses to adaptively learn the optimal pricing and advertising strategy. We study the regret of the algorithm when compared to the optimal clairvoyant price and advertising scheme. Our main result is a computationally efficient online algorithm that achieves an $O(T^{2/3}(m \log T )^{1/3})$ regret bound when the valuation function is linear in the product quality. Here $m$ is the cardinality of the discrete product quality domain and $T$ is the time horizon. This result requires some natural monotonicity and Lipschitz assumptions on the valuation function, but no Lipschitz or smoothness assumption on the buyers’ demand function. For constant $m$, our result matches the regret lower bound for dynamic pricing within logarithmic factors, which is a special case of our problem. We also obtain several improved results for the widely considered special case of additive valuations, including an $\tilde{O}(T^{2/3})$ regret bound independent of $m$ when $m\le T^{1/3}$.

Motivated by applications in cloud computing spot markets and selling banner ads on popular websites, we study the online resource allocation problem with costly buyback. To model this problem, we consider the classic edge-weighted fractional online matching problem with a tweak, where the decision maker can recall (i.e., buyback) any fraction of an offline resource that is pre-allocated to an earlier online vertex; however, by doing so not only the decision maker loses the previously allocated reward (which equates the edge-weight), it also has to pay a non-negative constant factor f of this edge-weight as an extra penalty. Parameterizing the problem by the buyback factor f, our main result is obtaining optimal competitive algorithms for all possible values of f through a novel primal-dual family of algorithms. We establish the optimality of our results by obtaining separate lower-bounds for each of small and large buyback factor regimes, and showing how our primal-dual algorithm exactly matches this lower-bound by appropriately tuning a parameter as a function of f. The optimal competitive ratio Γgen(f) and the optimal competitive ratio Γdet-int(f) of deterministic integral algorithms are as follows,

We study a natural competitive-information-design variant for the Pandora's Box problem [31], where each box is associated with a strategic information sender who can design what information about the box's prize value to be revealed to the agent when she inspects the box. This variant with strategic boxes is motivated by a wide range of real-world economic applications for Pandora's box. The main contributions of this article are two-fold: (1) we study informational properties of Pandora's Box by analyzing how a box's partial information revelation affects the search agent's optimal decisions; and (2) we fully characterize the pure symmetric equilibrium for the boxes' competitive information revelation, which reveals various insights regarding information competition and the resultant agent utility at equilibrium.

We show that economic conclusions derived from Bulow and Roberts (1989) for linear utility models approximately extend to non-linear utility models. Specifically, we quantify the extent to which agents with non-linear utilities resemble agents with linear utilities, and we show that the approximation of mechanisms for agents with linear utilities approximately extend for agents with non-linear utilities. We illustrate the framework for the objectives of revenue and welfare on non-linear models that include agents with budget constraints, agents with risk aversion, and agents with endogenous valuations. We derive bounds on how much these models resemble the linear utility model and combine these bounds with well-studied approximation results for linear utility models. We conclude that simple mechanisms are approximately optimal for these non-linear agent models. * The full version of the paper can be accessed at https://arxiv.org/abs/2003.00545. This work is support by NSF CCF AF #1618502.

Firms engaged in electronic commerce increasingly rely on predictive analytics via machine-learning algorithms to drive a wide array of managerial decisions. The tuning of many standard machine learning algorithms can be understood as trading off bias (i.e., accuracy) with variance (i.e., precision) in the algorithm's predictions. The goal of this paper is to understand how competition between firms affects their strategic choice of such algorithms. To this end, we model the interaction of two firms choosing learning algorithms as a game and analyze its equilibria. Absent competition, players care only about the magnitude of predictive error and not its source. In contrast, our main result is that with competition, players prefer to incur error due to variance rather than due to bias, even at the cost of higher total error. In addition, we show that competition can have counterintuitive implications---for example, reducing the error incurred by a firm's algorithm can be harmful to that firm---but we provide conditions under which such phenomena do not occur. In addition to our theoretical analysis, we also validate our insights by applying our metrics to a publicly available data set.

Motivated by the applications of rental services in e-commerce, we consider revenue maximization in online assortment of reusable resources for a stream of arriving consumers with different types. We design competitive online algorithms with respect to the optimum online policy in the Bayesian setting, in which types are drawn independently from known heterogeneous distributions over time. In the regime where the minimum of initial inventories c_min is large, our main result is a near-optimal 1-min(1/2,√log(cmin)/cmin) competitive algorithm for the general case of reusable resources. Our algorithm relies on an expected LP benchmark for the problem, solves this LP, and simulates the solution through an independent randomized rounding. The main challenge is obtaining point-wise inventory feasibility in a computationally efficient fashion from these simulation-based algorithms. To this end, we use several technical ingredients to design discarding policies - one for each resource. These policies handle the trade-off between the inventory feasibility under reusability and the revenue loss of each of the resources. However, discarding a unit of a resource changes the future consumption of other resources. To handle this new challenge, we also introduce post-processing assortment procedures that help with designing and analyzing our discarding policies as they run in parallel, which might be of independent interest. We finally evaluate the performance of our algorithms using the numerical simulations on synthetic data.

We introduce and study the online Bayesian recommendation problem for a platform, who can observe a utility-relevant state of a product, repeatedly interacting with a population of myopic users through an online recommendation mechanism. This paradigm is common in a wide range of scenarios in the current Internet economy. For each user with her own private preference and belief, the platform commits to a recommendation strategy to utilize his information advantage on the product state to persuade the self-interested user to follow the recommendation. The platform does not know user's preferences and beliefs, and has to use an adaptive recommendation strategy to persuade with gradually learning user's preferences and beliefs in the process.

In several applications of real-time matching of demand to supply in online marketplaces, the platform can allow for some latency to batch the demand and improve the matching’s efficiency. Motivated by these scenarios, we study the optimal trade-off between batching and inefficiency in online allocations. In particular, we consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems, where online vertices arrive in K batches. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive (fractional) matching algorithm, improving the classic (1-1/e) competitive ratios known for the online variant of these problems [Mehta et al., 2007; Aggarwal et al., 2011]. Our main technique is using a family of convex-programming based matchings that distribute the demand in a particularly balanced way among supply in different stages. More precisely, we identify a sequence of polynomials with decreasing degrees that can be used as strictly concave regularizers of the optimal matching linear program to form this family. By providing structural decompositions of the underlying graph using the optimal solutions of these convex programs, we develop a new multi-stage primal-dual framework to analyze the fractional multi-stage algorithm that returns the corresponding regularized optimal matching in each stage (by solving the stage’s convex program). We further show a matching upper-bound by providing an unweighted instance of the problem in which no online algorithm obtains a competitive ratio better than (1-(1-1/K)^K). We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios.

We study a two-stage stochastic matching problem motivated in part by applications in online marketplaces used for ride hailing. Using a randomized primal-dual algorithm applied to a family of “balancing” convex programs, we obtain the optimal 3/4 competitive ratio against the optimum offline benchmark. These balancing convex programs offer a natural generalization of the matching skeleton by Goel et al. (2012) and may be of independent interest. Switching to the more precise benchmark of optimum online, we exploit connections to submodular optimization and use a factor-revealing program to improve the 3/4 ratio to (1 – 1/e + 1/e2) ≈ 0.767 for the unweighted and 0.761 for the weighted case. We also show it is NP-hard to obtain an FPTAS with respect to this benchmark.

This paper considers prior-independent mechanism design, in which a single mechanism is designed to achieve approximately optimal performance on every prior distribution from a given class. Most results in this literature focus on mechanisms with truthtelling equilibria, a.k.a., truthful mechanisms. Feng and Hartline [FOCS 2018] introduce the revelation gap to quantify the loss of the restriction to truthful mechanisms. We solve a main open question left in Feng and Hartline [FOCS 2018]; namely, we identify a non-trivial revelation gap for revenue maximization.

Discrete choice models with unobserved heterogeneity are commonly used Econometric models for dynamic Economic behavior which have been adopted in practice to predict behavior of individuals and firms from schooling and job choices to strategic decisions in market competition. These models feature optimizing agents who choose among a finite set of options in a sequence of periods and receive choice-specific payoffs that depend on both variables that are observed by the agent and recorded in the data and variables that are only observed by the agent but not recorded in the data. Existing work in Econometrics assumes that optimizing agents are fully rational and requires finding a functional fixed point to find the optimal policy. We show that in an important class of discrete choice models the value function is globally concave in the policy. That means that simple algorithms that do not require fixed point computation, such as the policy gradient algorithm, globally converge to the optimal policy. This finding can both be used to relax behavioral assumption regarding the optimizing agents and to facilitate Econometric analysis of dynamic behavior. In particular, we demonstrate significant computational advantages in using a simple implementation policy gradient algorithm over existing “nested fixed point” algorithms used in Econometrics.

This paper considers prior-independent mechanism design, namely identifying a single mechanism that has near optimal performance on every prior distribution. We show that mechanisms with truthtelling equilibria, a.k.a., revelation mechanisms, do not always give optimal prior-independent mechanisms and we define the revelation gap to quantify the non-optimality of revelation mechanisms. This study suggests that it is important to develop a theory for the design of non-revelation mechanisms. Our analysis focuses on welfare maximization by single-item auctions for agents with budgets and a natural regularity assumption on their distribution of values. The all-pay auction (a non-revelation mechanism) is the Bayesian optimal mechanism; as it is prior-independent it is also the prior-independent optimal mechanism (a 1-approximation). We prove a lower bound on the prior-independent approximation of revelation mechanisms of 1.013 and that the clinching auction (a revelation mechanism) is a prior-independent e ≈ 2.714 approximation. Thus the revelation gap for single-item welfare maximization with public budget agents is in [1.013, e]. Some of our analyses extend to the revenue objective, position environments, and irregular distributions.