We study a new model of complementary valuations, which we call "proportional complementarities.'' In contrast to common models, such as hypergraphic valuations, in our model, we do not assume that the extra value derived from owning a set of items is independent of the buyer's base valuations for the items. Instead, we model the complementarities as proportional to the buyer's base valuations, and these proportionalities are known market parameters. Our goal is to design a simple pricing scheme that, for a single buyer with proportional complementarities, yields approximately optimal revenue. We define a new class of mechanisms where some number of items are given away for free, and the remaining items are sold separately at inflated prices. We find that the better of such a mechanism and selling the grand bundle earns a 12-approximation to the optimal revenue for pairwise proportional complementarities. This confirms the intuition that items should not be sold completely separately in the presence of complementarities. In the more general case, a buyer has a maximum of proportional positive hypergraphic valuations, where a hyperedge in a given hypergraph describes the boost to the buyer's value for item i given by owning any set of items T in addition. The maximum-out-degree of such a hypergraph is d, and k is the positive rank of the hypergraph. For valuations given by these parameters, our simple pricing scheme is an O(min{d,k})-approximation.

DNN training is extremely time-consuming, necessitating efficient multi-accelerator parallelization. Current approaches to paralleliz- ing training primarily use intra-batch parallelization, where a single iteration of training is split over the available workers, but suffer from diminishing returns at higher worker counts. We present PipeDream, a system that adds inter-batch pipelining to intra-batch parallelism to further improve parallel training throughput, help- ing to better overlap computation with communication and reduce the amount of communication when possible. PipeDream versions model parameters for backward pass correctness, schedules for- ward and backward passes of different minibatches concurrently on different workers to keep workers well utilized, and systemati- cally partitions DNN layers among workers to balance work and minimize communication. Extensive experimentation with a range of DNN tasks, models, and hardware configurations shows that PipeDream trains models to high accuracy up to 5.28x faster than commonly used inter-batch parallelism techniques.

We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling, cloud computing, and communicating over a network. This model is quite different from the traditional models, to the extent that neither do the classical equilibrium existence results seem to apply to it nor do any of the efficient algorithmic techniques developed to compute equilibria seem to apply directly. We give a proof of existence of equilibrium and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. We observe that in our market model, the set of equilibrium prices could be a connected, non-convex set. To the best of our knowledge, this is the first natural example of the phenomenon where the set of solutions could have such complicated structure, yet there is a combinatorial polynomial time algorithm to find one. Finally, we show that our model inherits many of the fairness properties of traditional equilibrium models.

We study a basic auction design problem with online supply. There are two unit-demand bidders and two types of items. The first item type will arrive first for sure, and the second item type may or may not arrive. The auctioneer has to decide the allocation of an item immediately after each item arrives, but is allowed to compute payments after knowing how many items arrived. For this problem we show that there is no deterministic truthful and individually rational mechanism that, even with unbounded computational resources, gets any finite approximation factor to the optimal social welfare.

Enabling interactive data exploration at cloud scale requires minimizing end-to-end query execution latency, while guar- anteeing fault tolerance, and query execution under resource- constraints. Typically, such a query execution involves or- chestrating the execution of hundreds or thousands of re- lated tasks on cloud scale clusters. Without any resource constraints, all query tasks can be scheduled to execute si- multaneously (gang scheduling) while connected tasks stream data between them. When the data size referenced by a query increases, gang scheduling may be resource-wasteful or un-satisfiable with a limited, per-query resource budget. This paper introduces Bubble Execution, a new query processing framework for interactive workloads at cloud scale, that balances cost-based query optimization, fault tolerance, optimal resource management, and execution orchestration. Bubble execution involves dividing a query execution graph into a collection of query sub-graphs (bubbles), and scheduling them within a per-query resource budget. The query operators (tasks) inside a bubble stream data between them while fault tolerance is handled by persisting temporary results at bubble boundaries. Our implementation enhances our JetScope service, for interactive workloads, deployed in production clusters at Microsoft. Experiments with TPC-H queries show that bubble execution can reduce resource usage significantly in the presence of failures while maintaining performance competitive with gang execution.

We consider "time-of-use" pricing as a technique for matching supply and demand of temporal resources with the goal of maximizing social welfare. Relevant examples include energy, computing resources on a cloud computing platform, and charging stations for electric vehicles, among many others. A client/job in this setting has a window of time during which he needs service, and a particular value for obtaining it. We assume a stochastic model for demand, where each job materializes with some probability via an independent Bernoulli trial. Given a per-time-unit pricing of resources, any realized job will first try to get served by the cheapest available resource in its window and, failing that, will try to find service at the next cheapest available resource, and so on. Thus, the natural stochastic fluctuations in demand have the potential to lead to cascading overload events. Our main result shows that setting prices so as to optimally handle the expected demand works well: with high probability, when the actual demand is instantiated, the system is stable and the expected value of the jobs served is very close to that of the optimal offline algorithm.

