We initiate the study of multidimensional Bayesian utility maximization, focusing on the unit-demand setting where values are i.i.d. across both items and buyers. The seminal result of Hartline and Roughgarden '08 studies simple, information-robust mechanisms that maximize utility for $n$ i.i.d. agents and $m$ identical items via an approximation to social welfare as an upper bound, and they prove this gap between optimal utility and social welfare is $\Theta(1+\log{n/m})$ in this setting. We extend these results to the multidimensional setting. To do so, we develop simple, prior-independent, approximately-optimal mechanisms, targeting the simplest benchmark of optimal welfare. We give a $(1-1/e)$-approximation when there are more items than buyers, and a $\Theta(\log{n/m})$-approximation when there are more buyers than items, and we prove that this bound is tight in both $n$ and $m$ by reducing the i.i.d. unit-demand setting to the identical items setting. Finally, we include an extensive discussion section on why Bayesian utility maximization is a promising research direction. In particular, we characterize complexities in this setting that defy our intuition from the welfare and revenue literature, and motivate why coming up with a better benchmark than welfare is a hard problem itself.

Welfare maximization in bilateral trade has been extensively studied in recent years. Previous literature obtained incentive-compatible approximation mechanisms only for the private values case. In this paper, we study welfare maximization in bilateral trade with interdependent values. Designing mechanisms for interdependent settings is much more challenging because the values of the players depend on the private information of the others, requiring complex belief updates and strategic inference.

The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $s_{1}, \ldots, s_{n}$ of the n bidders and public valuation functions $v_{i}\left(s_{1}, \ldots, s_{n}\right)$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and private valuations, and established $O\left(\log ^{2} n\right)$-approximation for SOS valuations. In this paper we show that this setting admits a constant factor approximation, settling the open question raised by Eden et al. (2022).

