We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. We establish the existence of such an embedding for binary matroids, and use it to relate variants of the binary matroid secretary problem to each other, showing that seemingly simpler problems are in fact equivalent to seemingly harder ones (up to constant-factors). Specifically, we show this to be the case for the version of the matroid secretary problem in which the matroid is not known in advance, and where it is known in advance. We also show that the version with known matroid structure, is equivalent to the problem where weights are not fully adversarial but drawn from a known pairwise-independent distribution.

In a linear combinatorial optimization problem, we are given a family F ⊆ 2U of feasible subsets of a ground set U of n elements, and our goal is to find S* = argminS ∈ F ⟨ w,1S ⟩. Traditionally, we are either given the weight vector up-front, or else we are given a value oracle which allows us to evaluate w(S) := ⟨ w, 1S ⟩ for any S ∈ F. We consider the weaker and more robust comparison oracle, which for any two feasible sets S, T ∈ F, reveals only if w(S) is less than/equal to/greater than w(T). We ask: When can we find the optimal feasible set S* = argminS ∈ F w(S) using a small number of comparison queries? If so, when can we do this efficiently?

We consider an extension to classic position auctions in which sponsored creatives are embedded within AI-generated content rather than shown in predefined slots. Leveraging advanced LLM technologies, it becomes viable to seamlessly integrate sponsored creatives with AI content and accurately estimate the context-aware benefits of differing insertion positions. However, this approach introduces novel challenges; substitution effects require rigorous treatment compared to standard position auction settings, where slots are independent of each other.

We study the problem of minimizing swap regret in structured normal-form games. Players have a very large (potentially infinite) number of pure actions, but each action has an embedding into $d$-dimensional space and payoffs are given by bilinear functions of these embeddings. We provide an efficient learning algorithm for this setting that incurs at most $\tilde{O}(T^{(d+1)/(d+3)})$ swap regret after $T$ rounds. To achieve this, we introduce a new online learning problem we call full swap regret minimization. In this problem, a learner repeatedly takes a (randomized) action in a bounded convex $d$-dimensional action set $\mathcal{K}$ and then receives a loss from the adversary, with the goal of minimizing their regret with respect to the worst-case swap function mapping $\mathcal{K}$ to $\mathcal{K}$. For varied assumptions about the convexity and smoothness of the loss functions, we design algorithms with full swap regret bounds ranging from $O(T^{d/(d+2)})$ to $O(T^{(d+1)/(d+2)})$. Finally, we apply these tools to the problem of online forecasting to minimize calibration error, showing that several notions of calibration can be viewed as specific instances of full swap regret. In particular, we design efficient algorithms for online forecasting that guarantee at most $O(T^{1/3})$ $\ell_2$-calibration error and $O(\max(\sqrt{\epsilon T}, T^{1/3}))$ discretized-calibration error (when the forecaster is restricted to predicting multiples of $\epsilon$).

We study the problem of procurement auctions, in which an auctioneer seeks to acquire services from a group of strategic sellers with private costs. The quality of the services is measured through some submodular function that is known to the auctioneer. Our goal is to design computationally efficient procurement auctions that (approximately) maximize the difference between the quality of the acquired services and the total cost of the sellers, in a way that is incentive compatible (IC) and individual rational (IR) for the sellers, and generates non-negative surplus (NAS) for the auctioneer. Our contribution is twofold: i) we provide an improved analysis of existing algorithms for non-positive submodular function maximization and ii) we design computationally efficient frameworks that transform submodular function optimization algorithms to mechanisms that are IC and IR for the sellers, NAS for the auctioneer, and approximation-preserving. Our frameworks are general and work both in the offline setting where the auctioneer can observe the bids and the services of all the sellers simultaneously, and in the online setting where the sellers arrive in an adversarial order and the auctioneer has to make an irrevocable decision whether to purchase their service or not. We further investigate whether it is possible to convert state-of-art submodular optimization algorithms into descending auctions. We focus on the adversarial setting, meaning that the schedule of the descending prices is determined by an adversary. We show that a submodular optimization algorithm satisfying bi-criteria $(1/2,1)$-approximation in welfare can be effectively converted to a descending auction in this setting. We further establish a connection between descending auctions and online submodular optimization. Finally, we demonstrate the practical applications of our frameworks by instantiating them with different state-of-the-art submodular optimization algorithms and comparing their welfare performance through empirical experiments on publicly available datasets that consist of thousands of sellers.

We investigate auction mechanisms for AI-generated content, focusing on applications like ad creative generation. In our model, agents' preferences over stochastically generated content are encoded as large language models (LLMs). We propose an auction format that operates on a token-by-token basis, and allows LLM agents to influence content creation through single dimensional bids. We formulate two desirable incentive properties and prove their equivalence to a monotonicity condition on output aggregation. This equivalence enables a second-price rule design, even absent explicit agent valuation functions. Our design is supported by demonstrations on a publicly available LLM.

We provide an algorithm with regret $O(C d \log \log T)$ for contextual pricing with $C$ corrupted rounds, improving over the previous bound of $O(d^3 C \log^2(T))$ of Krishnamurthy et al. The result is based on a reduction that calls the uncorrupted algorithm as a black-box, unlike the previous approach that modifies the inner workings of the uncorrupted algorithm. As a result, it leads to a conceptually simpler algorithm. Finally, we provide a lower bound ruling out a $O(C + d\log \log T)$ algorithm. This shows that robustifying contextual pricing is harder than robustifying contextual search with $\epsilon$-ball losses, for which it is possible to design algorithms where corruptions add only an extra additive term $C$ to the regret.

We study mechanism design when agents have private preferences and private information about a common payoff-relevant state. We show that standard message-driven mechanisms cannot implement socially efficient allocations when agents have multidimensional types, even under favorable conditions.

We study sequential procurement auctions where the sellers are provided with a ''best and final offer'' (BAFO) strategy. This strategy allows each seller i to effectively ''freeze'' their price while remaining active in the auction, and it signals to the buyer, as well as all other sellers, that seller i would reject any price lower than that. This is in contrast to prior work, e.g., on descending auctions, where the options provided to each seller are to either accept a price reduction or reject it and drop out. As a result, the auctions that we consider induce different extensive form games and our goal is to study the subgame perfect equilibria of these games. We focus on settings involving multiple sellers who have full information regarding each other's cost (i.e., the minimum price that they can accept) and a single buyer (the auctioneer) who has no information regarding these costs. Our main result shows that the auctions enhanced with the BAFO strategy can guarantee efficiency in every subgame perfect equilibrium, even if the buyer's valuation function is an arbitrary monotone function. This is in contrast to prior work which required that the buyer's valuation satisfies restrictive properties, like gross substitutes, to achieve efficiency. We then also briefly analyze the seller's cost in the subgame perfect equilibria of these auctions and we show that even if the auctions all return the same outcome, the cost that they induce for the buyer can vary significantly.