We consider a scheduling problem where a cloud service provider has multiple units of a resource available over time. Selfish clients submit jobs, each with an arrival time, deadline, length, and value. The service provider's goal is to implement a truthful online mechanism for scheduling jobs so as to maximize the social welfare of the schedule. Recent work shows that under a stochastic assumption on job arrivals, there is a single-parameter family of mechanisms that achieves near-optimal social welfare. We show that given any such family of near-optimal online mechanisms, there exists an online mechanism that in the worst case performs nearly as well as the best of the given mechanisms. Our mechanism is truthful whenever the mechanisms in the given family are truthful and prompt, and achieves optimal (within constant factors) regret. We model the problem of competing against a family of online scheduling mechanisms as one of learning from expert advice. A primary challenge is that any scheduling decisions we make affect not only the payoff at the current step, but also the resource availability and payoffs in future steps. Furthermore, switching from one algorithm (a.k.a. expert) to another in an online fashion is challenging both because it requires synchronization with the state of the latter algorithm as well as because it affects the incentive structure of the algorithms. We further show how to adapt our algorithm to a non-clairvoyant setting where job lengths are unknown until jobs are run to completion. Once again, in this setting, we obtain truthfulness along with asymptotically optimal regret (within poly-logarithmic factors).

We study Fisher markets and the problem of maximizing the Nash social welfare (NSW), and show several closely related new results. In particular, we obtain:

• A new integer program for the NSW maximization problem whose fractional relaxation has a bounded integrality gap. In contrast, the natural integer program has an unbounded integrality gap.
• An improved, and tight, factor 2 analysis of the algorithm of [7]; in turn showing that the integrality gap of the above relaxation is at most 2. The approximation factor shown by [7] was 2e^(1/e) ~ 2.89.
• A lower bound of e^(1/e) ~ 1.44 on the integrality gap of this relaxation.
• New convex programs for natural generalizations of linear Fisher markets and proofs that these markets admit rational equilibria.

In the multi-unit pricing problem, multiple units of a single item are for sale. A buyer's valuation for n units of the item is v*min{n,d}, where the per unit valuation v and the capacity d are private information of the buyer. We consider this problem in the Bayesian setting, where the pair (v,d) is drawn jointly from a given probability distribution. In the unlimited supply setting, the optimal (revenue maximizing) mechanism is a pricing problem, i.e., it is a menu of lotteries. In this paper we show that under a natural regularity condition on the probability distributions, which we call decreasing marginal revenue, the optimal pricing is in fact deterministic. It is a price curve, offering i units of the item for a price of p_i, for every integer i. Further, we show that the revenue as a function of the prices p_i is a concave function, which implies that the optimum price curve can be found in polynomial time. This gives a rare example of a natural multi-parameter setting where we can show such a clean characterization of the optimal mechanism. We also give a more detailed characterization of the optimal prices for the case where there are only two possible demands.

We consider revenue maximization in online auctions and pricing. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted pricing problem, we show regret bounds that scale with the best fixed price, rather than the range of the values. We also show regret bounds that are almost scale free, and match the offine sample complexity, when comparing to a benchmark that requires a lower bound on the market share. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret w.r.t. a given action scales with its own range, rather than the maximum range.

We consider a revenue-maximizing seller with a single item facing a single buyer with a private budget. The (value, budget) pair is drawn from an arbitrary and possibly correlated distribution. We characterize the optimal mechanism in such cases, and quantify the amount of price discrimination that might be present. For example, there could be up to 3*2^(k-1)-1 distinct non-trivial menu options in the optimal mechanism for such a buyer with k distinct possible budgets (compared to k if the marginal distribution of values conditioned on each budget has decreasing marginal revenue [Che and Gale, 2000], or 2 if there is an arbitrary distribution and one possible budget [Chawla et al., 2011]). Our approach makes use of the duality framework of Cai et al. [2016], and duality techniques related to the "FedEx Problem" of Fiat et al. [2016]. In contrast to [Fiat et al., 2016] and other prior work, we characterize the optimal primal/dual without nailing down an explicit closed form.

