Quantum Auctions

Hogg, Tad ; Chen, Kay- Yut ; Harsha, Pavithra

HP Development Company

关键词: quantam information;    incentive design;    economics;    game theory;   

RP-ID  :  HPL-2013-87

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We present a quantum auction protocol using superpositionsto represent bids and distributed search to identify the winner(s). Measuring the final quantum state gives the auction outcome while simultaneously destroying the superposition. Thus non-winning bids are never revealed. Participants can use entanglement to arrange for correlations among their bids, with the assurance that this entanglement is not observable by others. The protocol is useful for information hiding applications, such as partnership bidding with allocative externality orconcerns about revealing bidding preferences. The protocol applies to a variety of auction types, e.g., first or second price, and to auctionsinvolving either a single item or arbitrary bundles of items (i.e., combinatorial auctions). We analyze the game-theoretical behavior of thequantum protocol for the simple case of a sealed-bid quantum, and show how a suitably designed adiabatic search reduces the possibilities for bidders to game the auction. This design illustrates how incentive rather that computational constraints affect quantum algorithm choices.