In this paper, we investigate the question of whether no-swap-regret dynamics have stronger convergence properties in repeated games than regular no-external-regret dynamics. We prove that in almost all symmetric zero-sum games under symmetric initializations of the agents, no-swap-regret dynamics in self-play are guaranteed to converge in a strong ``frequent-iterate'' sense to the Nash equilibrium: in all but a vanishing fraction of the rounds, the players must play a strategy profile close to a symmetric Nash equilibrium. Remarkably, relaxing any of these three constraints, i.e. by allowing either i) asymmetric initial conditions, or ii) an asymmetric game or iii) no-external regret dynamics suffices to destroy this result and lead to complex non-equilibrating or even chaotic behavior. In a dual type of result, we show that the power of no-swap-regret dynamics comes at a cost of imposing a time-asymmetry on its inputs. While no-external-regret dynamics can be completely determined by the cumulative reward vector received by each player, we show there does not exist any general no-swap-regret dynamics defined on the same state space. In fact, we prove that any no-swap-regret learning algorithm must play a time-asymmetric function over the set of previously observed rewards, ruling out any dynamics based on a symmetric function of the current set of rewards.

Online platforms that deliver ads and general recommendation systems are now integral to our daily routines. These platforms aim to maximize user engagement with their content, whether it involves ads or general recommendations. And yet, for all of their importance, researchers are still struggling to fully capture which factors drive user engagement on these platforms. Understanding these factors can not only unlock the possibility of increased revenue for the platforms, but can also help increase user satisfaction. Despite the multitude of models put forth to explain user engagement behavior, most focus on short-sighted/myopic preferences; i.e., users are assumed to make engagement decisions not caring about their prior interactions with the platform. In this paper, we take a different approach and aim to model users' evolving preferences.

It has become the default in markets such as ad auctions for participants to bid in an auction through automated bidding agents (autobidders) which adjust bids over time to satisfy return-over-spend constraints. Despite the prominence of such systems for the internet economy, their resulting dynamical behavior is still not well understood. Although one might hope that such relatively simple systems would typically converge to the equilibria of their underlying auctions, we provide a plethora of results that show the emergence of complex behavior, such as bi-stability, periodic orbits and quasi periodicity. We empirically observe how the market structure (expressed as motifs) qualitatively affects the behavior of the dynamics. We complement it with theoretical results showing that autobidding systems can simulate both linear dynamical systems as well logical boolean gates.

We investigate auction mechanisms to support the emerging format of AI-generated content. We in particular study how to aggregate several LLMs in an incentive compatible manner. In this problem, the preferences of each agent over stochastically generated contents are described/encoded as an LLM. A key motivation is to design an auction format for AI-generated ad creatives to combine inputs from different advertisers. We argue that this problem, while generally falling under the umbrella of mechanism design, has several unique features. We propose a general formalism---the token auction model---for studying this problem. A key feature of this model is that it acts on a token-by-token basis and lets LLM agents influence generated contents through single dimensional bids.

Abstract. We construct explicit combinatorial Bernoulli factories for the following class of flow-based polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and [Formula: see text]-flows. In the process, we uncover new connections to algebraic combinatorics.

We consider the problem of evaluating forecasts of binary events whose predictions are consumed by rational agents who take an action in response to a prediction, but whose utility is unknown to the forecaster. We show that optimizing forecasts for a single scoring rule (e.g., the Brier score) cannot guarantee low regret for all possible agents. In contrast, forecasts that are well-calibrated guarantee that all agents incur sublinear regret. However, calibration is not a necessary criterion here (it is possible for miscalibrated forecasts to provide good regret guarantees for all possible agents), and calibrated forecasting procedures have provably worse convergence rates than forecasting procedures targeting a single scoring rule.Motivated by this, we present a new metric for evaluating forecasts that we call U-calibration, equal to the maximal regret of the sequence of forecasts when evaluated under any bounded scoring rule. We show that sublinear U-calibration error is a necessary and sufficient condition for all agents to achieve sublinear regret guarantees. We additionally demonstrate how to compute the U-calibration error efficiently and provide an online algorithm that achieves $O(\sqrt{T})$ U-calibration error (on par with optimal rates for optimizing for a single scoring rule, and bypassing lower bounds for the traditionally calibrated learning procedures). Finally, we discuss generalizations to the multiclass prediction setting.

Myerson-regularity (or simply regularity) is a standard condition in Economics that was originally introduced by Myerson in his seminar paper on optimal auctions [Myerson, 1981]. A regular distribution is a distribution with CDF F such that the revenue curve in quantile space R(q) = q · F−1(1 − q) is concave.

The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we learn the most with the smallest amount of data? For truthful auctions, this is the sample complexity problem. For posted price auctions, we no longer have access to samples. Instead, the algorithm is allowed to choose a price pt; then for a fresh sample vt ~ D we learn the sign st = sign(pt — vt) ∈ {-1, +1}. How many pricing queries are needed to estimate a given parameter of the underlying distribution? We give tight upper and lower bounds on the number of pricing queries required to find an approximately optimal reserve price for general, regular and MHR distributions. Interestingly, for regular distributions, the pricing query and sample complexities match. But for general and MHR distributions, we show a strict separation between them. All known results on sample complexity for revenue optimization follow from a variant of using the optimal reserve price of the empirical distribution. In the pricing query complexity setting, we show that learning the entire distribution within an error of ε in Levy distance requires strictly more pricing queries than to estimate the reserve. Instead, our algorithm uses a new property we identify called relative flatness to quickly zoom into the right region of the distribution to get the optimal pricing query complexity. * The full version of the paper can be accessed at https://arxiv.org/abs/2111.03158

The design of internet advertisement systems is both an auction design problem and an information retrieval (IR) problem. As an auction, the designer needs to take the participants incentives into account. As an information retrieval problem, it needs to identify the ad that it is the most relevant to a user out of an enormous set of ad candidates. Those aspects are combined by first having an IR system narrow down the initial set of ad candidates to a manageable size followed by an auction that ranks and prices those candidates.