We consider the linear contextual bandit problem with resource consumption, in addition to reward generation. In each round, the outcome of pulling an arm is a reward as well as a vector of resource consumptions. The expected values of these outcomes depend linearly on the context of that arm. The budget/capacity constraints require that the total consumption doesn’t exceed the budget for each resource. The objective is once again to maximize the total reward. This problem turns out to be a common generalization of classic linear contextual bandits (linContextual), bandits with knapsacks (BwK), and the online stochastic packing problem (OSPP). We present algorithms with near-optimal regret bounds for this problem. Our bounds compare favorably to results on the unstruc- tured version of the problem where the relation between the contexts and the outcomes could be arbitrary, but the algorithm only competes against a fixed set of policies accessible through an optimization oracle. We combine techniques from the work on linContextual, BwK and OSPP in a nontrivial manner while also tackling new difficulties that are not present in any of these special cases.

Traditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai et al. and Cole and Roughgarden to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden for the non-identical but independent value distribution case.

We provide a unified view of many recent exciting developments in Bayesian mechanism design, including the black-box reductions of Cai et. al., simple mechanisms for additive buyers [Hart and Nisan, Li and Yao, Babaioff et al.], and posted-price mechanisms for unit-demand buyers [Chawla et al., Kleinberg and Weinberg]. Additionally, we show that viewing these three previously disjoint lines of work through the same lens allows us to improve upon each in several directions. First, our work provides a new and transparent duality framework for Bayesian mechanism design, which naturally accommodates multiple agents, and arbitrary objectives and feasibility constraints. Using this, we prove that either a posted-price mechanism, or the VCG mechanism with per-bidder entry fees is a constant-factor approximation to the optimal Bayesian IC mechanism whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et al. and Yao. In addition, we improve the approximation factor in Yao's work from 69 to 8. Finally, we show that this view also leads to improved structural characterizations in the Cai et. al. framework.

We consider a contextual version of multi-armed bandit problem with global knapsack constraints. In each round, the outcome of pulling an arm is a scalar reward and a resource consumption vector, both dependent on the context, and the global knapsack constraints require the total consumption for each resource to be below some pre-fixed budget. The learning agent competes with an arbitrary set of context-dependent policies. This problem was introduced by Badanidiyuru et al., who gave a computationally inefficient algorithm with near optimal regret bounds for it. We give a computationally efficient algorithm for this problem with slightly better regret bounds, by generalizing the approach of Agarwal et al. for the non-constrained version of the problem. The computational time of our algorithm scales logarithmically in the size of the policy space. This answers the main open question of Badanidiyuru et al. We also extend our results to a variant where there are no knapsack constraints but the objective is an arbitrary Lipschitz concave function of the sum of outcome vectors.

We explore a radically different approach for building data center interconnects--using free-space optics between racks, it enables all rack-pairs to communicate via direct links and can reconfigure such links within 12us. Our approach uses a digital micromirror device (DMD) and mirror assembly combination as a transmitter and a photodetector on top of the rack as a receiver. Transmitters and receivers in our interconnect can be dynamically linked in billions of ways. We develop topology construction and routing methods to exploit this flexibility, including a new flow scheduling algorithm that is a constant factor approximation to the offline optimal solution. We build a small prototype that points to the feasibility of our approach. Simulations and analysis show that, for realistic data center workloads, it can improve mean flow completion time by 30-95%, while reducing cost by 25-40%.

In this paper we propose a general family of position auctions used in paid search, which we call multi-score position auctions. These auctions contain the GSP auction and the GSP auction with squashing as special cases. We show experimentally that these auctions contain special cases that perform better than the GSP auction with squashing, in terms of revenue, and the number of clicks on ads. In particular, we study in detail the special case that squashes the first slot alone and show that this beats pure squashing (which squashes all slots uniformly). We study the equilibria that arise in this special case to examine both the first order and the second order effect of moving from the squashing-all-slots auction to the squash-only-the-top-slot auction. For studying the second order effect, we simulate auctions using the value-relevance correlated distribution suggested in Lahaie and Pennock [2007]. Since this distribution is derived from a study of value and relevance distributions in Yahoo! we believe the insights derived from this simulation to be valuable. For measuring the first order effect, in addition to the said simulation, we also conduct experiments using auction data from Bing over several weeks that includes a random sample of all auctions.

We consider a pricing problem where a buyer is interested in purchasing/using a good, such as an app or music or software, repeatedly over time. The consumer discovers his value for the good only as he uses it, and the value evolves with each use. Optimizing for the seller's revenue in such dynamic settings is a complex problem and requires assumptions about how the buyer behaves before learning his future value(s), and in particular, how he reacts to risk. We explore the performance of a class of pricing mechanisms that are extremely simple for both the buyer and the seller to use: the buyer reacts to prices myopically without worrying about how his value evolves in the future; the seller needs to optimize for revenue over a space of only two parameters, and can do so without knowing the buyer's risk profile or fine details of the value evolution process. We present simple-versus-optimal type results, namely that under certain assumptions, simple pricing mechanisms of the above form are approximately optimal regardless of the buyer's risk profile . Our results assume that the buyer's value per usage evolves as a martingale. For our main result, we consider pricing mechanisms in which the seller offers the product for free for a certain number of uses, and then charges an appropriate fixed price per usage. We assume that the buyer responds by buying the product for as long as his value exceeds the fixed price. Importantly, the buyer does not need to know anything about how his future value will evolve, only how much he wants to use the product right now . Regardless of the buyers' initial value, our pricing captures as revenue a constant fraction of the total value that the buyers accumulate in expectation over time.

