Approximate composable truthful mechanism design

DOI10.1016/J.TCS.2016.02.025MaRDI QIDQ344791zbMATH OpenOpenAlexFDO

Authors Deshi Ye, Guochuan Zhang

Publication date 24 November 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.02.025

zbMATH Keywords

approximation algorithmsknapsack auctionmechanism design

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Truthful approximation mechanisms for restricted combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Algorithms and Computation
• Bounding the payment of approximate truthful mechanisms
• scientific article; zbMATH DE number 2079341
• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• A generic truthful mechanism for combinatorial auctions

Cites work

• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Algorithmic mechanism design (extended abstract)
• An Online Mechanism for Resource Allocation and Pricing in Clouds
• Approximate algorithms to pack rectangles into several strips
• Approximate truthful mechanism design for two-dimensional orthogonal knapsack problem
• Approximating the non-contiguous multiple organization packing problem
• Approximation algorithms for multiple strip packing
• Approximation techniques for utilitarian mechanism design
• Computationally-feasible truthful auctions for convex bundles
• scientific article; zbMATH DE number 1305407 (Why is no real title available?)
• scientific article; zbMATH DE number 1418266 (Why is no real title available?)
• scientific article; zbMATH DE number 6297731 (Why is no real title available?)
• scientific article; zbMATH DE number 6297764 (Why is no real title available?)
• Maximizing the total profit of rectangles packed into a rectangle
• Online multiple-strip packing
• Parameterized approximation scheme for the multiple knapsack problem
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• STACS 2004
• STACS 2005
• The multiple subset sum problem
• There is no EPTAS for two-dimensional knapsack
• Truth revelation in approximately efficient combinatorial auctions
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Truthful approximation mechanisms for restricted combinatorial auctions
• Truthful Mechanisms via Greedy Iterative Packing

Cited in

(10)

• Generalized assignment problem: truthful mechanism design without money
• No truthful mechanism can be better than n approximate for two natural problems
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Approximate truthful mechanism design for two-dimensional orthogonal knapsack problem
• scientific article; zbMATH DE number 6519655 (Why is no real title available?)
• Truthful Unification Framework for Packing Integer Programs with Choices
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Characterizing Truthful Multi-armed Bandit Mechanisms
• Mechanism design for the truthful elicitation of costly probabilistic estimates in distributed information systems
• Gradient-based local formulations of the Vickrey-Clarke-Groves mechanism for truthful minimization of social convex objectives

This page was built for publication: Approximate composable truthful mechanism design

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