We study the problem of contextual search in the adversarial noise model. Let $d$ be the dimension of the problem, $T$ be the time horizon and $C$ be the total amount of noise in the system. For the $\epsilon$-ball loss, we give a tight regret bound of $O(C + d \log(1/\epsilon))$ improving over the $O(d^3 \log(1/\epsilon)) \log^2(T) + C \log(T) \log(1/\epsilon))$ bound of Krishnamurthy et al (STOC’21). For the symmetric loss, we give an efficient algorithm with regret $O(C+d \log T)$. In terms of techniques, our algorithms are a departure from previous contextual search models in the sense that they keep track of density functions over the candidate vectors instead of a knowledge set consisting of the candidate vectors consistent with the feedback obtained.

We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case of a one-round communication protocol. We define message complexity corresponding to the minimum number of interactive rounds necessary to achieve the best possible outcome. Our main result is that for bilateral trade, agents don't stop talking until they reach an efficient outcome: Either agents achieve an efficient allocation in finitely many rounds of communication; or the optimal communication protocol has infinite number of rounds. We show an important class of bilateral trade settings where efficient allocation is achievable with a small number of rounds of communication.

We analyze the optimal information design in a click-through auction with stochastic click-through rates and known valuations per click. The auctioneer takes as given the auction rule of the click-through auction, namely the generalized second-price auction. Yet, the auctioneer can design the information flow regarding the click-through rates among the bidders. We require that the information structure to be calibrated in the learning sense. With this constraint, the auction needs to rank the ads by a product of the value and a calibrated prediction of the click-through rates. The task of designing an optimal information structure is thus reduced to the task of designing an optimal calibrated prediction.

We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a hidden vector $v \in [0,1]^d$. Every round the learner is provided an adversarially chosen context $u_t \in \R^d$, submits a guess $p_t$ for the value of $\langle u_t, v\rangle$, learns whether $p_t < \langle u_t, v\rangle$, and incurs loss $\ell(\langle u_t, v\rangle, p_t)$ (for some loss function $\ell$). The learner's goal is to minimize their total loss over the course of $T$ rounds. We present an algorithm for the contextual search problem for the symmetric loss function $\ell(\theta, p) = |\theta - p|$ that achieves $O_{d}(1)$ total loss. We present a new algorithm for the dynamic pricing problem (which can be realized as a special case of the contextual search problem) that achieves $O_{d}(\log \log T)$ total loss, improving on the previous best known upper bounds of $O_{d}(\log T)$ and matching the known lower bounds (up to a polynomial dependence on $d$). Both algorithms make significant use of ideas from the field of integral geometry, most notably the notion of intrinsic volumes of a convex set. To the best of our knowledge, this is the first application of intrinsic volumes to algorithm design.

In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer’s valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer’s value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.

Product Design is an important problem in marketing research where a firm tries to learn what features of a product are more valuable to consumers. We study this problem from the viewpoint of online learning: a firm repeatedly interacts with a buyer by choosing a product configuration as well as a price and observing the buyer's purchasing decision. The goal of the firm is to maximize revenue throughout the course of $T$ rounds by learning the buyer's preferences. We study both the case of a set of discrete products and the case of a continuous set of allowable product features. In both cases we provide nearly tight upper and lower regret bounds.

We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns. We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest.

The secretary problem is probably the purest model of decision making under uncertainty. In this paper, we ask which advice we can give the algorithm to improve its success probability. We propose a general model that unifies a broad range of problems: from the classic secretary problem with no advice to the variant where the quality of a secretary is drawn from a known distribution and the algorithm learns each candidate’s quality on arrival, more modern versions of advice in the form of samples, and a machine-learning inspired model where a classifier gives us a noisy signal about whether the current secretary is the best on the market. Our main technique is a factor-revealing linear program (LP) that captures all of these problems. We use this LP formulation to gain structural insight into the optimal policy. Using tools from linear programming, we present a tight analysis of optimal algorithms for secretaries with samples, optimal algorithms when secretaries’ qualities are drawn from a known distribution, and optimal algorithms for a new noisy binary advice model.

We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (ε, δ)-smallness. Using this technique, we make progress on several outstanding problems in the area: We show that, even in the case of non-identical distributions, it is possible to achieve (arbitrarily close to) the optimal approximation ratio of β ~0.745 when the items arrive in a random order (this version is commonly known as prophet secretary) as long as we are allowed to remove a small constant number of distributions. We show that forfrequent instances (where each distribution reoccurs some number of times) and random arrival order, it is possible to achieve the optimal approximation ratio of β (improving over the previous best-known bound of 0.738). We give a new, simpler proof of Kertz's optimal approximation guarantee of β ~0.745 for prophet inequalities with i.i.d. distributions. The proof is primal-dual and simultaneously produces upper and lower bounds. Using this decomposition in combination with a novel convex programming formulation, we construct the first (in parallel work with[1]) an Efficient PTAS (EPTAS) for the Optimal Ordering problem.

Dynamic mechanism design expands the scope of allocations that can be implemented and the performance that can be attained compared to static mechanisms. Even under stringent participation constraints and restrictions on transfers, recent work demonstrated that it is possible for a designer to extract the surplus of all players as revenue when players have quasilinear utilities and the number of interactions is large. Much of the analysis has focused on excludable environments (i.e., any player can be excluded from trade without affecting the utilities of others). The mechanisms presented in the literature, however, do not extend to non-excludable environments. Two prototypical examples of such environments are: (i) public projects, where all players must have the same allocation; and (ii) non-disposable goods, where each item must be allocated to some player. We show a general mechanism that can asymptotically extract full surplus as revenue in such environments. Moreover, we provide a tight characterization for general environments, and identify necessary and sufficient conditions on the possibility of asymptotic full surplus extraction. Our characterization is based on the geometry of achievable utility sets – convex sets that delineate the expected utilities that can be implemented by static mechanisms. Our results provide a reduction from dynamic to static mechanism design: the geometry of the achievable utility set of static mechanisms determines whether it is possible to fully extract surplus in the limit.