In recent years, there has been a growing interest in speed scaling algorithms, where a set of jobs need to be scheduled on a machine with variable speed so as to optimize the flow-times of the jobs and the energy consumed by the machine. A series of results have culminated in constant-competitive algorithms for this problem in the clairvoyant model, i.e., when job parameters are revealed on releasing a job (Bansal, Pruhs, and Stein, SODA 2007; Bansal, Chan, and Pruhs, SODA 2009). Our main contribution in this paper is the first constant-competitive speed scaling algorithm in the non- clairvoyant model, which is typically used in the scheduling literature to model practical settings where job volume is revealed only after the job has been completely processed. Unlike in the clairvoyant model, the speed scaling problem in the non-clairvoyant model is non-trivial even for a single job. Our non-clairvoyant algorithm is defined by using the existing clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other online optimization problems. We also give additional algorithmic results and lower bounds for speed scaling on multiple identical parallel machines.

We introduce single-bid auctions as a new format for combinatorial auctions. In single-bid auctions, each bidder submits a single real-valued bid for the right to buy items at a fixed price. Contrary to other simple auction formats, such as simultaneous or sequential single-item auctions, bidders can implement no-regret learning strategies for single-bid auctions in polynomial time. Price of anarchy bounds for correlated equilibria concepts in single-bid auctions therefore have more bite than their counterparts for auctions and equilibria for which learning is not known to be computationally tractable (or worse, known to be computationally intractable). Towards this end, we show that for any subadditive valuations the social welfare at equilibrium is an O(log m) approximation to the optimal social welfare, where m is the number of items. We also provide tighter approximation results for several subclasses. Our welfare guarantees hold for Nash equilibria and no-regret learning outcomes in both Bayesian and complete information settings via the smooth-mechanism framework. Of independent interest, our techniques show that in a combinatorial auction setting, efficiency guarantees of a mechanism via smoothness for a very restricted class ofcardinality it valuations extend, with a small degradation, to subadditive valuations, the largest complement-free class of valuations.

We consider the problem of a revenue-maximizing seller with m items for sale to n additive bidders with hard budget constraints, assuming that the seller has some prior distribution over bidder values and budgets. The prior may be correlated across items and budgets of the same bidder, but is assumed independent across bidders. We target mechanisms that are Bayesian Incentive Compatible, but that are ex-post Individually Rational and ex-post budget respecting. Virtually no such mechanisms are known that satisfy all these conditions and guarantee any revenue approximation, even with just a single item. We provide a computationally efficient mechanism that is a 3-approximation with respect to all BIC, ex-post IR, and ex-post budget respecting mechanisms. Note that the problem is NP-hard to approximate better than a factor of 16/15, even in the case where the prior is a point mass [Chakrabarty and Goel 2010]. We further characterize the optimal mechanism in this setting, showing that it can be interpreted as a distribution over virtual welfare maximizers. We prove our results by making use of a black-box reduction from mechanism to algorithm design developed by [Cai et al. 2013]. Our main technical contribution is a computationally efficient 3-approximation algorithm for the algorithmic problem that results by an application of their framework to this problem. The algorithmic problem has a mixed-sign objective and is NP-hard to optimize exactly, so it is surprising that a computationally efficient approximation is possible at all. In the case of a single item (m = 1), the algorithmic problem can be solved exactly via exhaustive search, leading to a computationally efficient exact algorithm and a stronger characterization of the optimal mechanism as a distribution over virtual value maximizers.

We introduce the online stochastic Convex Programming (CP) problem, a very general version of stochas- tic online problems which allows arbitrary concave objectives and convex feasibility constraints. Many well- studied problems like online stochastic packing and covering, online stochastic matching with concave returns, etc. form a special case of online stochastic CP. We present fast algorithms for these problems, which achieve near-optimal regret guarantees for both the i.i.d. and the random permutation models of stochastic inputs. When applied to the special case online packing, our ideas yield a simpler and faster primal-dual algorithm for this well studied problem, which achieves the optimal competitive ratio. Our techniques make explicit the connection of primal-dual paradigm and online learning to online stochastic CP.

