Sketching valuation functions

MaRDI QIDQ5743455zbMATH OpenFDO

Authors Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Noam Nisan, Tim Roughgarden, Robert D. Kleinberg

Publication date 10 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=2095197

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Faster and simpler sketches of valuation functions
• Communication complexity of combinatorial auctions with submodular valuations
• Learning submodular functions
• Budget feasible mechanism design, from prior-free to Bayesian
• Testing submodularity and other properties of valuation functions

Cites work

• An analysis of approximations for maximizing submodular set functions—I
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Combinatorial auctions
• Combinatorial auctions with decreasing marginal utilities
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 7051222 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Learning submodular functions
• Mechanism design with a restricted action space
• On maximizing welfare when utility functions are subadditive
• On the computational power of demand queries
• Optimal value of information in graphical models
• Optimization with demand oracles
• Submodularity of influence in social networks: from local to global
• Two Randomized Mechanisms for Combinatorial Auctions
• Welfare guarantees for combinatorial auctions with item bidding

Cited in

(18)

• Gross substitutability: an algorithmic survey
• Economic efficiency requires interaction
• Tight bounds on \(\ell_1\) approximation and learning of self-bounding functions
• Optimization with demand oracles
• Optimal bounds on approximation of submodular and XOS functions by juntas
• Testing coverage functions
• Recognizing coverage functions
• Submodular functions: learnability, structure, and optimization
• Testing submodularity and other properties of valuation functions
• Faster and simpler sketches of valuation functions
• Separating the communication complexity of truthful and nontruthful algorithms for combinatorial auctions
• The Complexity of Partial Function Extension for Coverage Functions
• Approximate F₂-Sketching of Valuation Functions
• The Limitations of Optimization from Samples
• scientific article; zbMATH DE number 7765404 (Why is no real title available?)
• A characterization of the existence of succinct linear representation of subset-valuations
• Universal optimization for non-clairvoyant subadditive joint replenishment
• Universal optimization for non-clairvoyant subadditive joint replenishment

This page was built for publication: Sketching valuation functions

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