In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in ℝd and only observes the purchasing decisions of a buyer with a fixed but unknown linear valuation over the products. The regret measures the difference between the revenue the seller could have obtained knowing the buyer valuation and what can be obtained by the learning algorithm. We give a poly-time algorithm for contextual pricing with O(d log log T + d log d) regret which matches the Ω(d log log T) lower bound up to the d log d additive factor. If we replace pricing loss by the symmetric loss, we obtain an algorithm with nearly optimal regret of O(d log d) matching the Ω(d) lower bound up to log d. These algorithms are based on a novel technique of bounding the value of the Steiner polynomial of a convex region at various scales. The Steiner polynomial is a degree d polynomial with intrinsic volumes as the coefficients. We also study a generalized version of contextual search where the hidden linear function over the Euclidean space is replaced by a hidden function f : → in a certain hypothesis class ℋ. We provide a generic algorithm with O(d2) regret where d is the covering dimension of this class. This leads in particular to a Õ(s2) regret algorithm for linear contextual search if the linear function is guaranteed to be s-sparse. Finally we also extend our results to the noisy feedback model, where each round our feedback is flipped with a fixed probability p < 1/2.

A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter p ∈ [0,1] means the algorithm does not know p, but has sample access to independent draws of a Bernoulli random variable with mean equal to p. In this paper, we study the problem of Bernoulli factories for polytopes: given Bernoulli access to a vector x∈ P for a given polytope P⊂ [0,1]n, output a randomized vertex such that the expected value of the i-th coordinate is exactly equal to xi. For example, for the special case of the perfect matching polytope, one is given Bernoulli access to the entries of a doubly stochastic matrix [xij] and asked to sample a matching such that the probability of each edge (i,j) be present in the matching is exactly equal to xij.

We combine theory and empirics to (i) show that some buyers in online advertising markets are financially constrained and (ii) demonstrate how to design auctions that take into account such financial constraints. We use data from a field experiment where reserve prices were randomized on Google’s advertising exchange (AdX). We find that, contrary to the predictions of classical auction theory, a significant set of buyers lowers their bids when reserve prices go up. We show that this behavior can be explained if we assume buyers have constraints on their minimum return on investment (ROI). We proceed to design auctions for ROI-constrained buyers. We show that optimal auctions for symmetric ROI-constrained buyers are either second-price auctions with reduced reserve prices or subsidized second-price auctions. For asymmetric buyers, the optimal auction involves a modification of virtual values. Going back to the data, we show that using ROI-aware optimal auctions can lead to large revenue gains and large welfare gains for buyers.

We study optimization with an approximate zero order oracle where there is a cost $c(\epsilon)$ associated with querying the oracle with $\epsilon$ accuracy. We consider the task of reconstructing a linear function: given a linear function $f : X \subseteq \R^d \rightarrow [-1,1]$ defined on a not-necessarily-convex set $X$, the goal is to reconstruct $\hat f$ such that $\vert{f(x) - \hat f(x)}\vert \leq \epsilon$ for all $x \in X$. We show that this can be done with cost $O(d \cdot c(\epsilon/d))$. The algorithm is based on a (poly-time computable) John-like theorem for simplices instead of ellipsoids, which may be of independent interest. This question is motivated by optimization with threshold queries, which are common in economic applications such as pricing. With threshold queries, approximating a number up to precision $\epsilon$ requires $c(\epsilon) = \log(1/\epsilon)$. For this, our algorithm has cost $O(d \log(d/\epsilon))$ which matches the $\Omega(d \log(1/\epsilon))$ lower bound up to log factors.

We study "adversarial scaling", a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the "click-through-rate" can be decomposed to a (fixed across time) arm-quality component and a non-stochastic user-relevance component (fixed across arms). Despite the relative stochasticity of our model, we demonstrate two settings where most bandit algorithms suffer. On the positive side, we show that two algorithms, one from the action elimination and one from the mirror descent family are adaptive enough to be robust to adversarial scaling. Our results shed light on the robustness of adaptive parameter selection in stochastic bandits, which may be of independent interest.

Motivated by pricing applications in online advertising, we study a variant of linear regression with a discontinuous loss function that we term Myersonian regression. In this variant, we wish to find a linear function $f : \mathbb{R}^d \rightarrow \mathbb{R}$ that well approximates a set of points $(x_i, v_i) \in \mathbb{R}^d \times [0, 1]$ in the following sense: we receive a loss of $v_i$ when $f(x_i) > v_i$ and a loss of $v_i - f(x_i)$ when $f(x_i) \leq v_i$. This arises naturally in the economic application of designing a pricing policy for differentiated items (where the loss is the gap between the performance of our policy and the optimal Myerson prices). We show that Myersonian regression is NP-hard to solve exactly and furthermore that no fully polynomial-time approximation scheme exists for Myersonian regression conditioned on the Exponential Time Hypothesis being true. In contrast to this, we demonstrate a polynomial-time approximation scheme for Myersonian regression that obtains an $\epsilon m$ additive approximation to the optimal possible revenue and can be computed in time $O(\exp(\mathrm{poly}(1/\epsilon))\poly(m, n))$. We show that this algorithm is stable and generalizes well over distributions of samples.

We consider a setting in which bidders participate in multiple auctions run by different sellers, and optimize their bids for the aggregate auction. We analyze this setting by formulating a game between sellers, where a seller’s strategy is to pick an auction to run. Our analysis aims to shed light on the recent change in the Display Ads market landscape: here, ad exchanges (sellers) were mostly running second-price auctions earlier and over time they switched to variants of the first-price auction, culminating in Google’s Ad Exchange moving to a first-price auction in 2019. Our model and results offer an explanation for why the first-price auction occurs as a natural equilibrium in such competitive markets.

We consider a firm that sells products that arrive over time to a buyer. We study this problem under a notion we call positive commitment, where the seller is allowed to make binding positive promises to the buyer about items arriving in the future, but is not allowed to commit not to make further offers to the buyer in the future. We model this problem as a dynamic game where the seller chooses a mechanism at each period subject to a sequential rationality constraint, and characterize the perfect Bayesian equilibrium of this dynamic game. We prove the equilibrium is efficient and that the seller’s revenue is a function of the buyer’s ex ante utility under a no commitment model. In particular, all goods are sold in advance to the buyer at what we call the positive commitment price.

