Search

The article discusses the importance of submodular welfare maximization (SWM) for internet advertising. Topics discussed include the general classification of web-based advertising allocation problems, the role of algorithms for real data sets, and computation of allocation constraints for web-based advertising.

The article discusses the study regarding the development of prior-free mechanism for welfare and revenue maximization of the auction agents with common budget. Topics discussed include identifying several appropriate prior-free benchmarks, the mechanism's optimization of its objectives such as incentive constraint, budget constraint, and feasibility constraint, and the characterization of clinching auction.

The article discusses a principled, game-theoretic study of budget smoothing algorithm for Internet advertising (ad) auctions . Topics discussed include proposing the notion of regret-free budget smoothing policies, the existence of the regret-free budget smoothing policies and giving a polynomial time smoothing algorithm in single slot auctions, and designing a heuristic for budget smoothing that performs better compared with existing benchmark heuristics.

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(√log n/k) to 1 - O(√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(√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. [ABSTRACT FROM AUTHOR]

Designing distributed algorithms that converge quickly to an equilibrium is one of the foremost research goals in algorithmic game theory, and convex programs have played a crucial role in the design 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. The convergence is obtained from a new perspective: we show that the Proportional Response dynamics is equivalent to a gradient descent algorithm (with respect to a Bregman divergence instead of euclidean distance) on a convex program that captures the equilibria 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 Vazirani. This also gives a way to extend the Proportional Response dynamics to spending constraint utilties. We also prove a technical result that is interesting 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). [ABSTRACT FROM AUTHOR]

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(ε) 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 (ε2/log(1/ε)2)/(log n + log (1/ε)) where n is the number of resources available. There are instances where this ratio is #949;2/log n such that no randomized algorithm can have a competitive ratio of 1-o(ε) 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+ε) the mixed packing-covering problem with O(γ m log n/ε2) oracle calls where the constraint matrix of this LP has dimension n x m, and γ 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We analyze the problem of designing a truthful pay-per-click auction where the click-through-rates (CTR) of the bidders are unknown to the auction. Such an auction faces the classic explore/exploit dilemma: while gathering information about the click through rates of advertisers, the mechanism may loose revenue; however, this gleaned information may prove valuable in the future for a more pro table allocation. In this sense, such mechanisms are prime candidates to be designed using multi-armed bandit techniques. However, a naive application of multi-armed bandit algorithms would not take into account the strategic considerations of the players— players might manipulate their bids (which determine the auction's revenue) in a way as to maximize their own utility. Hence, we consider the natural restriction that the auction be truthful. The revenue that we could hope to achieve is the expected revenue of a Vickrey auction that knows the true CTRs, and we define the truthful regret to be the difference between the expected revenue of the auction and this Vickrey revenue. This work sharply characterizes what regret is achievable, under a truthful restriction. We show that this truthful restriction imposes statistical limits on the achievable regret—the achievable regret is ϴ(T2/3), while for traditional bandit algorithms (without the truthful restriction) the achievable regret is ϴ(T1/2) (where T is the number of rounds). We term the extra T1/6 factor, the `price of truthfulness'. [ABSTRACT FROM AUTHOR]

We consider the problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit. The goal is to maximize the revenue generated by these keyword sales, bearing in mind that, as some bidders may eventually exceed their budget, not all keywords should be sold to the highest bidder. We assume that the sequence of keywords (or equivalently, of bids) is revealed on-line. Our concern will be the competitive ratio for this problem versus the off-line optimum. We extend the current literature on this problem by considering the setting where the keywords arrive in a random order. In this setting we are able to achieve a competitive ratio of 1 -ϵ under some mild, but necessary, assumptions. In contrast, it is already known that when the keywords arrive in an adversarial order, the best competitive ratio is bounded away from 1. Our algorithm is motivated by PAC learning, and proceeds in two parts: a training phase, and an exploitation phase. [ABSTRACT FROM AUTHOR]

We study auctions for selling a limited supply of a single commodity in the case where the supply is known in advance and the case it is unknown and must be instead allocated in an online fashion. The latter variant was proposed by Mahdian and Saberi [12] as a model of an important phenomena in auctions for selling Internet advertising: advertising impressions must be allocated as they arrive and the total quantity available is unknown in advance. We describe the Bayesian optimal mechanism for these variants and extend the random sampling auction of Goldberg et al. [8] to address the prior-free case. [ABSTRACT FROM AUTHOR]

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., Engineering and Applied Sciences