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.

When training transformers on graph-structured data, incorporating information about the underlying topology is crucial for good performance. Topological masking, a type of relative position encoding, achieves this by upweighting or downweighting attention depending on the relationship between the query and keys in the graph. In this paper, we propose to parameterise topological masks as a learnable function of a weighted adjacency matrix -- a novel, flexible approach which incorporates a strong structural inductive bias. By approximating this mask with graph random features (for which we prove the first known concentration bounds), we show how this can be made fully compatible with linear attention, preserving $\mathcal{O}(N)$ time and space complexity with respect to the number of input tokens. The fastest previous alternative was $\mathcal{O}(N \log N)$ and only suitable for specific graphs. Our efficient masking algorithms provide strong performance gains for image and point cloud data, including with $>30$k nodes.

The rise of interactive platforms like conversational AI assistants introduces a new dimension to ad auctions: time. As a conversation evolves, a platform can learn more about a user's interests, creating a fundamental trade-off: delay ad delivery to acquire precise information about ad quality, or deliver the ad immediately to capitalize on a thick market before potential bidders are revealed to be poor matches. We study this trade-off in a model where a revenue-maximizing platform can commit to an auction format (first- or second-price) but not to its timing, endogenously choosing when to run the auction after observing its beliefs about advertisers' ad quality.

We envision a marketplace where diverse entities offer specialized "modules" through APIs, allowing users to compose the outputs of these modules for complex tasks within a given budget. This paper studies the market design problem in such an ecosystem, where module owners strategically set prices for their APIs (to maximize their profit) and a central platform orchestrates the aggregation of module outputs at query-time. One can also think about this as a first-price procurement auction with budgets. The first observation is that if the platform's algorithm is to find the optimal set of modules then this could result in a poor outcome, in the sense that there are price equilibria which provide arbitrarily low value for the user. We show that under a suitable version of the "bang-per-buck" algorithm for the knapsack problem, an ε-approximate equilibrium always exists, for any arbitrary ε > 0. Further, our first main result shows that with this algorithm any such equilibrium provides a constant approximation to the optimal value that the buyer could get under various constraints including (i) a budget constraint and (ii) a budget and a matroid constraint. This can also be interpreted as a price of anarchy result for budget-constrained first-price procurement auctions. Finally, we demonstrate that these approximately efficient equilibria can be learned through decentralized price adjustments by module owners using no-regret learning algorithms.

In this paper, we initiate the study of autobidding where the signals for each bidder can be noisy and correlated. Our first set of results showcases the failure of traditional auctions such as the second-price auction (SPA) and the first-price auction (FPA). In particular, uniform bidding is not an optimal bidding strategy for SPA and both SPA and FPA can have arbitrarily poor efficiency. To circumvent this, we propose the Contextual Second Price Auction (CSPA), a novel mechanism which mitigates the aforementioned adverse effects by leveraging multiple signals to adjust the allocation of SPA. We show that uniform bidding is an optimal bidding strategy in CSPA and we prove a tight bound on the price for anarchy for CSPA of 2, thus recovering the well-established results in the independent setting. Finally, we show that CSPA always achieves at least half the welfare of SPA; moreover this is also tight.

We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of $\frac{e}{e-1}$, and provide a $\frac{4e}{e-1}$-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm.

We study an auction setting in which bidders bid for placement of their content within a summary generated by a large language model (LLM), e.g., an ad auction in which the display is a summary paragraph of multiple ads. This generalizes the classic ad settings such as position auctions to an LLM generated setting, which allows us to handle general display formats. We propose a novel factorized framework in which an auction module and an LLM module work together via a prediction model to provide welfare maximizing summary outputs in an incentive compatible manner. We provide a theoretical analysis of this framework and synthetic experiments to demonstrate the feasibility and validity of the system together with welfare comparisons.

