Skip to main navigation Skip to search Skip to main content

Multi-Unit Bayesian Auction with Demand or Budget Constraints

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Abstract

We consider the problem of revenue maximization on multi-unit auctions where items are distinguished by their relative values; any pair of items has the same ratio of values to all buyers. As is common in the study of revenue maximizing problems, we assume that buyers' valuations are drawn from public known distributions and they have additive valuations for multiple items. Our problem is well motivated by sponsored search auctions, which made money for Google and Yahoo! in practice. In this auction, each advertiser bids an amount bi to compete for ad slots on a web page. The value of each ad slot corresponds to its click-through-rate, and each buyer has her own per-click valuations, which is her private information. Obviously, a strategic bidder may bid an amount that is different with her true valuation to improve her utility. Our goal is to design truthful mechanisms avoiding this misreporting. We develop the optimal (with maximum revenue) truthful auction for a relaxed demand model (where each buyer i wants at most di items) and a sharp demand model (where buyer i wants exactly di items). We also find an auction that always guarantees at least half of the revenue of the optimal auction when the buyers are budget constrained. Moreover, all of the auctions we design can be computed efficiently, that is, in polynomial time. © 2014 Wiley Periodicals, Inc.
Original languageEnglish
Pages (from-to)355-368
JournalComputational Intelligence
Volume32
Issue number3
DOIs
Publication statusPublished - 1 Aug 2016
Externally publishedYes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Research Keywords

  • sponsored search, algorithmic game theory, mechanism design, approximation

Fingerprint

Dive into the research topics of 'Multi-Unit Bayesian Auction with Demand or Budget Constraints'. Together they form a unique fingerprint.

Cite this