On the approximability of budget feasible mechanisms

zbMATH Open1377.90113arXiv1007.3801MaRDI QIDQ5365073FDOQ5365073

Authors: Ning Chen, Pinyan Lu, N. V. Gravin 

Publication date: 29 September 2017

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

Recommendations

• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• Budget feasible mechanism design, from prior-free to Bayesian
• Worst-case mechanism design via Bayesian analysis
• Simple and efficient budget feasible mechanisms for monotone submodular valuations
• On budget-feasible mechanism design for symmetric submodular objectives

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (27)

• Approximation Schemes for Multi-Budgeted Independence Systems
• Selling privacy at auction
• An online sequential procurement mechanism under uncertain demands in multi-cloud environment
• A simple mechanism for a budget-constrained buyer
• Budget feasible mechanism design, from prior-free to Bayesian
• Hardness of and approximate mechanism design for the bike rebalancing problem
• Tight revenue gaps among multiunit mechanisms
• Budget feasible mechanisms for procurement auctions with divisible agents
• Budget feasible mechanisms for experimental design
• Coverage, matching, and beyond: new results on budgeted mechanism design
• Auction mechanisms for allocating subsidies for carbon emissions reduction: an experimental investigation
• Almost budget-balanced VCG mechanisms to assign multiple objects
• Auction design for value maximizers with budget and return-on-spend constraints
• Partial allocations in budget-feasible mechanism design: bridging multiple levels of service and divisible agents
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• Budget-feasible mechanisms for proportionally selecting agents from groups
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Budget feasible procurement auctions
• Simple and efficient budget feasible mechanisms for monotone submodular valuations
• Ex-post optimal knapsack procurement
• On budget-feasible mechanism design for symmetric submodular objectives
• Worst-case mechanism design via Bayesian analysis
• Budget-feasible Sybil-proof mechanisms for crowdsensing
• Budget-feasible Sybil-proof mechanisms for crowdsensing
• Budget feasible mechanisms on matroids
• Budget feasible mechanisms on matroids
• Mechanisms for dual-role-facility location games: truthfulness and approximability

This page was built for publication: On the approximability of budget feasible mechanisms

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