A special case of Myerson's classic result describes the revenue-optimal equilibrium when a seller offers a single item to a buyer. We study a repeated sales extension of this model: a seller offers to sell a single fresh copy of an item to the same buyer every day via a posted price. The buyer's value for the item is unknown to the seller but is drawn initially from a publicly known distribution F and remains the same throughout. We study this setting where the seller is unable to commit to future prices and find several surprises. First, if the horizon is fixed, previous work showed that an equilibrium exists, and all equilibria yield tiny or constant revenue. This is a far cry from the linearly growing benchmark of getting Myerson optimal revenue each day. Our first result shows that this is because the buyer strategies in these equilibria are necessarily unnatural. We restrict to a natural class of buyer strategies called threshold strategies, and show that threshold equilibria rarely exist. Second, if the seller can commit not to raise prices upon purchase, while still retaining the possibility of lowering prices in future, we show that threshold equilibria always exist and for most distributions there is a unique threshold equilibrium. As an example, if F is uniform in [0,1], the seller can extract revenue of order $\sqrt{n}$ in $n$ rounds as opposed to the constant revenue obtainable when he is unable to make commitments. Finally, we consider the infinite horizon game, where both the seller and the buyer discount the future utility by a factor of $1-\delta \in [0,1)$. When the value distribution is uniform in [0,1], there exists a threshold equilibrium with expected revenue at least $\frac{4}{3+2\sqrt{2}} \sim 69$\% of the Myerson optimal revenue benchmark. This is in sharp contrast to the constant revenue obtained in the limit of the $n$-stage games as $n$ approaches infinity.

An automated market maker is a natural and common mechanism to subsidize information acquisition, revelation, and aggregation in a prediction market. The sought-after prediction aggregate is the equilibrium price. However, traders with budget constraints are restricted in their ability to impact the market price on their own. We give a detailed characterization of optimal trades in the presence of budget constraints in a prediction market with a cost-function-based automated market maker. As a concrete application of our characterization, we give sufficient conditions for a property we call budget additivity: two traders with budgets B and B' and the same beliefs would have a combined impact equal to a single trader with budget B +B'. That way, even if a single trader cannot move the market much, a crowd of like-minded traders can have the same desired effect. We show that a generalization of the heavily-used logarithmic market scoring rule is budget additive for affinely independent payoffs, but the quadratic market scoring rule is not. Our results may be used both descriptively, to understand if a particular market maker is affected by budget constraints or not, and prescriptively, as a recipe to construct markets.

We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching markets. When the agents' values are drawn independently from a distribution, the Bayesian optimal mechanism is given by Myerson as a virtual-surplus optimizer. We develop a framework for prior-free mechanism design and analysis. A good mechanism in our framework approximates the optimal mechanism for the distribution if there is a distribution; moreover, when there is no distribution this mechanism still provably performs well.
We define and characterize optimal envy-free outcomes in symmetric single-dimensional environments. Our characterization mirrors Myerson's theory. Furthermore, unlike in mechanism design where there is no point-wise optimal mechanism, there is always a point-wise optimal envy-free outcome.
Envy-free outcomes and incentive-compatible mechanisms are similar in structure and performance. We therefore use the optimal envy-free revenue as a benchmark for measuring the performance of a prior-free mechanism. A good mechanism is one that approximates the envy-free benchmark on any profile of agent values. We show that good mechanisms exist, and in particular, a natural generalization of the random sampling auction of Goldberg et al. is a constant approximation.

In this paper, we consider a very general model for exploration-exploitation tradeoff which allows arbitrary concave rewards and convex constraints on the decisions across time, in addition to the customary limitation on the time horizon. This model subsumes the classic multi-armed bandit (MAB) model, and the Bandits with Knapsacks (BwK) model of Badanidiyuru et al.[2013]. We also consider an extension of this model to allow linear contexts, similar to the linear contextual extension of the MAB model. We demonstrate that a natural and simple extension of the UCB family of algorithms for MAB provides a polynomial time algorithm that has near-optimal regret guarantees for this substantially more general model, and matches the bounds provided by Badanidiyuru et al.[2013] for the special case of BwK, which is quite surprising. We also provide computationally more efficient algorithms by establishing interesting connections between this problem and other well studied problems/algorithms such as the Blackwell approachability problem, online convex optimization, and the Frank-Wolfe technique for convex optimization. We give examples of several concrete applications, where this more general model of bandits allows for richer and/or more efficient formulations of the problem.

