Better approximation for interdependent SOS valuations

DOI10.1007/978-3-031-22832-2_13MaRDI QIDQ6167251zbMATH OpenOpenAlexFDO

Authors Pinyan Lu, Enze Sun, Chenghan Zhou

Publication date 4 August 2023

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.06507

zbMATH Keywords

approximation algorithmscombinatorial auctionmechanism design

Mathematics Subject Classification ID

Approximation algorithms (68W25) Mechanism design theory (91B03) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: Submodular over signal (SOS) defines a family of interesting functions for which there exist truthful mechanisms with constant approximation to the social welfare for agents with interdependent valuations. The best-known truthful auction is of $4$-approximation and a lower bound of 2 was proved. We propose a new and simple truthful mechanism to achieve an approximation ratio of 3.315.

Recommendations

• Auctions with interdependence and SOS: improved approximation
• Combinatorial auctions with interdependent valuations: SOS to the rescue
• Approximation in mechanism design with interdependent values
• Limitations of randomized mechanisms for combinatorial auctions
• Limitations of randomized mechanisms for combinatorial auctions

Cites work

• A Theory of Auctions and Competitive Bidding
• Auctions with interdependence and SOS: improved approximation
• Efficient assignment with interdependent values
• Efficient Auctions
• Efficient Design with Interdependent Valuations
• Implementation with interdependent valuations
• Incentives in Teams
• Mechanism design. A linear programming approach.
• Prior-free clock auctions for bidders with interdependent values
• Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information

Cited in

(3)

• Combinatorial auctions with interdependent valuations: SOS to the rescue
• Fair division with interdependent values
• Fair division with interdependent values

This page was built for publication: Better approximation for interdependent SOS valuations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167251)