knapsack auctions
12385501
CS 364 A Algorithmic Game Theory Lecture 4 Algorithmic Mechanism Design
In a knapsack auction, each bidder i has a publicly known size wi (e.g. the duration of a TV ad) and a private valuation (e.g. a company's willingness to pay for its ad being shown during the Super Bowl) The seller has a capacity W (e.g. the length of a commercial break) The feasible set X is defined as the 0 1 n vectors (x1, xn) such that n i=1wixi W (As usual, xi 1 indicates that i is a winning bidder. Other situations such knapsack auctions model include bidders who want files stored on a shared server, data streams sent through a shared communication channel, or processes to be executed on a shared supercomputer. (When there is a shared resource with limited capacity, you have a Knapsack problem. Note that k item auctions (k identical copies of a good, one per customer) is the special case where wi 1 for all i and W k. Here, different bidders can have different sizes. Let's try to design an awesome auction using our two step design paradigm. Recall that we first assume without justification that bids equal values and then decide on our allocation rule. Then we pay the piper and devise a payment rule that extends the allocation rule to a DSIC mechanism. c (c)2013, Tim Roughgarden. These lecture notes are provided for personal use only. See my book Twenty Lectures on Algorithmic Game Theory, published by Cambridge University Press, for the latest version. +Department of Computer Science, Stanford University, 462 Gates Building, 353 Serra Mall, Stanford, CA 94305. Email: tim@cs.stanford.edu.
Knapsack Auctions
6472299
Subsidies, knapsack auctions and Dantzig's greedy heuristic
A budget constrained buyer wants to purchase items from a shortlisted set. Items are differentiated by quality and sellers have private reserve prices for their items. Sellers quote prices strategically, inducing a knapsack game. The buyeraEUR(tm)s problem is to select a subset of maximal quality. We propose a buying mechanism which can be viewed as a game theoretic extension of DantzigaEUR(tm)s greedy heuristic for the classic knapsack problem. We use Monte Carlo simulations to analyse the performance of our mechanism. Finally, we discuss how the mechanism can be applied to award R&D subsidies.
Ludwig Ensthaler Thomas Giebe
2733106
Knapsack auctions
We consider a game theoretic knapsack problem that has application to auctions for selling advertisements on Internet search engines. Consider n agents each wishing to place an object in the knapsack. Each agent has a private valuation for having their object in the knapsack and each object has a publicly known size. For this setting, we consider the design of auctions in which agents have an incentive to truthfully reveal their private valuations. Following the framework of Goldberg et al. [10] we look to design an auction that obtains a constant fraction of the profit obtainable by a natural optimal pricing algorithm that knows the agents' valuations and object sizes.We give an auction that obtains a constant factor approximation in the non trivial special case where the knapsack has unlimited capacity. We then reduce the limited capacity version of the problem to the unlimited capacity version via an approximately efficient auction (i.e. one that maximizes the social welfare) This reduction follows from generalizable principles.
SODA '06
Gagan Aggarwal Jason D Hartline
17519419
A Knapsack Based Approach to Bidding in Ad Auctions
We model the problem of bidding in ad auctions as a penalized multiple choice knapsack problem (PMCKP) a combination of the multiple choice knapsack problem (MCKP) and the penalized knapsack problem (PKP) [1] We present two versions of PMCKPGlobalPMCKP and LocalPMCKP, together with a greedy algorithm that solves the linear relaxation of a GlobalPMCKP optimally. We also develop a greedy heuristic for solving LocalPMCKP. Although our heuristic is not optimal, we show that it performs well in TAC AA games.
ECAI
Jordan Berg Amy Greenwald Victor Naroditskiy Eric Sodomka
49294204
Frugal Auction Design for Set Systems: Vertex Cover and Knapsack
We study mechanism design for procurement auctions in which the goal is to buy a subset of items or hire a team of providers. In order to measure the efficiency of a mechanism, one defines an appropriate benchmark which denotes a reasonable expectation of the payments and defines the overpayment of a mechanism based on the benchmark. This ratio is called the \em frugality ratio of the mechanism. Procurement auctions are well studied and benchmarks proposed for these auctions have evolved over a sequence of papers \citearcher2007frugal,chen2010frugal,elkind2007frugality,karlinbeyond,kempe2010frugal. In this work, we introduce a newer benchmark, and based on that, study classic procurement auctions. Our benchmark addresses critical issues raised by the unintuitive behavior of the previous benchmarks. We show two attractive properties for our benchmark which have been lacking in the previous proposals: \em monotonicity and \em smoothness. Based on our benchmark, we provide positive results for vertex cover and knapsack auctions. Prior to this work, \kempefrugal\citekempe2010frugal propose a constant approximation mechanism for vertex cover auctions. However, their analysis suffers from an error. We give a correct analysis to the mechanism of \kempefrugal\citekempe2010frugal with respect to our benchmark. In particular, we prove their mechanism is optimal up to a constant factor. Our analysis is different from what \kempefrugal\citekempe2010frugal propose. We also study the knapsack auctions and give a truthful mechanism for such auctions with a bounded frugality ratio. We show that this is almost tight by presenting a lower bound on the frugality ratio of any truthful mechanism for such auctions. All our results depend on both properties of the benchmark.
EC
Mohammad Taghi Hajiaghayi M Reza Khani Saeed Seddighin
125949205
The Second Price Knapsack Problem: Near Optimal Real Time Bidding in Internet Advertisement
In many online advertisement (ad) exchanges, ad slots are each sold via a separate second price auction. This paper considers the bidder's problem of maximizing the value of ads they purchase in these auctions, subject to budget constraints. This 'second price knapsack' problem presents challenges when devising a bidding strategy because of the uncertain resource consumption: bidders win if they bid the highest amount, but pay the second highest bid, unknown a priori. This is in contrast to the traditional online knapsack problem, where posted prices are revealed when ads arrive, and for which there exists a rich literature of primal and dual algorithms. The main results of this paper establish general methods for adapting these primal and dual online knapsack selection algorithms to the second price knapsack problem, where the prices are revealed only after bidding. In particular, a methodology is provided for converting deterministic and randomized knapsack selection algorithms into second price knapsack bidding strategies, that purchase ads through an equivalent set of criteria and thereby achieve the same competitive guarantees. This shows a connection between the traditional knapsack selection algorithm and second price auction bidding algorithms, that has not previously been leveraged. Empirical analysis on real ad exchange data verifies the usefulness of this method, and gives examples where it can outperform state of the art techniques.
Jonathan Amar Nicholas Renegar
909248
Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems
We consider the budget constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple choice) knapsack problem We design both deterministic and randomized algorithms for the online (multiple choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e. without knowledge) of other bidders' prices and/or clickthrough rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder.
WINE
Yunhong Zhou Deeparnab Chakrabarty Rajan M Lukose
3669970
The Performance of Deferred Acceptance Auctions
Deferred acceptance auctions are mechanisms whose allocation rule can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal recently introduced these auctions and proved that they satisfy remarkable incentive guarantees: in addition to being dominant strategy and incentive compatible, they are weakly group strategyproof and can be implemented by ascending clock auctions. Neither forward greedy mechanisms nor the VCG mechanism generally possess any of these additional incentive properties. The goal of this paper is to initiate the study of deferred acceptance auctions from an approximation standpoint. We study what fraction of the optimal social welfare can be guaranteed by these auctions in two canonical problems, knapsack auctions and combinatorial auctions with single minded bidders. For knapsack auctions, we prove a separation between deferred acceptance auctions and arbitrary dominant strategy incentive compatible mechanisms. For combinatorial auctions with single minded bidders.
Math. Oper. Res.
Paul Dutting Vasilis Gkatzelis Tim Roughgarden
15475326
Online knapsack problem and budgeted truthful bipartite matching
Two related online problems: knapsack and truthful bipartite matching are considered. For these two problems, the common theme is how to 'match' an arriving left vertex in an online fashion with any of the available right vertices, if at all, so as to maximize the sum of the value of the matched edges, subject to satisfying a sum weight constraint on the matched left vertices. Assuming that the left vertices arrive in an uniformly random order (secretary model) two almost similar algorithms are proposed for the two problems, that are 2e competitive and 24 competitive, respectively. The proposed online bipartite matching algorithm is also shown to be truthful: there is no incentive for any left vertex to misreport its bid/weight. Direct applications of these problems include job allocation with load balancing, generalized adwords, crowdsourcing auctions, and matching wireless users to cooperative relays in device to device communication enabled cellular network.
IEEE INFOCOM 2017 IEEE Conference on Computer Communications
Rahul Vaze
35853994
Budget constrained bidding in keyword auctions and online knapsack problems
We consider the budget constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple choice) knapsack problem. We design both deterministic and randomized algorithms for the online (multiple choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e. without knowledge) of other bidders' prices and/or click through rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder.
WWW
Yunhong Zhou Deeparnab Chakrabarty Rajan M Lukose