Multi-Unit Bayesian Auction with Demand or Budget Constraints

Multi-Unit Bayesian Auction with Demand or Budget Constraints

0.00 Avg rating0 Votes
Article ID: iaor20163064
Volume: 32
Issue: 3
Start Page Number: 355
End Page Number: 368
Publication Date: Aug 2016
Journal: Computational Intelligence
Authors: , , ,
Keywords: demand, investment, combinatorial optimization, economics, marketing, internet, advertising
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.

Reviews

Required fields are marked *. Your email address will not be published.