Search

Economic theory distinguishes between principal-agent settings in which the agent has a private type and settings in which the agent takes a hidden action. Many practical problems, however, involve aspects of both. For example, brand X may seek to hire an influencer Y to create sponsored content to be posted on social media platform Z. This problem has a hidden action component (the brand may not be able or willing to observe the amount of effort exerted by the influencer), but also a private type component (influencers may have different costs per unit-of-effort). This "effort" and "cost per unit-of-effort" perspective naturally leads to a principal-agent problem with hidden action and single-dimensional private type, which generalizes both the classic principal-agent hidden action model of contract theory à la Grossmann and Hart [1986] and the (procurement version) of single-dimensional mechanism design à la Myerson [1983]. A natural goal in this model is to design an incentive-compatible contract, which consist of an allocation rule that maps types to actions, and a payment rule that maps types to payments for the stochastic outcomes of the chosen action. Our main contribution is an LP-duality based characterization of implementable allocation rules for this model, which applies to both discrete and continuous types. This characterization shares important features of Myerson's celebrated characterization result, but also departs from it in significant ways. We present several applications, including a polynomial-time algorithm for finding the optimal contract with a constant number of actions. This in sharp contrast to recent work on hidden action problems with multi-dimensional private information, which has shown that the problem of computing an optimal contract for constant numbers of actions is APX-hard. [ABSTRACT FROM AUTHOR]

We study a generalization of both the classic single-dimensional mechanism design problem, and the hidden-action principal-agent problem of contract theory [c.f., Alon et al. 2021]. In this setting, the principal seeks to incentivize an agent with a private Bayesian type to take a costly action. The goal is to design an incentive compatible menu of contracts which maximizes the expected revenue. [ABSTRACT FROM AUTHOR]

We study a setting with a decision maker making a binary decision by aggregating information from symmetric agents. Each agent provides the decision maker a recommendation depending on her private signal about the hidden state. We assume that agents are truthful - an agent recommends guessing the more likely state based on her information. This assumption is natural if the agents are unaware of how the decision-maker will aggregate their recommendations. While the decision maker has a prior distribution over the hidden state and knows the marginal distribution of each agent's private signal, the correlation between these signals is chosen adversarially. The decision maker's goal is choosing an information aggregation rule that is robustly optimal. [ABSTRACT FROM AUTHOR]

Understanding when equilibria are guaranteed to exist is a central theme in economic theory, seemingly unrelated to computation. This paper shows that the existence of pricing equilibria is inextricably connected to the computational complexity of related optimization problems: demand oracles, revenue-maximization, and welfare-maximization. This relationship implies, under suitable complexity assumptions, a host of impossibility results. We also suggest a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept: such extensions seem to require the invention of novel polynomial-time algorithms for welfare-maximization. [ABSTRACT FROM AUTHOR]

Designing double auctions is a complex problem, especially when there are restrictions on the sets of buyers and sellers that may trade with one another. The goal of this paper is to develop “black-box reductions” from double-auction design to the exhaustively-studied problem of designing single-sided mechanisms. We consider several desirable properties of a double auction: feasibility, dominant-strategy incentivecompability, the still stronger incentive constraints offered by a deferred-acceptance implementation, exact and approximate welfare maximization, and budget-balance. For each of these properties, we identify sufficient conditions on the two one-sided mechanisms — one for the buyers, one for the sellers — and on the method of composition, that guarantee the desired property of the double auction. Our framework also offers new insights into classic double-auction designs, such as the VCG and McAfee auctions with unit-demand buyers and unit-supply sellers. [ABSTRACT FROM AUTHOR]

The article presents a study which investigates the use of optimal and near-optimal mechanism design in generalizing the standard setting of interdependent and private values. Topics discussed include application of Myerson's optimal auction theory in evaluating many interdependent settings, the characterization of ex post incentive compatible (IC) and individually rational (IR) mechanisms, and the use of mechanism design theory in defining the rules of the game being played by bidders.

Most results in revenue-maximizing auction design hinge on "getting the price right" - offering goods to bidders at a price low enough to encourage a sale, but high enough to garner non-trivial revenue. Getting the price right can be hard work, especially when the seller has little or no a priori information about bidders' valuations. A simple alternative approach is to "let the market do the work", and have prices emerge from competition for scarce goods. The simplest-imaginable implementation of this idea is the following: first, if necessary, impose an artificial limit on the number of goods that can be sold; second, run the welfare-maximizing VCG mechanism subject to this limit. We prove that such "supply-limiting mechanisms" achieve near-optimal expected revenue in a range of single- and multi-parameter Bayesian settings. Indeed, despite their simplicity, we prove that they essen- tially match the state-of-the-art in prior-independent mechanism design. [ABSTRACT FROM AUTHOR]