We study the design of prior-independent auctions in a setting with heterogeneous bidders. In particular, we consider the setting of selling to n bidders whose values are drawn from n independent but not necessarily identical distributions. We work in the robust auction design regime, where we assume the seller has no knowledge of the bidders’ value distributions and must design a mechanism that is prior-independent. While there have been many strong results on prior-independent auction design in the i.i.d. setting, not much is known for the heterogeneous setting, even though the latter is of significant practical importance. Unfortunately, no prior-independent mechanism can hope to always guarantee any approximation to Myerson's revenue in the heterogeneous setting; similarly, no prior-independent mechanism can consistently do better than the second-price auction. In light of this, we design a family of (parametrized) randomized auctions which approximates at least one of these benchmarks: For heterogeneous bidders with regular value distributions, our mechanisms either achieve a good approximation of the expected revenue of an optimal mechanism (which knows the bidders’ distributions) or exceeds that of the second-price auction by a certain multiplicative factor. The factor in the latter case naturally trades off with the approximation ratio of the former case. We show that our mechanism is optimal for such a trade-off between the two cases by establishing a matching lower bound. Our result extends to selling k identical items to heterogeneous bidders with an additional O(ln2 k)-factor in our trade-off between the two cases.

We consider the problem of maximizing the gains from trade (GFT) in two-sided markets. The seminal impossibility result by Myerson and Satterthwaite (1983) shows that even for bilateral trade, there is no individually rational (IR), Bayesian incentive compatible (BIC) and budget balanced (BB) mechanism that can achieve the full GFT. Moreover, the optimal BIC, IR and BB mechanism that maximizes the GFT is known to be complex and heavily depends on the prior. In this paper, we pursue a Bulow-Klemperer-style question, i.e., does augmentation allow for prior-independent mechanisms to compete against the optimal mechanism? Our first main result shows that in the double auction setting with m i.i.d. buyers and n i.i.d. sellers, by augmenting O(1) buyers and sellers to the market, the GFT of a simple, dominant strategy incentive compatible (DSIC), and prior-independent mechanism in the augmented market is at least the optimal in the original market, when the buyers’ distribution first-order stochastically dominates the sellers’ distribution. The mechanism we consider is a slight variant of the standard Trade Reduction mechanism due to McAfee (1992). For comparison, Babaioff, Goldner, and Gonczarowski (2020) showed that if one is restricted to augmenting only one side of the market, then n(m + 4√m) additional agents are sufficient for their mechanism to beat the original optimal and ⌊ log2 m ⌋ additional agents are necessary for any prior-independent mechanism. Next, we go beyond the i.i.d. setting and study the power of two-sided recruitment in more general markets. Our second main result is that for any ε > 0 and any set of O(1/ε) buyers and sellers where the buyers’ value exceeds the sellers’ value with constant probability, if we add these additional agents into any market with arbitrary correlations, the Trade Reduction mechanism obtains a (1−ε)-approximation of the GFT of the augmented market. Importantly, the newly recruited agents are agnostic to the original market.

We propose a new Markov Decision Process (MDP) model for ad auctions to capture the user response to the quality of ads, with the objective of maximizing the long-term discounted revenue. By incorporating user response, our model takes into consideration all three parties involved in the auction (advertiser, auctioneer, and user). The state of the user is modeled as a user-specific click-through rate (CTR) with the CTR changing in the next round according to the set of ads shown to the user in the current round. We characterize the optimal mechanism for this MDP as a Myerson's auction with a notion of modified virtual value, which relies on the value distribution of the advertiser, the current user state, and the future impact of showing the ad to the user. Leveraging this characterization, we design a sample-efficient and computationally-efficient algorithm which outputs an approximately optimal policy that requires only sample access to the true MDP and the value distributions of the bidders. Finally, we propose a simple mechanism built upon second price auctions with personalized reserve prices and show it can achieve a constant-factor approximation to the optimal long term discounted revenue.

We study the efficiency of non-truthful auctions for auto-bidders with both return on spend (ROS) and budget constraints. The efficiency of a mechanism is measured by the price of anarchy (PoA), which is the worst case ratio between the liquid welfare of any equilibrium and the optimal (possibly randomized) allocation. Our first main result is that the first-price auction (FPA) is optimal, among deterministic mechanisms, in this setting. Without any assumptions, the PoA of FPA is n which we prove is tight for any deterministic mechanism. However, under a mild assumption that a bidder's value for any query does not exceed their total budget, we show that the PoA is at most 2. This bound is also tight as it matches the optimal PoA without a budget constraint. We next analyze two randomized mechanisms: randomized FPA (rFPA) and "quasi-proportional'' FPA. We prove two results that highlight the efficacy of randomization in this setting. First, we show that the PoA of rFPA for two bidders is at most 1.8 without requiring any assumptions. This extends prior work which focused only on an ROS constraint. Second, we show that quasi-proportional FPA has a PoA of 2 for any number of bidders, without any assumptions. Both of these bypass lower bounds in the deterministic setting. Finally, we study the setting where bidders are assumed to bid uniformly. We show that uniform bidding can be detrimental for efficiency in deterministic mechanisms while being beneficial for randomized mechanisms, which is in stark contrast with the settings without budget constraints.