We consider the single-item interdependent value setting, where there is a single item sold by a monopolist, n buyers, and each buyer has a private signal si describing a piece of information about the item. Additionally, each bidder i has a valuation function vi(s1, …, sn) mapping the (private) signals of all buyers into a positive real number representing their value for the item. This setting captures scenarios where the item's information is asymmetric or dispersed among agents, such as in competitions for oil drilling rights, or in auctions for art pieces. Due to the increased complexity of this model compared to the standard private values model, it is generally assumed that each bidder's valuation function vi is public knowledge to the seller or all other buyers. But in many situations, the seller may not know the bidders' valuation functions—how a bidder aggregates signals into a valuation is often their private information. In this paper, we design mechanisms that guarantee approximately-optimal social welfare while satisfying ex-post incentive compatibility and individually rationality for the case where the valuation functions are private to the bidders, and thus may be strategically misreported to the seller. When the valuations are public, it is possible for optimal social welfare to be attained by a deterministic mechanism when the valuations satisfy a single-crossing condition. In contrast, when the valuations are the bidders' private information, we show that no finite bound on the social welfare can be achieved by any deterministic mechanism even under single-crossing. Moreover, no randomized mechanism can guarantee better than n-approximation. We thus consider valuation functions that are submodular over signals (SOS), introduced in the context of combinatorial auctions in a recent breakthrough paper by Eden et al. [EC'19]. Our main result is an O(log2 n)-approximation randomized mechanism for buyers with private signals and valuations under the SOS condition. We also give a tight Θ(k)-approximation mechanism for the case each agent's valuation depends on at most k other signals even for unknown k.

We study gains from trade in multi-dimensional two-sided markets. Specifically, we focus on a setting with n heterogeneous items, where each item is owned by a different seller i, and there is a constrained-additive buyer with feasibility constraint ℱ. Multi-dimensional settings in one-sided markets, e.g. where a seller owns multiple heterogeneous items but also is the mechanism designer, are well-understood. In addition, single-dimensional settings in two-sided markets, e.g. where a buyer and seller each seek or own a single item, are also well-understood. Multi-dimensional two-sided markets, however, encapsulate the major challenges of both lines of work: optimizing the sale of heterogeneous items, ensuring incentive-compatibility among both sides of the market, and enforcing budget balance. We present, to the best of our knowledge, the first worst-case approximation guarantee for gains from trade in a multi-dimensional two-sided market. Our first result provides an O(log(1/r))-approximation to the first-best gains from trade for a broad class of downward-closed feasibility constraints (such as matroid, matching, knapsack, or the intersection of these). Here r is the minimum probability over all items that a buyer's value for the item exceeds the seller's cost. Our second result removes the dependence on r and provides an unconditional O(log n)-approximation to the second-best gains from trade. We extend both results for a general constrained-additive buyer, losing another O(log n)-factor en-route. The first result is achieved using a fixed posted price mechanism, and the analysis involves a novel application of the prophet inequality or a new concentration inequality. Our second result follows from a stitching lemma that allows us to upper bound the second-best gains from trade by the first-best gains from trade from the “likely to trade” items (items with trade probability at least 1/n) and the optimal profit from selling the “unlikely to trade” items. We can obtain an O(log n)-approximation to the first term by invoking our O(log(1/r))-approximation on the “likely to trade” items. We introduce a generalization of the fixed posted price mechanism—seller adjusted posted price—to obtain an O(log n)-approximation to the optimal profit for the “unlikely to trade” items. Unlike fixed posted price mechanisms, not all seller adjusted posted price mechanisms are incentive compatible and budget balanced. We develop a new argument based on “allocation coupling” to show the seller adjusted posted price mechanism used in our approximation is indeed budget balanced and incentive-compatible.

We study auctions for carbon licenses, a policy tool used to control the social cost of pollution. Each identical license grants the right to produce a unit of pollution. Each buyer (i.e., firm that pollutes during the manufacturing process) enjoys a decreasing marginal value for licenses, but society suffers an increasing marginal cost for each license distributed. The seller (i.e., the government) can choose a number of licenses to put up for auction, and wishes to maximize the societal welfare: the total economic value of the buyers minus the social cost. Motivated by emission license markets deployed in practice, we focus on uniform price auctions with a price floor and/or price ceiling. The seller has distributional information about the market, and their goal is to tune the auction parameters to maximize expected welfare. The target benchmark is the maximum expected welfare achievable by any such auction under truth-telling behavior. Unfortunately, the uniform price auction is not truthful, and strategic behavior can significantly reduce (even below zero) the welfare of a given auction configuration. We describe a subclass of "safe-price" auctions for which the welfare at any Bayes-Nash equilibrium will approximate the welfare under truth-telling behavior. We then show that the better of a safe-price auction, or a truthful auction that allocates licenses to only a single buyer, will approximate the target benchmark. In particular, we show how to choose a number of licenses and a price floor so that the worst-case welfare, at any equilibrium, is a constant approximation to the best achievable welfare under truth-telling after excluding the welfare contribution of a single buyer.

We consider optimal (revenue maximizing) mechanism design in the interdimensional setting, where one dimension is the 'value' of the buyer, and the other is a 'type' that captures some auxiliary information. A prototypical example of this is the FedEx Problem, for which Fiat et al. [2016] characterize the optimal mechanism for a single agent. Another example of this is when the type encodes the buyer's budget [DW17]. The question we address is how far can such characterizations goIn particular, we consider the setting of single-minded agents. A seller has heterogenous items. A buyer has a valuation vfor a specific subset of items S, and obtains value vif and only if he gets all the items in S(and potentially some others too).

We consider the problem of welfare (and gains-from-trade) maximization in two-sided markets using simple mechanisms that are prior-independent. The seminal impossibility result of Myerson and Satterthwaite [1983] shows that even for bilateral trade, there is no feasible (individually rational, truthful, and budget balanced) mechanism that has welfare as high as the optimal-yet-infeasible VCG mechanism, which attains maximal welfare but runs a deficit. On the other hand, the optimal feasible mechanism needs to be carefully tailored to the Bayesian prior, and even worse, it is known to be extremely complex, eluding a precise description. In this paper we present Bulow-Klemperer-style results to circumvent these hurdles in double-auction market settings. We suggest using the Buyer Trade Reduction (BTR) mechanism, a variant of McAfee's mechanism, which is feasible and simple (in particular, it is deterministic, truthful, prior-independent, and anonymous). First, in the setting in which the values of the buyers and of the sellers are sampled independently and identically from the same distribution, we show that for any such market of any size, BTR with one additional buyer whose value is sampled from the same distribution has expected welfare at least as high as the optimal-yet-infeasible VCG mechanism in the original market. We then move to a more general setting in which the values of the buyers are sampled from one distribution, and those of the sellers from another, focusing on the case where the buyers' distribution first-order stochastically dominates the sellers' distribution. We present both upper bounds and lower bounds on the number of buyers that, when added, guarantees that BTR in the augmented market achieve welfare at least as high as the optimal in the original market. Our lower bounds extend to a large class of mechanisms, and all of our positive and negative results extend to adding sellers instead of buyers. In addition, we present positive results about the usefulness of pricing at a sample for welfare maximization (and more precisely, for gains-from-trade approximation) in two-sided markets under the above two settings, which to the best of our knowledge are the first sampling results in this context.

We consider a setting where an auctioneer sells a single item to n potential agents with interdependent values. That is, each agent has her own private signal, and the valuation of each agent is a known function of all n private signals. This captures settings such as valuations for oil drilling rights, broadcast rights, pieces of art, and many more.

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.

Consider the pricing problem faced by FedEx. Each customer has a package to ship, a deadline $d$ by which he needs his package to arrive, and a value $v$ for a guarantee that the package will arrive by his deadline. FedEx can (and does) offer a number of different shipping options in order to extract more revenue from their customers. In this paper, we solve the optimal (revenue-maximizing) auction problem for the single-agent version of this problem. Our paper adds to the relatively short list of multi-parameter settings for which a closed-form solution is known.