The problem of market clearing is to set a price for an item such that quantity demanded equals quantity supplied. In this work, we cast the problem of predicting clearing prices into a learning framework and use the resulting models to perform revenue optimization in auctions and markets with contextual information. The economic intuition behind market clearing allows us to obtain fine-grained control over the aggressiveness of the resulting pricing policy, grounded in theory. To evaluate our approach, we fit a model of clearing prices over a massive dataset of bids in display ad auctions from a major ad exchange. The learned prices outperform other modeling techniques in the literature in terms of revenue and efficiency trade-offs. Because of the convex nature of the clearing loss function, the convergence rate of our method is as fast as linear regression.

We study a secretary problem which captures the task of ranking in online settings. We term this problem the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the maximum element, the algorithm is asked to assign a rank, or position, to each of the elements. The rank assigned is irrevocable and is given knowing only the pairwise comparisons with elements previously arrived. The goal is to minimize the distance of the rank produced to the true rank of the elements measured by the Kendall-Tau distance, which corresponds to the number of pairs that are inverted with respect to the true order. Our main result is a matching upper and lower bound for the secretary ranking problem. We present an algorithm that ranks n elements with only O(n^{3/2}) inversions in expectation, and show that any algorithm necessarily suffers \Omega(n^{3/2}) inversions when there are n available positions. In terms of techniques, the analysis of our algorithm draws connections to linear probing in the hashing literature, while our lower bound result relies on a general anti-concentration bound for a generic balls and bins sampling process. We also consider the case where the number of positions m can be larger than the number of secretaries n and provide an improved bound by showing a connection of this problem with random binary trees.

We study the problem of designing dynamic double auctions for two-sided markets in which a platform intermediates the trade between one seller offering independent items to multiple buyers, repeatedly over a finite horizon, when agents have private values. Motivated by online advertising and ride-hailing markets, we seek to design mechanisms satisfying the following properties: no positive transfers, i.e., the platform never asks the seller to make payments nor buyers are ever paid and periodic individual rationality, i.e., every agent should derive a non-negative utility from every trade opportunity. We provide mechanisms satisfying these requirements that are asymptotically efficient and budget-balanced with high probability as the number of trading opportunities grows. Moreover, we show that the average expected profit obtained by the platform under these mechanisms asymptotically approaches first best (the maximum possible welfare generated by the market).

We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems in contextual decision-making. In contextual search, a learner is trying to learn the value of a hidden vector. Every round the learner is provided an adversarially-chosen context vector, submits a guess for the inner product of the context vector with the hidden vector, learns whether their guess was too high or too low, and incurs some loss based on the quality of their guess. The learner's goal is to minimize their total loss over the course of some number of rounds. We present an algorithm for the contextual search problem for the symmetric loss function that achieves constant total loss. We present a new algorithm for the dynamic pricing problem (which can be realized as a special case of the contextual search problem) that achieves doubly-logarithmic total loss, improving exponentially on the previous best known upper bounds and matching the known lower bounds (up to a polynomial dependence on dimension). Both algorithms make significant use of ideas from the field of integral geometry, most notably the notion of intrinsic volumes of a convex set. To the best of our knowledge this is the first application of intrinsic volumes to algorithm design.

We investigate the problem of learning a Lipschitz function from binary feedback. In this problem, a learner is trying to learn a Lipschitz function $f:[0,1]^d \rightarrow [0,1]$ over the course of $T$ rounds. On round $t$, an adversary provides the learner with an input $x_t$, the learner submits a guess $y_t$ for $f(x_t)$, and learns whether $y_t > f(x_t)$ or $y_t \leq f(x_t)$. The learner's goal is to minimize their total loss $\sum_t\ell(f(x_t), y_t)$ (for some loss function $\ell$). The problem is motivated by \textit{contextual dynamic pricing}, where a firm must sell a stream of differentiated products to a collection of buyers with non-linear valuations for the items and observes only whether the item was sold or not at the posted price. For the symmetric loss $\ell(f(x_t), y_t) = \vert f(x_t) - y_t \vert$, we provide an algorithm for this problem achieving total loss $O(\log T)$ when $d=1$ and $O(T^{(d-1)/d})$ when $d>1$, and show that both bounds are tight (up to a factor of $\sqrt{\log T}$). For the pricing loss function $\ell(f(x_t), y_t) = f(x_t) - y_t {\bf 1}\{y_t \leq f(x_t)\}$ we show a regret bound of $O(T^{d/(d+1)})$ and show that this bound is tight. We present improved bounds in the special case of a population of linear buyers.

Gross substitutability is a central concept in Economics and is connected to important notions in Discrete Convex Analysis, Number Theory and the analysis of Greedy algorithms in Computer Science. Many different characterizations are known for this class, but providing a constructive description remains a major open problem. The construction problem asks how to construct all gross substitutes from a class of simpler functions using a set of operations. Since gross substitutes are a natural generalization of matroids to real-valued functions, matroid rank functions form a desirable such class of simpler functions. Shioura proved that a rich class of gross substitutes can be expressed as sums of matroid rank functions, but it is open whether all gross substitutes can be constructed this way. Our main result is a negative answer showing that some gross substitutes cannot be expressed as positive linear combinations of matroid rank functions. En route, we provide necessary and sufficient conditions for the sum to preserve substitutability, uncover a new operation preserving substitutability and fully describe all substitutes with at most 4 items.

Despite their better revenue and welfare guarantees for repeated auctions, dynamic mechanisms have not been widely adopted in practice. This is partly due to the complexity of their implementation as well as their unrealistic use of forecasting for future periods. We address these shortcomings and present a new family of dynamic mechanisms that are simple and require no distribution knowledge of future periods.

We introduce a new model of stochastic bandits with adversarial corruptions which aims to capture settings where most of the input follows a stochastic pattern but some fraction of it can be adversarially changed to trick the algorithm, e.g., click fraud, fake reviews and email spam. The goal of this model is to encourage the design of bandit algorithms that (i) work well in mixed adversarial and stochastic models, and (ii) whose performance deteriorates gracefully as we move from fully stochastic to fully adversarial models.

Dynamic mechanisms are a powerful technique in designing revenue-maximizing repeated auctions. Despite their strength, these types of mechanisms have not been widely adopted in practice for several reasons, e.g., for their complexity, and for their sensitivity to the accuracy of predicting buyers» value distributions. In this paper, we aim to address these shortcomings and develop simple dynamic mechanisms that can be implemented efficiently, and provide theoretical guidelines for decreasing the sensitivity of dynamic mechanisms on prediction accuracy of buyers» value distributions. We prove that the dynamic mechanism we propose is provably dynamic incentive compatible, and introduce a notion of buyers» regret in dynamic mechanisms, and show that our mechanism achieves bounded regret while improving revenue and social welfare compared to a static reserve pricing policy. Finally, we confirm our theoretical analysis via an extensive empirical study of our dynamic auction on real data sets from online adverting. For example, we show our dynamic mechanisms can provide a +17% revenue lift with relative regret less than 0.2%.