Auto-bidding has recently become a popular feature in ad auctions. This feature enables advertisers to simply provide high-level constraints and goals to an automated agent, which optimizes their auction bids on their behalf. These auto-bidding intermediaries interact in a decentralized manner in the underlying auctions, leading to new interesting practical and theoretical questions on auction design, for example, in understanding the bidding equilibrium properties between auto-bidder intermediaries for different auctions. In this paper, we examine the effect of different auctions on the incentives of advertisers to report their constraints to the auto-bidder intermediaries. More precisely, we study whether canonical auctions such as first price auction (FPA) and second price auction (SPA) are auto-bidding incentive compatible (AIC): whether an advertiser can gain by misreporting their constraints to the autobidder.

Auto-bidding is now widely adopted as an interface between advertisers and internet advertising as it allows advertisers to specify high-level goals, such as maximizing value subject to a value-per-spend constraint. Prior research has mainly focused on auctions that are truthful (such as a second-price auction) because these auctions admit simple (uniform) bidding strategies and are thus simpler to analyze. The main contribution of this paper is to characterize the efficiency across the spectrum of all auctions, including non-truthful auctions for which optimal bidding may be complex.

Advertisers in online ad auctions are increasingly using auto-bidding mechanisms to bid into auctions instead of directly bidding their value manually. One of the prominent auto-bidding formats is that of target cost-per-acquisition (tCPA) which maximizes the volume of conversions subject to a return-of-investment constraint. From an auction theoretic perspective however, this trend seems to go against foundational results that postulate that for profit-maximizing (aka quasi-linear) bidders, it is optimal to use a classic bidding system like marginal CPA (mCPA) bidding rather than using strategies like tCPA.

Internet ad auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amounts of space, and an advertiser can provide multiple formats, only one of which can be shown.The seller is now faced with a multi-parameter mechanism design problem.Computing an efficient allocation is computationally intractable, and therefore the standard Vickrey-Clarke-Groves (VCG) auction, while truthful and welfare-optimal, is impractical. In this paper, we tackle a fundamental problem in the design of modern ad auctions. We adopt a ``Myersonian'' approach and study allocation rules that are monotone both in the bid and set of rich ads. We show that such rules can be paired with a payment function to give a truthful auction. Our main technical challenge is designing a monotone rule that yields a good approximation to the optimal welfare. Monotonicity doesn't hold for standard algorithms, e.g. the incremental bang-per-buck order, that give good approximations to ``knapsack-like'' problems such as ours. In fact, we show that no deterministic monotone rule can approximate the optimal welfare within a factor better than $2$ (while there is a non-monotone FPTAS). Our main result is a new, simple, greedy and monotone allocation rule that guarantees a $3$ approximation. In ad auctions in practice, monotone allocation rules are often paired with the so-called \emph{Generalized Second Price (GSP)} payment rule, which charges the minimum threshold price below which the allocation changes. We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) is bounded. Under standard no-overbidding assumptions, we prove bounds on the a pure and Bayes-Nash PoA. Finally, we experimentally test our algorithms on real-world data.

Auto-bidding is an area of increasing importance in the domain of online advertising. We study the problem of designing auctions in an auto-bidding setting with the goal of maximizing welfare at system equilibrium. Previous results showed that the price of anarchy (PoA) under VCG is 2 and also that this is tight even with two bidders. This raises an interesting question as to whether VCG yields the best efficiency in this setting, or whether the PoA can be improved upon. We present a prior-free randomized auction in which the PoA is approx. 1.896 for the case of two bidders, proving that one can achieve an efficiency strictly better than that under VCG in this setting. We also provide a stark impossibility result for the problem in general as the number of bidders increases – we show that no (randomized) anonymous truthful auction can have a PoA strictly better than 2 asymptotically as the number of bidders per query increases. While it was shown in previous work that one can improve on the PoA of 2 if the auction is allowed to use the bidder’s values for the queries in addition to the bidder’s bids, we note that our randomized auction is prior-free and does not use such additional information; our impossibility result also applies to auctions without additional value information.

