Part ofa series on
Auctions
Types
All-pay Chinese Bidding fee Dollar Amsterdam Anglo-Dutch Barter double Best/not best Brazilian Calcutta Candle Click-box bidding Combinatorial Common value Deferred-acceptance Discriminatory price Double Dutch English Forward French Generalized first-price Generalized second-price Japanese Knapsack Multi-attribute Multiunit No-reserve Rank Reverse Scottish Sealed first-price Simultaneous ascending Single-price Traffic light Uniform price Unique bid Value of revenues Vickrey Vickrey–Clarke–Groves Walrasian Yankee
Bidding
Shading Calor licitantis Cancellation hunt Jump Rigging Sniping Suicide Tacit collusion
Contexts
Algorithms Autos Art Charity Children Players Domain names Flowers Loans Scam Slaves Spectrum Stamps Virginity Wine Wives
Theory
Digital goods Price of anarchy Revenue equivalence Winner's curse
Online
Ebidding Private electronic market Software
v t e

Aknapsack auction is an auction in which several identical items are sold, and there are several bidders with different valuations interested in different amounts of items. The goal is to choose a subset of the bidders with a total demand, at most, the number of items and, subject to that, a maximum total value. Finding this set of bidders requires solving an instance of theknapsack problem, which explains the term "knapsack auction".

An 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 advertisement 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.

There arem identical items andn different bidders. The preferences of each bidderi are given by two numbers:

• A demands_i - 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 valuev_i - a number that determines how much money the bidder expects to gain from receiving exactlys_i items.

Afeasible outcome of the auction is a subsetW ofwinning bidders, such that their total demand is at mostm:${\displaystyle \sum _{i\in W}{s}_i\le m}$. Thevalue of a setW of winners is the sum of values of the winners:${\displaystyle \sum _{i\in W}{v}_i}$. 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, thenm=300 (the number of seconds),n=the number of potential advertisers,s_i=the length ofi's advertisement in seconds, andv_i=the money thati expects to gain if his advertisement is broadcast.

If the demands and values of all bidders are publicly known, then the problem can be solved by any algorithm for theknapsack problem. The problem is NP-hard, but it has efficient constant-factor approximation algorithms as well as anFPTAS. In practice, usually the demandss_i are publicly known (e.g., the length of the advertisement of each advertiser must be known), but the valuationsv_i are the private information of the bidders. Therefore, the auction mechanism should incentivize the bidders to reveal their true valuations.

TheVCG auction is atruthful 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 doesnot 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?

Mu'alem and Nisan gave the first affirmative answer to this question:^[1] they showed that combining twogreedy algorithms yields a truthful 2-factor approximation mechanism.

Briest, Krysta and Vocking^[2] improved this result by showing a truthfulFPTAS.

Dutting, Gkatzelis and Roughgarden^[3] presented a truthfuldeferred-acceptance auction that attains an O(logm) 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.

• Types of auction
• Mechanism design