We present a deterministic nearly-linear time algorithm for approximating any point inside a convex polytope with a sparse convex combination of the polytope’s vertices. Our result provides a constructive proof for the Approximate Carathéodory Problem, which states that any point inside a polytope contained in the $\ell_p$ ball of radius $D$ can be approximated to within $\epsilon$ in $\ell_p$ norm by a convex combination of $O\left(D^2 p/\epsilon^2\right)$ vertices of the polytope for $p \geq 2$. While for the particular case of $p=2$, this can be achieved by the well-known Perceptron algorithm, we follow a more principled approach which generalizes to arbitrary $p\geq 2$; furthermore, this naturally extends to domains with more complicated geometry, as it is the case for providing an approximate Birkhoff-von Neumann decomposition. Secondly, we show that the sparsity bound is tight for $\ell_p$ norms, using an argument based on anti-concentration for the binomial distribution, thus resolving an open question posed by Barman. Experimentally, we verify that our deterministic optimization-based algorithms achieve in practice much better sparsity than previously known sampling-based algorithms. We also show how to apply our techniques to SVM training and rounding fractional points in matroid and flow polytopes.

We propose ego-splitting, a new framework for detecting clusters in complex networks which leverage the local structures known as ego-nets (i.e. the subgraph induced by the neighborhood of each node) to de-couple overlapping clusters. Ego-splitting is a highly scalable and flexible framework, with provable theoretical guarantees, that reduces the complex overlapping clustering problem to a simpler and more amenable non-overlapping (partitioning) problem. We can scale community detection to graphs with tens of billions of edges and outperform previous solutions based on ego-nets analysis.

Many online platforms act as intermediaries between a seller and a set of buyers. Examples of such settings include online retailers (such as Ebay) selling items on behalf of sellers to buyers, or advertising exchanges (such as AdX) selling pageviews on behalf of publishers to advertisers. In such settings, revenue sharing is a central part of running such a marketplace for the intermediary, and fixed-percentage revenue sharing schemes are often used to split the revenue among the platform and the sellers. In particular, such revenue sharing schemes require the platform to (i) take at most a constant fraction \alpha of the revenue from auctions and (ii) pay the seller at least the seller declared opportunity cost c for each item sold. A straightforward way to satisfy the constraints is to set a reserve price at c / (1 - \alpha) for each item, but it is not the optimal solution on maximizing the profit of the intermediary. While previous studies (by Mirrokni and Gomes, and by Niazadeh et al) focused on revenue-sharing schemes in static double auctions, in this paper, we take advantage of the repeated nature of the auctions. In particular, we introduce dynamic revenue sharing schemes where we balance the two constraints over different auctions to achieve higher profit and seller revenue. This is directly motivated by the practice of advertising exchanges where the fixed-percentage revenue-share should be met across all auctions and not in each auction. In this paper, we characterize the optimal revenue sharing scheme that satisfies both constraints in expectation. Finally, we empirically evaluate our revenue sharing scheme on real data.

We study the dynamic mechanism design problem of a seller who repeatedly sells independent items to a buyer with private values. In this setting, the seller could potentially extract the entire buyer surplus by running efficient auctions and charging an upfront participation fee at the beginning of the horizon. In some markets, such as internet advertising, participation fees are not practical since buyers expect to inspect items before purchasing them. This motivates us to study the design of dynamic mechanisms under successively more stringent requirements that capture the implicit business constraints of these markets. We first consider a periodic individual rationality constraint, which limits the mechanism to charge at most the buyer's value in each period. While this prevents large upfront participation fees, the seller can still design mechanisms that spread a participation fee across the first few auctions. These mechanisms have the unappealing feature that they provide close-to-zero buyer utility in earlier auctions in exchange for higher utility in later auctions. To address this problem, we introduce a {martingale utility constraint, which imposes the requirement that from the perspective of the buyer, the next item's expected utility is equal to the present one's. Our main result is providing a dynamic auction satisfying martingale utility and periodic individual rationality whose loss in profit with respect to first-best (full extraction of buyer surplus) is optimal up to polylogarithmic factors. The proposed mechanism is a dynamic two-tier auction with a hard floor and a soft floor that allocates the item whenever the buyer's bid is above the hard floor and charges the minimum of the bid and the soft floor.

We consider a multidimensional search problem that is motivated by questions in contextual decision-making, such as dynamic pricing and personalized medicine. Nature selects a state from a d-dimensional unit ball and then generates a sequence of d-dimensional directions. We are given access to the directions, but not access to the state. After receiving a direction, we have to guess the value of the dot product between the state and the direction. Our goal is to minimize the number of times when our guess is more than ε away from the true answer. We construct a polynomial time algorithm that we call Projected Volume achieving regret O(dlog(d/ε)), which is optimal up to a logd factor. The algorithm combines a volume cutting strategy with a new geometric technique that we call cylindrification.

We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and general buyer valuations having only access to an aggregate demand oracle, i.e., an oracle that given prices on all goods, returns the aggregated demand over the entire population of buyers. For the important special case of gross substitute valuations, our algorithm queries the aggregate demand oracle Õ(n) times and takes Õ(n3) time, where n is the number of goods. At the heart of our solution is a method for exactly minimizing certain convex functions which cannot be evaluated but for which the subgradients can be computed. We also give the fastest known algorithm for computing Walrasian equilibrium for gross substitute valuations in the value oracle model. Our algorithm has running time Õ((mn + n3)TV) where TV is the cost of querying the value oracle. A key technical ingredient is to regularize a convex programming formulation of the problem in a way that subgradients are cheap to compute. En route, we give necessary and sufficient conditions for the existence of robust Walrasian prices, i.e., prices for which each agent has a unique demanded bundle and the demanded bundles clear the market. When such prices exist, the market can be perfectly coordinated by solely using prices.