The connection between games and no-regret algorithms has been widely studied in the literature. A fundamental result is that when all players play no-regret strategies, this produces a sequence of actions whose time-average is a coarse-correlated equilibrium of the game. However, much less is known about equilibrium selection in the case that multiple equilibria exist. In this work, we study the convergence of no-regret bidding algorithms in auctions. Besides being of theoretical interest, bidding dynamics in auctions is an important question from a practical viewpoint as well. We study the repeated game between bidders in which a single item is sold at each time step and the bidder's value is drawn from an unknown distribution. We show that if the bidders use any mean-based learning rule then the bidders converge with high probability to the truthful pure Nash Equilibrium in a second price auction, in VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a first price auction. We note mean-based algorithms cover a wide variety of known no-regret algorithms such as Exp3, UCB, \epsilon-Greedy etc. Also, we analyze the convergence of the individual iterates produced by such learning algorithms, as opposed to the time-average of the sequence. Our experiments corroborate our theoretical findings and also find a similar convergence when we use other strategies such as Deep Q-Learning.

We consider the fundamental problem of selecting $k$ out of $n$ random variables in a way that the expected highest or second-highest value is maximized. This question captures several applications where we have uncertainty about the quality of candidates (e.g. auction bids, search results) and have the capacity to explore only a small subset due to an exogenous constraint. For example, consider a second price auction where system constraints (e.g., costly retrieval or model computation) allow the participation of only $k$ out of $n$ bidders, and the goal is to optimize the expected efficiency (highest bid) or expected revenue (second highest bid). We study the case where we are given an explicit description of each random variable. We give a PTAS for the problem of maximizing the expected highest value. For the second-highest value, we prove a hardness result: assuming the Planted Clique Hypothesis, there is no constant factor approximation algorithm that runs in polynomial time. Surprisingly, under the assumption that each random variable has monotone hazard rate (MHR), a simple score-based algorithm, namely picking the $k$ random variables with the largest $1/\sqrt{k}$ top quantile value, is a constant approximation to the expected highest and second highest value, \emph{simultaneously}.

In-app advertising is a complex market worth billions of dollars per year, yet it has been studied significantly less than traditional web display ads. In this paper we study an important but often overlooked feature of ads in mobile apps (mostly absent in traditional web ads), that of ad refreshes : A user is shown a stream of banner ads during the app session, in which each ad is displayed in the ad slot for a certain amount of time (the refresh rate) before the ad-slot is refreshed to the next ad. Data analysis on our large-scale experiments that vary refresh rates reveals a surprising result, that cannot be explained by existing user click models: Varying ads» refresh almost preserves total number of clicks. We propose a new, natural, "two-phase" click model for this setting that explains this independence, as well as our measurements of the click-through rate as a function of the impression»s time-on-screen and of ad-repeat counts. The new click model leads to a clean formulation of the problem of auctioning the entire user-session: i.e., determining online, both the sequence of winning ads as well as the amount of time to display each one. We complement the theoretical auction design with results from a live-traffic experiment with its implementation. Our experiments and analysis provide the theoretical foundation for AdMob»s "Google-optimized refresh rate" feature, used by many mobile apps for better monetization of ads shown to millions of users.

The online stochastic matching problem is a variant of online bipartite matching in which edges are labeled with probabilities. A match will “succeed” with the probability along that edge; this models, for instance, the click of a user in search advertisement. The goal is to maximize the expected number of successful matches. This problem was introduced by Mehta and Panigrahi (FOCS 2012), who focused on the case where all probabilities in the graph are equal. They gave a 0.567-competitive algorithm for vanishing probabilities, relative to a natural benchmark, leaving the general case as an open question. This paper examines the general case where the probabilities may be unequal. We take a new algorithmic approach rather than generalizing that of Mehta and Panigrahi: Our algorithm maintains, at each time, the probability that each offline vertex has succeeded thus far, and chooses assignments so as to maximize marginal contributions to these probabilities. When the algorithm does not observe the realizations of the edges, this approach gives a 0.5-competitive algorithm, which achieves the known upper bound for such “non-adaptive” algorithms. We then modify this approach to be “semi-adaptive:” if the chosen target has already succeeded, choose the arrival's “second choice” instead (while still updating the probabilities non-adaptively). With one additional tweak to control the analysis, we show that this algorithm achieves a competitive ratio of 0.534 for the unequal, vanishing probabilities setting. A “fully-adaptive” version of this algorithm turns out to be identical to an algorithm proposed, but not analyzed, in Mehta and Panigrahi (2012); we do not manage to analyze it either since it introduces too many dependencies between the stochastic processes. Our semi-adaptive algorithm thus can be seen as allowing analysis of competitive ratio while still capturing the power of adaptivity.

