Knapsack auction

Last updated October 30, 2023

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 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 s_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 value v_i - a number that determines how much money the bidder expects to gain from receiving exactly s_i items.

A feasible outcome of the auction is a subset W of winning bidders, such that their total demand is at most m: $\sum _{i\in W}s_{i}\leq m$ . The value of a set W of winners is the sum of values of the winners: $\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, 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.

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 s_i are publicly known (e.g., the length of the advertisement of each advertiser must be known), but the valuations v_i 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:^[1] they showed that combining two greedy algorithms yields a truthful 2-factor approximation mechanism.

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

Dutting, Gkatzelis and Roughgarden^[3] 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.

Related Research Articles

In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about what the others do, you fare best or at least not worse by being truthful.

A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction. Bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins but the price paid is the second-highest bid. This type of auction is strategically similar to an English auction and gives bidders an incentive to bid their true value. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893. In 1797 Johann Wolfgang von Goethe sold a manuscript using a sealed-bid, second-price auction.

A Japanese auction is a dynamic auction format. It proceeds in the following way.

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.

The revelation principle is a fundamental principle in mechanism design. It states that if a social choice function can be implemented by an arbitrary mechanism, then the same function can be implemented by an incentive-compatible-direct-mechanism with the same equilibrium outcome (payoffs).

A Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other bidders. The auction system assigns the items in a socially optimal manner: it charges each individual the harm they cause to other bidders. It gives bidders an incentive to bid their true valuations, by ensuring that the optimal strategy for each bidder is to bid their true valuations of the items; it can be undermined by bidder collusion and in particular in some circumstances by a single bidder making multiple bids under different names. It is a generalization of a Vickrey auction for multiple items.

Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In some markets, prices may be used to induce the desired outcomes — these markets are the study of auction theory. In other markets, prices may not be used — these markets are the study of matching theory.

The generalized second-price auction (GSP) is a non-truthful auction mechanism for multiple items. Each bidder places a bid. The highest bidder gets the first slot, the second-highest, the second slot and so on, but the highest bidder pays the price bid by the second-highest bidder, the second-highest pays the price bid by the third-highest, and so on. First conceived as a natural extension of the Vickrey auction, it conserves some of the desirable properties of the Vickrey auction. It is used mainly in the context of keyword auctions, where sponsored search slots are sold on an auction basis. The first analyses of GSP are in the economics literature by Edelman, Ostrovsky, and Schwarz and by Varian. It is used by Google's AdWords technology and Facebook.

A sponsored search auction (SSA), also known as a keyword auction, is an indispensable part of the business model of modern web hosts. It refers to results from a search engine that are not output by the main search algorithm, but rather clearly separate advertisements paid for by third parties. These advertisements are typically related to the terms for which the user searched. They come in the form of a link and some information, with the hope that a search user will click on the link and buy something from the advertiser. In sponsored search auctions, there are typically some fixed number of slots for advertisements and more advertisers that want these slots than there are slots. The advertisers have different valuations for these slots and slots are a scarce resource, so an auction is done to determine how the slots will be assigned.

In mechanism design, a Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially-optimal solution. It is a generalization of a Vickrey–Clarke–Groves auction. A VCG auction performs a specific task: dividing items among people. A VCG mechanism is more general: it can be used to select any outcome out of a set of possible outcomes.

In mechanism design, monotonicity is a property of a social choice function. It is a necessary condition for being able to implement the function using a strategyproof mechanism. Its verbal description is:

If changing one agent's type changes the outcome under the social choice function, then the resulting difference in utilities of the new and original outcomes evaluated at the new type of this agent must be at least as much as this difference in utilities evaluated at the original type of this agent.

A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms and prior-independent mechanisms.

In mechanism design, an agent is said to have single-parameter utility if his valuation of the possible outcomes can be represented by a single number. For example, in an auction for a single item, the utilities of all agents are single-parametric, since they can be represented by their monetary evaluation of the item. In contrast, in a combinatorial auction for two or more related items, the utilities are usually not single-parametric, since they are usually represented by their evaluations to all possible bundles of items.

A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of these variables.

A prior-free mechanism (PFM) is a mechanism in which the designer does not have any information on the agents' valuations, not even that they are random variables from some unknown probability distribution.

A Prior-independent mechanism (PIM) is a mechanism in which the designer knows that the agents' valuations are drawn from some probability distribution, but does not know the distribution.

Bayesian-optimal pricing is a kind of algorithmic pricing in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a Bayesian-optimal mechanism, in which the price is determined in advance without collecting actual buyers' bids.

A deferred-acceptance auction (DAA) is an auction in which the allocation is chosen by repeatedly rejecting the least attractive bids. It is a truthful mechanism with strategic properties that make it particularly suitable to complex auctions such as the radio spectrum reallocation auction. An important advantage of DAA over the more famous VCG auction is that DAA is immune to manipulations by coalitions of bidders, while VCG is immune to manipulations only by individual bidders.

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

The Partial Allocation Mechanism(PAM) is a mechanism for truthful resource allocation. It is based on the max-product allocation - the allocation maximizing the product of agents' utilities (also known as the Nash-optimal allocation or the Proportionally-Fair solution; in many cases it is equivalent to the competitive equilibrium from equal incomes). It guarantees to each agent at least 0.368 of his/her utility in the max-product allocation. It was designed by Cole, Gkatzelis and Goel.

References

↑ Mu'alem, Ahuva; Nisan, Noam (2008-11-01). "Truthful approximation mechanisms for restricted combinatorial auctions". Games and Economic Behavior. Special Issue in Honor of Michael B. Maschler. 64 (2): 612–631. doi:10.1016/j.geb.2007.12.009. ISSN 0899-8256.
↑ Briest, Patrick; Krysta, Piotr; Vöcking, Berthold (2011-01-01). "Approximation Techniques for Utilitarian Mechanism Design". SIAM Journal on Computing. 40 (6): 1587–1622. doi:10.1137/090772988. ISSN 0097-5397.
↑ Dütting, Paul; Gkatzelis, Vasilis; Roughgarden, Tim (2014-06-01). "The performance of deferred-acceptance auctions" (PDF). Proceedings of the fifteenth ACM conference on Economics and computation. EC '14. New York, NY, USA: Association for Computing Machinery. pp. 187–204. doi:10.1145/2600057.2602861. ISBN 978-1-4503-2565-3. S2CID 1950202.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Mu'alem, Ahuva; Nisan, Noam (2008-11-01). "Truthful approximation mechanisms for restricted combinatorial auctions". Games and Economic Behavior. Special Issue in Honor of Michael B. Maschler. 64 (2): 612–631. doi:10.1016/j.geb.2007.12.009. ISSN 0899-8256.

[2] Briest, Patrick; Krysta, Piotr; Vöcking, Berthold (2011-01-01). "Approximation Techniques for Utilitarian Mechanism Design". SIAM Journal on Computing. 40 (6): 1587–1622. doi:10.1137/090772988. ISSN 0097-5397.

[3] Dütting, Paul; Gkatzelis, Vasilis; Roughgarden, Tim (2014-06-01). "The performance of deferred-acceptance auctions" (PDF). Proceedings of the fifteenth ACM conference on Economics and computation. EC '14. New York, NY, USA: Association for Computing Machinery. pp. 187–204. doi:10.1145/2600057.2602861. ISBN 978-1-4503-2565-3. S2CID 1950202.

[1]

[2]

[3]