Knapsack auction

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

A knapsack 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 the knapsack 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.

A knapsack 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 the knapsack 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.

How it works

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, s i =the length of i 's advertisement in seconds, and v i =the money that i expects to gain if his advertisement is broadcast. 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?

Text derived from https://en.wikipedia.org/w/index.php?oldid=1346211227 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001346211227 · captured 1774876519.0 · version history

Cite this page as: encyclopegia.org, “Knapsack auction”, snapshot enwiki-001346211227. https://encyclopegia.org/a/knapsack-auction

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.