Search engine ad auctions typically have a significant fraction of advertisers who are budget constrained, i.e., if allowed to participate in every auction that they bid on, they would spend more than their budget. This yields an important problem: selecting the ad auctions which these advertisers participate, in order to optimize different system objectives such as the return on investment for advertisers, and the quality of ads shown to users. We present a system and algorithms for optimizing budget constrained spend. The system is designed be deployed in a large search engine, with hundreds of thousands of advertisers, millions of searches per hour, and with the query stream being only partially predictable. We have validated the system design by implementing it in the Google ads serving system and running experiments on live traffic. We have also compared our algorithm to previous work that casts this problem as a large linear programming problem limited to popular queries, and show that our algorithms yield substantially better results.

The online matching problem has received significant attention in recent years because of its connections to allocation problems in Internet advertising, crowd-sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations, rather it is to maximize the number of successful allocations, where success of an allocation is governed by a stochastic process which follows the allocation. To address such applications, we propose and study the online matching problem with stochastic rewards (called the ONLINE STOCHASTIC MATCHING problem) in this paper. Our problem also has close connections to the existing literature on stochastic packing problems, in fact, our work initiates the study of online stochastic packing problems. We give a deterministic algorithm for the ONLINE STOCHASTIC MATCHING problem whose competitive ratio converges to (approximately) 0.567 for uniform and vanishing probabilities. We also give a randomized algorithm which outperforms the deterministic algorithm for higher probabilities. Finally, we complement our algorithms by giving an upper bound on the competitive ratio of any algorithm for this problem. This result shows that the best achievable competitive ratio for the ONLINE STOCHASTIC MATCHING problem is provably worse than that for the (non-stochastic) online matching problem.

We study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a bipartite graph. The vertices in U have weights and are known ahead of time, while the vertices in V arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in U. When all the weights are equal, this reduces to the classic online bipartite matching problem for which Karp, Vazirani and Vazirani gave an optimal (1 − 1/e)-competitive algorithm in their seminal work [10]. Our main result is an optimal (1 − 1/e)-competitive randomized algorithm for general vertex weights. We use random perturbations of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in [10] in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of online budgeted allocations [14] in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of [14, 3] which apply when the bids are much smaller than the budgets.

We consider the online bipartite matching problem in the unknown distribution input model. We show that the Ranking algorithm of [KVV90] achieves a competitive ratio of at least 0.653. This is the first analysis to show an algorithm which breaks the natural 1 - 1/e -barrier' in the unknown distribution model (our analysis in fact works in the stricter, random order model) and answers an open question in [GM08]. We also describe a family of graphs on which Ranking does no better than 0.727 in the random order model. Finally, we show that for graphs which have k > 1 disjoint perfect matchings, Ranking achieves a competitive ratio of at least 1 - √(1/k - 1/k2 + 1/n) -- in particular Ranking achieves a factor of 1 - o(1) for graphs with ω(1) disjoint perfect matchings.

A classic theorem by Vizing proves that if the maximum degree of a graph is Δ, then it is possible to color its edges, in polynomial time, using at most Δ+1 colors. However, this algorithm is offline, i.e., it assumes the whole graph is known in advance. A natural question then is how well we can do in the online setting, where the edges of the graph are revealed one by one, and we need to color each edge as soon as it is added to the graph. Online edge coloring has an important application in fast switch scheduling. Here, a natural model is that edges arrive online, but in a random permutation. Even in the random permutations model, the best analysis for any algorithm is factor 2, which comes from the simple greedy algorithm (which is factor 2 even in the worst case online model). The algorithm of Aggarwal et al. [1] provides a 1+o(1) factor algorithm, but for the case of multigraphs, when Δ = ω(n2), where n is the number of vertices. In this paper, we show that for graphs with Δ = ω(log n), it is possible to color the graph with 1.43Δ + o(Δ) colors in the online random order model. Our algorithm is inspired by a 1.6 factor distributed offline algorithm of Panconesi and Srinivasan [9], which we extend by reusing colors online in multiple rounds.