We observe that Lambert et al.'s [2008] family of weighted score wagering mechanisms admit arbitrage: participants can extract a guaranteed positive payoff by betting on any prediction within a certain range. In essence, participants leave free money on the table when they "agree to disagree", and as a result, rewards don’t necessarily go to the most informed and accurate participants. This observation suggests that when participants have immutable beliefs, it may be possible to design alternative mechanisms in which the center can make a profit by removing this arbitrage opportunity without sacrificing incentive properties such as individual rationality, incentive compatibility, and sybilproofness. We introduce a new family of wagering mechanisms called no-arbitrage wagering mechanisms that retain many of the positive properties of weighted score wagering mechanisms, but with the arbitrage opportunity removed. We show several structural results about the class of mechanisms that satisfy no-arbitrage in conjunction with other properties, and provide examples of no-arbitrage wagering mechanisms with interesting properties.

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for unrelated machines.) For power functions of the form $f(s) = s^\alpha$ for some constant $\alpha>1$, we get a competitive ratio of $O(\tfrac {\alpha} {\log \alpha}) $, improving upon a previous competitive ratio of $O(\alpha^2)$ by Anand et al., along with a matching lower bound of $\Omega(\tfrac {\alpha} {\log \alpha})$. Further, in the resource augmentation model, with a 1+ $\epsilon$ speed up, we give a $2( \tfrac 1 \epsilon+1)$ competitive algorithm, with essentially the same techniques, improving the bound of $1 + O(\frac{1}{\epsilon^2})$ by Gupta et al. and matching the bound of Anand et al. for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself.

In the context of online ad serving, display ads may appear on different types of web-pages, where each page includes several ad slots and therefore multiple ads can be shown on each page. The set of ads that can be assigned to ad slots of the same page needs to satisfy various pre-specified constraints including exclusion constraints, diversity constraints, and the like. Upon arrival of a user, the ad serving system needs to allocate a set of ads to the current web-page respecting these per-page allocation constraints. Previous slot-based settings ignore the important concept of a page, and may lead to highly suboptimal results in general. In this paper, motivated by these applications in display advertising and inspired by the submodular welfare maximization problem with online bidders, we study a general class of page-based ad allocation problems, present the first (tight) constant-factor approximation algorithms for these problems, and confirm the performance of our algorithms experimentally on real-world data sets. A key technical ingredient of our results is a novel primal-dual analysis for handling free-disposal, which updates dual variables using a "level function" instead of a single level, and unifies with previous analyses of related problems. This new analysis method allows us to handle arbitrarily complicated allocation constraints for each page. Our main result is an algorithm that achieves a 1 - 1/e - o(1) competitive ratio. Moreover, our experiments on real-world data sets show signi?cant improvements of our page-based algorithms compared to the slot-based algorithms. Finally, we observe that our problem is closely related to the submodular welfare maximization (SWM) problem. In particular, we introduce a variant of the SWM problem with online bidders, and show how to solve this problem using our algorithm for whole page optimization.

In Internet ad auctions, search engines often throttle budget constrained advertisers so as to spread their spends across the specified time period. Such policies are known as budget smoothing policies. In this paper, we perform a principled, game-theoretic study of what the outcome of an ideal budget smoothing algorithm should be. In particular, we propose the notion of regret-free budget smoothing policies whose outcomes throttle each advertiser optimally, given the participation of the other advertisers. We show that regret-free budget smoothing policies always exist, and in the case of single slot auctions we can give a polynomial time smoothing algorithm. Inspired by the existence proof, we design a heuristic for budget smoothing which performs considerably better than existing benchmark heuristics.

We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service of the agents. These environments include position auctions where slots with decreasing click-through rates are auctioned to advertisers. We generalize and characterize the envy-free benchmark from Hartline and Yan [2011] to settings with budgets and characterize the optimal envy-free outcomes for both welfare and revenue. We give prior-free mechanisms that approximate these benchmarks. A building block in our mechanism is a clinching auction for position auction environments. This auction is a generalization of the multi-unit clinching auction of Dobzinski et al. [2008] and a special case of the polyhedral clinching auction of Goel et al. [2012]. For welfare maximization, we show that this clinching auction is a good approximation to the envy-free optimal welfare for position auction environments. For profit maximization, we generalize the random sampling profit extraction auction from Fiat et al. [2002] for digital goods to give a 10.0-approximation to the envy-free optimal revenue in symmetric, downward- closed environments. Even without budgets this revenue maximization question is of interest and we obtain an improved approximation bound of 7.5 (from 30.4 by Ha and Hartline [2012]).

Tatonnement is a simple and natural rule for updating prices in Exchange (Arrow-Debreu) markets. In this paper we de- ?ne a class of markets for which tatonnement is equivalent to gradient descent. This is the class of markets for which there is a convex potential function whose gradient is always equal to the negative of the excess demand and we call it Convex Potential Function (CPF) markets. We show the following results.

