Achieving Budget-Balance with Vickrey-Based Payment Schemes in Combinatorial Exchanges Export

@techreport{citeulike:4197120, abstract = {Generalized Vickrey mechanisms have received wide attention in the combinatorial auction design literature because they are efficient and strategy-proof. However, it is well known that it is impossible for an exchange, with multiple buyers and sellers and voluntary participation, to be efficient and budget-balanced, even relaxing dominant strategy requirements. Except for special cases, a market-maker in an efficient exchangemust make more payments than it collects. Taking a constructive approach, we clear exchanges to maximize reported surplus, and explore the efficiency effects of differentbudget-balanced payment rules. The payment rules are formulated to minimize the distance to Vickrey payments, under different metrics. Different rules lead to differentlevels of truth-revelation, and therefore efficiency. Experimental and theoretical analysis suggest a simple Threshold scheme, which gives surplus to agents with payments furtherthan a certain threshold value from their Vickrey payments, has good properties. The scheme exploits agent uncertainty about bids from other agents to reduce manipulationopportunities.}, author = {Parkes, David and Kalagnanam, Jayant and Eso, Marta}, citeulike-article-id = {4197120}, day = {23}, institution = {IBM Research}, keywords = {balance, budget, design, mechanis, payment, vcg}, month = {October}, number = {RC 22218 W0110-065}, posted-at = {2009-03-20 09:36:11}, priority = {2}, title = {Achieving Budget-Balance with Vickrey-Based Payment Schemes in Combinatorial Exchanges}, year = {2001} }

TY - RPRT ID - citeulike:4197120 L3 - citeulike-article-id:4197120 N2 - Generalized Vickrey mechanisms have received wide attention in the combinatorial auction design literature because they are efficient and strategy-proof. However, it is well known that it is impossible for an exchange, with multiple buyers and sellers and voluntary participation, to be efficient and budget-balanced, even relaxing dominant strategy requirements. Except for special cases, a market-maker in an efficient exchangemust make more payments than it collects. Taking a constructive approach, we clear exchanges to maximize reported surplus, and explore the efficiency effects of differentbudget-balanced payment rules. The payment rules are formulated to minimize the distance to Vickrey payments, under different metrics. Different rules lead to differentlevels of truth-revelation, and therefore efficiency. Experimental and theoretical analysis suggest a simple Threshold scheme, which gives surplus to agents with payments furtherthan a certain threshold value from their Vickrey payments, has good properties. The scheme exploits agent uncertainty about bids from other agents to reduce manipulationopportunities. IS - RC 22218 W0110-065 TI - Achieving Budget-Balance with Vickrey-Based Payment Schemes in Combinatorial Exchanges KW - balance KW - budget KW - design KW - mechanis KW - payment KW - vcg AU - Parkes, David AU - Kalagnanam, Jayant AU - Eso, Marta PY - 2001/10/23/ ER -