We consider the class of max-min and min-max optimization problems subject to a global budget constraint. We undertake a systematic algorithmic and complexity-theoretic study of such problems, which we call design problems. Every optimization problem leads to a natural design problem. Our main result uses techniques of Freund and Schapire [Games Econom. Behav., 29 (1999), pp. 79–103] from learning theory, and its generalizations, to show that for a large class of optimization problems, the design version is as easy as the optimization version. We also observe the relationship between max-min design problems and fractional packing problems. In particular, we obtain in a systematic fashion results about the fractional packing number of Steiner trees.

We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of 1- 1/e ¿ 0.632, a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the 1 - 1/e bound. Our main result is a 0.67-approximation online algorithm for stochastic bipartite matching, breaking this 1 - ¿ barrier. Furthermore, we show that no online algorithm can produce a 1 - ¿ approximation for an arbitrarily small e for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-)matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application.

We compare the expected efficiency of revenue maximizing (or optimal) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for selling a single item with (k + logeovere-1 k + 1) bidders is at least as much as the efficiency of the efficiency-maximizing mechanism with k bidders, when bidder valuations are drawn i.i.d. from a Monotone Hazard Rate distribution. Surprisingly, we also show that this bound is tight within a small additive constant of 4.7. In other words, Θ(log k) extra bidders suffice for the revenue-maximizing mechanism to match the efficiency of the efficiency-maximizing mechanism, while o(log k) do not. This is in contrast to the result of Bulow and Klemperer comparing the revenue of the two mechanisms, where only one extra bidder suffices. More precisely, they show that the revenue of the efficiency-maximizing mechanism with k + 1 bidders is no less than the revenue of the revenue-maximizing mechanism with k bidders.

We study the fundamental classification problems 0-Extension and Metric Labeling. A generalization of Multiway Cut, 0-Extension is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization Metric Labeling is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial–time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant. We prove (1) that the integrality ratio of the earthmover relaxation for Metric Labeling is $\Omega(\log k)$ (which is asymptotically tight), k being the number of labels, whereas the best previous lower bound on the integrality ratio was only constant; (2) that the integrality ratio of the earthmover relaxation for 0-Extension is $\Omega(\sqrt{\log k})$, k being the number of terminals (it was known to be $O((\log k)/\log\log k)$), whereas the best previous lower bound was only constant; (3) that for no $\epsilon>0$ is there a polynomial-time $O((\log n)^{1/4-\epsilon})$-approximation algorithm for 0-Extension, n being the number of vertices, unless NP$\subseteq$DTIME$(n^{\mathrm{poly}(\log n)})$, whereas the strongest inapproximability result known before was only MAX SNP-hardness; and (4) that there is a polynomial-time approximation algorithm for 0-Extension with performance ratio $O(\sqrt{\mathrm{diam}(d)})$, where $\mathrm{diam}(d)$ is the ratio of the largest to smallest nonzero distances in the terminal metric.

A common technique for processing conjunctive queries is to first match each predicate separately using an index lookup, and then compute the intersection of the resulting row- id lists, via an AND-tree. The performance of this technique depends crucially on the order of lists in this tree: it is important to compute early the intersections that will produce small results. But this optimization is hard to do when the data or predicates have correlation. We present a new algorithm for ordering the lists in an AND- tree by sampling the intermediate intersection sizes. We prove that our algorithm is near-optimal and validate its effectiveness experimentally on datasets with a variety of distributions.

It is known [5] that an additively ε-approximate Nash equilibrium (with supports of size at most two) can be computed in polynomial time in any 2-player game with ε=.5. It is also known that no approximation better than .5 is possible unless equilibria with support larger than logn are considered, where n is the number of strategies per player. We give a polynomial algorithm for computing an ε-approximate Nash equilibrium in 2-player games with ε ≈ .38; our algorithm computes equilibria with arbitrarily large supports.

The only known general technique for designing truthful, approximatelybudget-balanced cost-sharing mechanisms is due to Moulin. While Moulin mechanisms have been successfully designed for a widerange of applications, recent negative results show that for manyfundamental cost-sharing problems, Moulin mechanisms inevitably sufferfrom poor budget-balance, poor economic efficiency, or both. We propose acyclic mechanisms, a new framework for designingtruthful, approximately budget-balanced cost-sharing mechanisms. Acyclic mechanisms strictly generalize Moulin mechanisms andoffer three important advantages. First, it is easier to design acyclic mechanisms than Moulinmechanisms: many classical primal-dual algorithms naturallyinduce a non-Moulin acyclic mechanism with good performanceguarantees. Second, for several important classes of cost-sharing problems, acyclicmechanisms have exponentially better budget-balance and economicefficiency than Moulin mechanisms.Finally, while Moulin mechanisms have found application primarily in binary demand games, we extend acyclic mechanisms to general demand games, a multi-parameter setting in which each bidder can be allocated one of several levels of service.

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/ e for this problem.