• CPF markets contain the class of Eisenberg Gale (EG) markets, de?ned previously by Jain and Vazirani.
• The subclass of CPF markets for which the demand is a differentiable function contains exactly those mar- kets whose demand function has a symmetric negative semi-definite Jacobian.
• We de?ne a family of continuous versions of taton- nement based on gradient descent using a Bregman divergence. As we show, all processes in this family converge to an equilibrium for any CPF market. This is analogous to the classic result for markets satisfying the Weak Gross Substitutes property.
• A discrete version of tatonnement converges toward the equilibrium for the following markets of comple- mentary goods; its convergence rate for these settings is analyzed using a common potential function.
  • Fisher markets in which all buyers have Leontief utilities. The tatonnement process reduces the distance to the equilibrium, as measured by the potential function, to an epsilon fraction of its initial value in O(1/epsilon) rounds of price updates.
  • Fisher markets in which all buyers have comple- mentary CES utilities. Here, the distance to thequilibrium is reduced to epsilon fraction of its initial value in O(log(1/epsilon)) rounds of price updates.
  This shows that tatonnement converges for the entire range of Fisher markets when buyers have complementary CES utilities, in contrast to prior work, which could analyze only the substitutes range, together with a small portion of the complementary range.

We give a simple proof that the RANKING algorithm of Karp, Vazirani and Vazirani is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. The approach also generalizes easily to the vertex-weighted version considered by Agarwal et al. Further we show that the proof is very similar to the deterministic primal-dual argument for the online budgeted allocation problem with small bids (also called the AdWords problem) of Mehta et al.

In this paper we consider the adwords problem in the unknown distribution model. We consider the case where the budget to bid ratio $k$ is at least 2, and give improved competitive ratios. Earlier results had competitive ratios better than $1-1/e$ only for ``large enough'' $k$, while our competitive ratio increases continuously with $k$. For $k=2$ the competitive ratio we get is $0.729$ and it is $0.9$ for $k=16$. We also improve the asymptotic competitive ratio for large $k$ from $1 - O(\sqrt{\log n /k})$ to $1 - O(\sqrt{1 /k})$, thus removing any dependence on $n$, the number of advertisers. This ratio is optimal, even with known distributions. That is, even if an algorithm is tailored to the distribution, it cannot get a competitive ratio of $1 - o(\sqrt{1 /k})$, whereas our algorithm does not depend on the distribution. The algorithm is rather simple, it computes a score for every advertiser based on his original budget, the remaining budget and the remaining number of steps in the algorithm and assigns a query to the advertiser with the highest bid plus his score. The analysis is based on a ``hybrid argument'' that considers algorithms that are part actual, part hypothetical, to prove that our (actual) algorithm is better than a completely hypothetical algorithm whose performance is easy to analyze.

We consider a significant generalization of the Adwords problem by allowing arbitrary concave returns, and we characterize the optimal competitive ratio achievable. The problem considers a sequence of items arriving online that have to be allocated to agents, with different agents bidding different amounts. The objective function is the sum, over each agent i, of a monotonically non-decreasing concave function $M_i : R_+ \rightarrow R_+$ of the total amount allocated to i. All variants of online matching problems (including the Adwords problem) studied in the literature consider the special case of budgeted linear functions, that is, functions of the form $M_i( u_i) = \min \{u_i,B_i\}$ for some constant $B_i$. The distinguishing feature of this paper is in allowing arbitrary concave returns. The main result of this paper is that for each concave function $M$, there exists a constant $F(M) \leq 1$ such that

• there exists an algorithm with competitive ratio of \\$\min_i\{ F(M_i) \}$, independent of the sequence of items.
• No algorithm has a competitive ratio larger than $F(M)$ over all instances with $M_i= M$ for all $i$.

We describe a real-time bidding algorithm for performance-based display ad allocation. A central issue in performance display advertising is matching campaigns to ad impressions, which can be formulated as a constrained optimization problem that maximizes revenue subject to constraints such as budget limits and inventory availability. The current practice is to solve the optimization problem offline at a tractable level of impression granularity (e.g., the placement level), and to serve ads online based on the precomputed static delivery scheme. Although this offline approach takes a global view to achieve optimality, it fails to scale to ad delivery decision making at an individual impression level. Therefore, we propose a real-time bidding algorithm that enables fine-grained impression valuation (e.g., targeting users with real-time conversion data), and adjusts value-based bid according to real-time constraint snapshot (e.g., budget consumption level). Theoretically, we show that under a linear programming (LP) primal-dual formulation, the simple real-time bidding algorithm is indeed an online solver to the original primal problem by taking the optimal solution to the dual problem as input. In other words, the online algorithm guarantees the offline optimality given the same level of knowledge an offline optimization would have. Empirically, we develop and experiment with two real-time bid adjustment approaches to adapting to the non-stationary nature of the marketplace: one adjusts bids against real-time constraint satisfaction level using control-theoretic methods, and the other adjusts bids also based on the historical bidding landscape statistically modeled. Finally, we show experimental results with real-world ad serving data.