Internet display advertising industry follows two main business models. One model is based on direct deals between publishers and advertisers where they sign legal contracts containing terms of fulfillment for a future inventory. The second model is a spot market based on auctioning page views in real-time on advertising exchange (AdX) platforms such as DoubleClick's Ad Exchange, RightMedia, or AppNexus. These exchanges play the role of intermediaries who sell items (e.g. page-views) on behalf of a seller (e.g. a publisher) to buyers (e.g., advertisers) on the opposite side of the market. The computational and economics issues arising in this second model have been extensively investigated in recent times. In this work, we consider a third emerging model called reservation exchange market. A reservation exchange is a two-sided market between buyer orders for blocks of advertisers' impressions and seller orders for blocks of publishers' page views. The goal is to match seller orders to buyer orders while providing the right incentives to both sides. In this work we first describe the important features of mechanisms for efficient reservation exchange markets. We then address the algorithmic problems of designing revenue sharing schemes to provide a fair division between sellers of the revenue collected from buyers. A major conceptual contribution of this work is in showing that even though both clinching ascending auctions and VCG mechanisms achieve the same outcome from a buyer perspective, however, from the perspective of revenue sharing among sellers, clinching ascending auctions are much more informative than VCG auctions.

We consider the problem faced by a firm that receives highly differentiated products in an online fashion and needs to price them in order to sell them to its customer base. Products are described by vectors of features and the market value of each product is linear in the values of the features. The firm does not initially know the values of the different features, but it can learn the values of the features based on whether products were sold at the posted prices in the past. This model is motivated by a question in online advertising, where impressions arrive over time and can be described by vectors of features. We first consider a multi-dimensional version of binary search over polyhedral sets, and show that it has exponential worst-case regret. We then propose a modification of the prior algorithm where uncertainty sets are replaced by their Lowner-John ellipsoids. We show that this algorithm has a worst-case regret that is quadratic in the dimensionality of the feature space and logarithmic in the time horizon.

Ad exchange platforms connect online publishers and advertisers and facilitate the sale of billions of impressions every day. We study these environments from the perspective of a publisher who wants to find the profit-maximizing exchange in which to sell his inventory. Ideally, the publisher would run an auction among exchanges. However, this is not usually possible due to practical business considerations. Instead, the publisher must send each impression to only one of the exchanges, along with an asking price. We model the problem as a variation of the multi-armed bandits problem in which exchanges (arms) can behave strategically in order to maximizes their own profit. We propose e mechanisms that find the best exchange with sub-linear regret and have desirable incentive properties.

We study the question of setting and testing reserve prices in single item auctions when the bidders are not identical. At a high level, there are two generalizations of the standard second price auction: in the lazy version we first determine the winner, and then apply reserve prices; in the eager version we first discard the bidders not meeting their reserves, and then determine the winner among the rest. We show that the two versions have dramatically different properties: lazy reserves are easy to optimize, and A/B test in production, whereas eager reserves always lead to higher welfare, but their optimization is NP-complete, and naive A/B testing will lead to incorrect conclusions. Despite their different characteristics, we show that the overall revenue for the two scenarios is always within a factor of 2 of each other, even in the presence of correlated bids. Moreover, we prove that the eager auction dominates the lazy auction on revenue whenever the bidders are independent or symmetric. We complement our theoretical results with simulations on real world data that show that even suboptimally set eager reserve prices are preferred from a revenue standpoint.

In various markets where sellers compete in price, price oscillations are observed rather than convergence to equilibrium. Such fluctuations have been empirically observed in the retail market for gasoline, in airline pricing and in the online sale of consumer goods. Motivated by this, we study a model of price competition in which equilibria rarely exist. We seek to analyze the welfare, despite the nonexistence of equilibria, and present welfare guarantees as a function of the market power of the sellers. We first study best response dynamics in markets with sellers that provide a homogeneous good, and show that except for a modest number of initial rounds, the welfare is guaranteed to be high. We consider two variations: in the first the sellers have full information about the buyer's valuation. Here we show that if there are n items available across all sellers and nmax is the maximum number of items controlled by any given seller, then the ratio of the optimal welfare to the achieved welfare will be at most log n/(n-nmax + 1))+1. As the market power of the largest seller diminishes, the welfare becomes closer to optimal. In the second variation we consider an extended model in which sellers have uncertainty about the buyer's valuation. Here we similarly show that the welfare improves as the market power of the larger seller decreases, yet with a worse ratio of n/(n-nmax + 1). Our welfare bounds in both cases are essentially tight. The exponential gap in welfare between the two variations quantifies the value of accurately learning the buyer's valuation in such settings.

One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to 'block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of core in cooperative game theory.

A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations. Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying these properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots. We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multiunit auctions with decreasing marginal utilities in the presence of budget constraints.

Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research in economics, initiated by Hurwicz (1972), is devoted to understanding how such markets perform when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported demands, finding clearing prices in the reported market via an ascending price tatonnement procedure, and returns the resulting allocation. Similar mechanisms are used, for example, in the daily opening of the New York Stock Exchange and the call market for copper and gold in London.

Constraints on agent's ability to pay play a major role in auction design for any setting where the magnitude of financial transactions is sufficiently large. Those constraints have been traditionally modeled in mechanism design as hard budget, i.e., mechanism is not allowed to charge agents more than a certain amount. Yet, real auction systems (such as Google AdWords) allow more sophisticated constraints on agents' ability to pay, such as average budgets. In this work, we investigate the design of Pareto optimal and incentive compatible auctions for agents with constrained quasi-linear utilities, which captures more realistic models of liquidity constraints that the agents may have. Our result applies to a very general class of allocation constraints known as polymatroidal environments, encompassing many settings of interest such as multi-unit auctions, matching markets, video-on demand and advertisement systems.

We consider a single buyer with a combinatorial preference that would like to purchase related products and services from different vendors,where each vendor supplies exactly one product. We study the general case where subsets of products can be substitutes as well as complementary and analyze the game that is induced on the vendors, where a vendor's strategy is the price that he asks for his product. This model generalizes both Bertrand competition (where vendors are perfect substitutes) and Nash bargaining (where they are perfect complements), and captures a wide variety of scenarios that can appear in complex crowd sourcing or in automatic pricing of related products.

We consider the pricing problem faced by a seller who assigns a price to a good that confers its benefits not only to its buyers, but also to other individuals around them. For example, a snow-blower is potentially useful not only to the household that buys it, but also to others on the same street. Given that the seller is constrained to selling such a (locally) public good via individual private sales, how should he set his prices given the distribution of values held by the agents?

