Knapsack auction
- 3 min read
- 3 chapters
Explore on Lably
ToursExplore Lably’s 3D toursAn example application of a knapsack auction is auctioning broadcast time among advertisers. Here, the items are the time units (e.g., seconds). Each advertiser has an adversitement of a different length (different number of seconds) and a different value for an advertisement. The goal is to select a subset of advertisements to serve in a time slot of a specific length to maximize the total value.
Notation
There are m identical items and n different bidders. The preferences of each bidder i are given by two numbers:
- A demand si - an integer that determines how many items this bidder wants. The bidder needs precisely this number of items and has no use for more or fewer items.
- A value vi - a number that determines how much money the bidder expects to gain from receiving exactly si items.
A feasible outcome of the auction is a subset W of winning bidders, such that their total demand is at most m: . The value of a set W of winners is the sum of values of the winners: . The goal is to find a feasible set of winners with a maximum total value.
In the broadcast time example, if there are 5 minutes allocated for advertisements, then m=300 (the number of seconds), n=the number of potential advertisers, si=the length of i's advertisement in seconds, and vi=the money that i expects to gain if his advertisement is broadcast.
Sign in to keep reading
2 more chapters are free with a Lably account.
Baseline solutions
If the demands and values of all bidders are publicly known, then the problem can be solved by any algorithm for the knapsack problem. The problem is NP-hard, but it has efficient constant-factor approximation algorithms as well as an FPTAS. In practice, usually the demands si are publicly known (e.g., the length of the advertisement of each advertiser must be known), but the valuations vi are the private information of the bidders. Therefore, the auction mechanism should incentivize the bidders to reveal their true valuations.
The VCG auction is a truthful mechanism that can be used to maximize the sum of values while incentivizing agents to reveal their true values. However, it only works if the outcome maximizes the values; it does not work with approximations (if the outcome is only approximately optimal, then VCG is no longer truthful). Finding the optimal outcome cannot be done in polynomial time unless P=NP. This raises the question: are there truthful mechanisms that work in polynomial time and attain an approximately-optimal outcome?
Truthful approximation mechanisms
Mu'alem and Nisan gave the first affirmative answer to this question: they showed that combining two greedy algorithms yields a truthful 2-factor approximation mechanism.
Briest, Krysta and Vocking improved this result by showing a truthful FPTAS.
Dutting, Gkatzelis and Roughgarden presented a truthful deferred-acceptance auction that attains an O(log m) approximation, and proved that no deferred-acceptance auction can achieve a better approximation. This shows a separation between the general class of truthful auctions and the sub-class of deferred-acceptance auctions.