We study the fundamental classification problems O-EXTENSION and METRIC LABELING. MINIMUM WEIGHT TRIANGULATION is closely related to partitioning problems in graph theory and to Lipschitz extensions in Banach spaces; its generalization METRIC LABELING is motivated by applications in computer vision. Researchers had proposed using earthmover metrics to get polynomial time-solvable relaxations for these problems. A conjecture that has attracted much attention recently is that the integrality ratio for these relaxations is constant.We prove

We study the following question: What is the smallest t such that every symmetric boolean function on k variables (which is not a constant or a parity function), has a non-zero Fourier coefficient of order at least 1 and at most t? We exclude the constant functions for which there is no such t and the parity functions for which t has to be k. Let τ(k) be the smallest such t. The main contribution of this paper is a proof of the following self similar nature of this question: If τ(l) ≤ s, then for any ɛ> 0 and � for k ≥ k0(l, ɛ), τ(k) ≤ k s+1 l+1 + ɛ Coupling this result with a computer based search which establishes τ(30) = 2, one obtains that for large enough k, τ(k) ≤ 3k/31. The motivation for our work is to understand the complexity of learning symmetric juntas. A k-junta is a boolean function of n variables that depends only on an unknown subset of k variables. If f is symmetric in the variables it depends on, it is called a symmetric k-junta. Our results imply an algorithm to learn the class of symmetric k-juntas, in the uniform PAC learning model, in time approximately n 3k 31. This improves on a result of Mossel, O’Donnell and Servedio in [11], who show that symmetric k-juntas can be ∗ Research supported by NSF grants CCR-0002299 and CCF-0431023.

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it to derive two optimal algorithms achieving competitive ratios of 1-1/e for this problem.

We study two problems, that of computing social optimum and that of finding fair allocations, in the congestion game model of Milchtaich[8] Although we show that the general problem is hard to approximate to any factor, we give simple algorithms for natural simplifications. We also consider these problems in the symmetric network congestion game model [11, 4], and show hardness results and approximate solutions.

In the digital goods setting we prove that for any randomized auction which is truthful in expectation, there exists an equivalent randomized auction which randomizes over truthful deterministic auctions. By equivalent auctions we mean auctions in which the probability of winning and the expected price offered are the same for all bidders for all bid values. We also prove an approximate equivalence proof in the case where the bids come from a discrete space. Finally, we consider the computational issue of finding an efficient equivalent auction.

We prove the existence of ε-Nash equilibrium strategies with support logarithmic in the number of pure strategies. We also show that the payoffs to all players in any (exact) Nash equilibrium can be ε-approximated by the payoffs to the players in some such logarithmic support ε-Nash equilibrium. These strategies are also uniform on a multiset of logarithmic size and therefore this leads to a quasi-polynomial algorithm for computing an ε-Nash equilibrium. To our knowledge this is the first subexponential algorithm for finding an ε-Nash equilibrium. Our results hold for any multiple-player game as long as the number of players is a constant (i.e., it is independent of the number of pure strategies). A similar argument also proves that for a fixed number of players m, the payoffs to all players in any m-tuple of mixed strategies can be ε-approximated by the payoffs in some m-tuple of constant support strategies.We also prove that if the payoff matrices of a two person game have low rank then the game has an exact Nash equilibrium with small support. This implies that if the payoff matrices can be well approximated by low rank matrices, the game has an ε-equilibrium with small support. It also implies that if the payoff matrices have constant rank we can compute an exact Nash equilibrium in polynomial time.

We describe a fixed point approach for the following stochastic optimization problem: given a multicast tree and probability distributions of user utilities, compute prices to offer the users in order to maximize the expected profit of the service provider. We show that any optimum pricing is a fixed point of an efficiently computable map. In the language of classical numerical analysis, we show that the non-linear Jacobi and Gauss-Seidel methods of coordinate descent are applicable to this problem. We provide proof of convergence to the optimum prices for special cases of utility distributions and tree edge costs.