We study robust mechanism design for revenue maximization when selling a single item in an auction, assuming that only the mean of the value distribution and an upper bound on the bidders' valuations for the item are known. Robust mechanism design is a rising alternative to Bayesian mechanism design, which yields designs that do not rely on assumptions like full distributional knowledge, but rather only partial knowledge of the distributions. We seek a mechanism that maximizes revenue over the worst-case distribution compatible with the known parameters. Such a mechanism arises as an equilibrium of a zero-sum game between the seller and an adversary who chooses the distribution, and so can be referred to as the max-min mechanism. Carrasco et al. [2018] derive the max-min pricing when the seller faces a single bidder for the item. We go from max-min pricing to max-min auctions by studying the canonical setting of two i.i.d. bidders, and show the max-min mechanism is the second-price auction with a randomized reserve. We derive a closed-form solution for the distribution over reserve prices, as well as the worst-case value distribution, for which there is simple economic intuition. We also derive a closed-form solution for the max-min reserve price distribution for any number of bidders, and we show that unlike the case of two bidders, a second-price auction with a randomized reserve cannot be an equilibrium for more than two bidders. Our technique for solving the zero-sum game is quite different than that of Carrasco et al. -- we focus on a reduced zero-sum game, where the seller can only choose a distribution for a second-price auction with a randomized reserve price (rather than any mechanism). We then analyze a discretized version of the setting to find conditions an equilibrium would satisfy. By refining the discretization grid, we are able to achieve differential equations, and solving them yields closed-form non-discretized distributions. The resulting distributions for the seller and the adversary are later shown to be an equilibrium for the reduced zero-sum game. For the two-bidder case, we expand our result to an equilibrium of the original zero-sum game, where the seller is not limited to second price auctions with reserve. The full version of the paper is available at https://arxiv.org/abs/2205.09008. [ABSTRACT FROM AUTHOR]

We study contract design for welfare maximization in the well-known "common agency" model of Bernheim and Whinston [1986]. This model combines the challenges of coordinating multiple principals with the fundamental challenge of contract design: that principals have incomplete information of the agent's choice of action. Motivated by the significant social inefficiency of standard contracts for such settings (which we formally quantify using a price of anarchy/stability analysis), we investigate whether and how a recent toolbox developed for the first set of challenges under a complete-information assumption -- VCG contracts [Lavi and Shamash, 2019] -- can be extended to incomplete information. We define and characterize the class of "incomplete information VCG contracts (IIVCG)", and show it is the unique class guaranteeing truthfulness of the principals and welfare maximization by the agent. Our results reveal an inherent tradeoff between two important properties required to ensure participation in the contract: individual rationality (for the principals) and limited liability (for the agent). We design a polynomial-time algorithm for determining whether a setting has an IIVCG contract with both properties. As our main result we design a polynomial-time "algorithmic IIVCG" contract: given valuation reports from the principals it returns, if possible for the setting, a payment scheme for the agent that constitutes an IIVCG contract with all desired properties. We also give a sufficient graph-theoretic condition on the population of principals that [ABSTRACT FROM AUTHOR]

We study a Bayesian persuasion setting with binary actions (adopt and reject) for Receiver. We examine the following question -- how well can Sender perform, in terms of persuading Receiver to adopt, when ignorant of Receiver's utility? We take a robust (adversarial) approach to study this problem; that is, our goal is to design signaling schemes for Sender that perform well for all possible Receiver's utilities. We measure performance of signaling schemes via the notion of (additive) regret: the difference between Sender's hypothetically optimal utility had she known Receiver's utility function and her actual utility induced by the given scheme. On the negative side, we show that if Sender has no knowledge at all about Receiver's utility, then Sender has no signaling scheme that performs robustly well. On the positive side, we show that if Sender only knows Receiver's ordinal preferences of the states of nature -- i.e., Receiver's utility upon adoption is monotonic as a function of the state -- then Sender can guarantee a surprisingly low regret even when the number of states tends to infinity. In fact, we exactly pin down the minimum regret value that Sender can guarantee in this case, which turns out to be at most 1/e. We further show that such positive results are not possible under the alternative performance measure of a multiplicative approximation ratio by proving that no constant ratio can be guaranteed even for monotonic Receiver's utility; this may serve to demonstrate the merits of regret as a robust performance measure that is not too pessimistic. Finally, we analyze an intermediate setting in between the no-knowledge and the ordinal-knowledge settings. [ABSTRACT FROM AUTHOR]

We consider a robust version of the revenue maximization problem, where a single seller wishes to sell n items to a single unit-demand buyer. In this robust version, the seller knows the buyer's marginal value distribution for each item separately, but not the joint distribution, and prices the items to maximize revenue in the worst case over all compatible correlation structures. We devise a computationally efficient (polynomial in the support size of the marginals) algorithm that computes the worst-case joint distribution for any choice of item prices. And yet, in sharp contrast to the additive buyer case [Carroll, 2017], we show that it is NP-hard to approximate the optimal choice of prices to within any factor better than n1/2-∈. For the special case of marginal distributions that satisfy the monotone hazard rate property, we show how to guarantee a constant fraction of the optimal worst-case revenue using item pricing; this pricing equates revenue across all possible correlations and can be computed efficiently. [ABSTRACT FROM AUTHOR]