We present algorithms for a class of resource allocation problems both in the online setting with stochastic input and in the offline setting. This class of problems contains many interesting special cases such as the Adwords problem. In the online setting we introduce a new distributional model called the adversarial stochastic input model, which is a generalization of the i.i.d model with unknown distributions, where the distributions can change over time. In this model we give a 1 - O(epsilon) approximation algorithm for the resource allocation problem, with almost the weakest possible assumption: the ratio of the maximum amount of resource consumed by any single request to the total capacity of the resource, and the ratio of the profit contributed by any single request to the optimal profit is at most O (epsilon^2 /log(n/epsilon) where n is the number of resources available. There are instances where this ratio is epsilon^2/log n such that no randomized algorithm can have a competitive ratio of 1 - o(epsilon^2) even in the i.i.d model. The upper bound on ratio that we require improves on the previous upper-bound for the i.i.d case by a factor of n. Our proof technique also gives a very simple proof that the greedy algorithm has a competitive ratio of 1 - 1/e for the Adwords problem in the i.i.d model with unknown distributions, and more generally in the adversarial stochastic input model, when there is no bound on the bid to budget ratio. All the previous proofs assume that either bids are very small compared to budgets or something very similar to this. In the offline setting we give a fast algorithm to solve very large LPs with both packing and covering constraints. We give algorithms to approximately solve (within a factor of 1 + epsilon) the mixed packing-covering problem with O(gamma m log(n/delta)/epsilon^2 ) oracle calls where the constraint matrix of this LP has dimension n x m, the success probability of the algorithm is 1 - delta, and gamma is a parameter which is very similar to the ratio described for the online setting. We discuss several applications, and how our algorithms improve existing results in some of these applications.

Designing distributed algorithms that converge quickly to an equi- librium is one of the foremost research goals in algorithmic game theory, and convex programs have played a crucial role in the de- sign of algorithms for Fisher markets. In this paper we shed new light on both aspects for Fisher markets with linear and spending constraint utilities. We show fast convergence of the Proportional Response dynamics recently introduced by Wu and Zhang [WZ07]. The convergence is obtained from a new perspective: we show that the Proportional Response dynamics is equivalent to a gradient de- scent algorithm (with respect to a Bregman divergence instead of euclidean distance) on a convex program that captures the equilib- ria for linear utilities. We further show that the convex program program easily extends to the case of spending constraint utilities, thus resolving an open question raised by [Vaz10]. This also gives a way to extend the Proportional Response dynamics to spending constraint utilties. We also prove a technical result that is interest- ing in its own right: that the gradient descent algorithm based on a Bregman divergence converges with rate O(1/t) under a condition that is weaker than having Lipschitz continuous gradient (which is the usual assumption in the optimization literature for obtaining the same rate).

We derive efficient algorithms for both detecting and representing matchings in lopsided bipartite graphs; such graphs have so many nodes on one side that it is infeasible to represent them in memory or to identify matchings using standard approaches. Detecting and representing matchings in lopsided bipartite graphs is important for allocating and delivering guaranteed-placement display ads, where the corresponding bipartite graph of interest has nodes representing advertisers on one side and nodes representing web-page impressions on the other; real-world instances of such graphs can have billions of impression nodes. We provide theoretical guarantees for our algorithms, and in a real-world advertising application, we demonstrate the feasibility of our detection algorithms.

We study bargaining networks, discussed in a recent paper of Kleinberg and Tardos, from the perspective of cooperative game theory. In particular we examine three solution concepts, the nucleolus, the core center and the core median. All solution concepts define unique solutions, so they provide testable predictions. We define a new monotonicity property that is a natural axiom of any bargaining game solution, and we prove that all three of them satisfy this monotonicity property. This is actually in contrast to the conventional wisdom for general cooperative games that monotonicity and the core condition (which is a basic property that all three of them satisfy) are incompatible with each other. Our proofs are based on a primal-dual argument (for the nucleolus) and on the FKG inequality (for the core center and the core median). We further observe some qualitative differences between the solution concepts. In particular, there are cases where a strict version of our monotonicity property is a natural axiom, but only the core center and the core median satisfy it. On the other hand, the nucleolus is easy to compute, whereas computing the core center or the core median is #P-hard (yet it can be approximated in polynomial time).