Auctions for perishable goods such as internet ad inventory need to make real-time allocation and pricing decisions as the supply of the good arrives in an online manner, without knowing the entire supply in advance. These allocation and pricing decisions get complicated when buyers have some global constraints. In this work, we consider a multi-unit model where buyers have global {\em budget} constraints, and the supply arrives in an online manner. Our main contribution is to show that for this setting there is an individually-rational, incentive-compatible and Pareto-optimal auction that allocates these units and calculates prices on the fly, without knowledge of the total supply. We do so by showing that the Adaptive Clinching Auction satisfies a {\em supply-monotonicity} property. We also analyze and discuss, using examples, how the insights gained by the allocation and payment rule can be applied to design better ad allocation heuristics in practice. Finally, while our main technical result concerns multi-unit supply, we propose a formal model of online supply that captures scenarios beyond multi-unit supply and has applications to sponsored search. We conjecture that our results for multi-unit auctions can be extended to these more general models.

Typical models of strategic interactions in computer science use simultaneous move games. However, in applications simultaneity is often hard or impossible to achieve. In this paper, we study the robustness of the Nash Equilibrium when the assumption of simultaneity is dropped. In particular we propose studying the sequential price of anarchy: the quality of outcomes of sequential versions of games whose simultaneous counterparts are prototypical in algorithmic game theory. We study different classes of games with high price of anarchy, and show that the subgame perfect equilibrium of their sequential version is a much more natural prediction, ruling out unreasonable equilibria, and leading to much better quality solutions.

The buying and selling of information is taking place at a scale unprecedented in the history of commerce, thanks to the formation of online marketplaces for user data. Data providing agencies sell user information to advertisers to allow them to match ads to viewers more effectively. In this paper we study the design of optimal mechanisms for a monopolistic data provider to sell information to a buyer, in a model where both parties have (possibly correlated) private signals about a state of the world, and the buyer uses information learned from the seller, along with his own signal, to choose an action (e.g., displaying an ad) whose payoff depends on the state of the world.

Signaling is an important topic in the study of asymmetric information in economic settings. In particular, the transparency of information available to a seller in an auction setting is a question of major interest. We introduce the study of signaling when conducting a second price auction of a probabilistic good whose actual instantiation is known to the auctioneer but not to the bidders. This framework can be used to model impressions selling in display advertising. We establish several results within this framework. First, we study the problem of computing a signaling scheme that maximizes the auctioneer's revenue in a Bayesian setting. We show that this problem is polynomially solvable for some interesting special cases, but computationally hard in general. Second, we establish a tight bound on the minimum number of signals required to implement an optimal signaling scheme. Finally, we show that at least half of the maximum social welfare can be preserved within such a scheme.

In many settings agents participate in multiple different auctions that are not necessarily implemented simultaneously. Future opportunities affect strategic considerations of the players in each auction, introducing externalities. Motivated by this consideration, we study a setting of a market of buyers and sellers, where each seller holds one item, bidders have combinatorial valuations and sellers hold item auctions sequentially. Our results are qualitatively different from those of simultaneous auctions, proving that simultaneity is a crucial aspect of previous work. We prove that if sellers hold sequential first price auctions then for unit-demand bidders (matching market) every subgame perfect equilibrium achieves at least half of the optimal social welfare, while for submodular bidders or when second price auctions are used, the social welfare can be arbitrarily worse than the optimal. We also show that a first price sequential auction for buying or selling a base of a matroid is always efficient, and implements the VCG outcome. An important tool in our analysis is studying first and second price auctions with externalities (bidders have valuations for each possible winner outcome), which can be of independent interest. We show that a Pure Nash Equilibrium always exists in a first price auction with externalities.

A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations. Toward this goal and motivated by AdWords auctions, we present an auction for polymatroidal environments satisfying the above properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots.

The Generalized Second Price (GSP) auction is the primary auction used for selling sponsored search advertisements. In this paper we consider the revenue of this auction at equilibrium. We prove that if agent values are drawn from identical regular distributions, then the GSP auction paired with an appropriate reserve price generates a constant fraction (1/6th) of the optimal revenue. In the full-information game, we show that at any Nash equilibrium of the GSP auction obtains at least half of the revenue of the VCG mechanism excluding the payment of a single participant. This bound holds also with any reserve price, and is tight.

The Generalized Second Price (GSP) auction is the primary method by which sponsered search advertisements are sold. We study the performance of this auction in the Bayesian setting for players with correlated types. Correlation arises very naturally in the context of sponsored search auctions, especiallyasaresultofuncertaintyinherentinthebehaviour of the underlying ad allocation algorithm. We demonstrate that the Bayesian Price of Anarchy of the GSP auction is bounded by 4, even when agents have arbitrarily correlated types. Our proof highlights a connection between the GSP mechanism and the concept of smoothness in games, which may be of independent interest. For the special case of uncorrelated (i.e. independent) agent types, we improve our bound to 2(1−1/e) −1 ≈ 3.16, significantly improving upon previously known bounds. Using our techniques, we obtain the same bound on the performanceofGSPatcoarsecorrelatedequilibria, whichcaptures (for example) a repeated-auction setting in which agents apply regret-minimizing bidding strategies. Moreoever, our analysis is robust against the presence of irrational bidders and settings of asymmetric information, and our bounds degrade gracefully when agents apply strategies that form only an approximate equilibrium.

The Generalized Second Price Auction has been the main mechanism used by search companies to auction positions for advertisements on search pages. In this paper we study the social welfare of the Nash equilibria of this game in various models. In the full information setting, socially optimal Nash equilibria are known to exist (i.e., the Price of Stability is 1). This paper is the first to prove bounds on the price of anarchy, and to give any bounds in the Bayesian setting. Our main result is to show that the price of anarchy is small assuming that all bidders play un-dominated strategies. In the full information setting we prove a bound of 1.618 for the price of anarchy for pure Nash equilibria, and a bound of 4 for mixed Nash equilibria. We also prove a bound of 8 for the price of anarchy in the Bayesian setting, when valuations are drawn independently, and the valuation is known only to the bidder and only the distributions used are common knowledge. Our proof exhibits a combinatorial structure of Nash equilibria and uses this structure to bound the price of anarchy. While establishing the structure is simple in the case of pure and mixed Nash equilibria, the extension to the Bayesian setting requires the use of novel combinatorial techniques that can be of independent interest.