Abstract: Algorithmic Mechanism Design attempts to marry computation and incentives, mainly by leveraging monetary transfers between designer and selfish agents involved. This is principally because in absence of money, very little can be done to enforce truthfulness. However, in certain applications, money is unavailable, morally unacceptable or might simply be at odds with the objective of the mechanism. For example, in Combinatorial Auctions (CAs), the paradigmatic problem of the area, we aim at solutions of maximum social welfare but still charge the society to ensure truthfulness. Additionally, truthfulness of CAs is poorly understood already in the case in which bidders happen to be interested in only two different sets of goods. We focus on the design of incentive-compatible CAs without money in the general setting of -minded bidders. We trade monetary transfers with the observation that the mechanism can detect certain lies of the bidders: i.e., we study truthful CAs with verification and without money. We prove a characterization of truthful mechanisms, which makes an interesting parallel with the well-understood case of CAs with money for single-minded bidders. We then give a host of upper bounds on the approximation ratio obtained by either deterministic or randomized truthful mechanisms when the sets and valuations are private knowledge of the bidders. (Most of these mechanisms run in polynomial time and return solutions with (nearly) best possible approximation guarantees.) We complement these positive results with a number of lower bounds (some of which are essentially tight) that hold in the easier case of public sets. We thus provide an almost complete picture of truthfully approximating CAs in this general setting with multi-dimensional bidders.
Recommendations
- An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
- scientific article; zbMATH DE number 2079341
- Truthful randomized mechanisms for combinatorial auctions
- Truthful randomized mechanisms for combinatorial auctions
- Combinatorial auctions with verification are tractable
Cites work
- scientific article; zbMATH DE number 2086678 (Why is no real title available?)
- (Incremental) priority algorithms
- Algorithmic Game Theory
- Algorithmic mechanism design
- Approximately optimal mechanism design via differential privacy
- Approximation techniques for utilitarian mechanism design
- Bundling equilibrium in combinatorial auctions
- Collusion-resistant mechanisms with verification yielding optimal solutions
- Combinatorial auctions with verification are tractable
- Frugality in path auctions
- Global Incentive Constraints in Auction Design
- Implementation with partial verification
- Mathematical Foundations of Computer Science 2005
- Mechanism design with weaker incentive compatibility constraints
- Mechanism design. A linear programming approach.
- On the complexity of approximating \(k\)-set packing
- On the limitations of greedy mechanism design for truthful combinatorial auctions
- Online mechanism design (randomized rounding on the fly)
- Optimal collusion-resistant mechanisms with verification
- Partially Verifiable Information and Mechanism Design
- Price discrimination through communication
- Scheduling without payments
- Truth revelation in approximately efficient combinatorial auctions
- Truthful approximation mechanisms for restricted combinatorial auctions
- Truthfulness flooded domains and the power of verification for mechanism design
- Two Randomized Mechanisms for Combinatorial Auctions
- Utilitarian mechanism design for multiobjective optimization
- When are local incentive constraints sufficient?
- Winner-imposing strategyproof mechanisms for multiple facility location games
Cited in
(7)- From monetary to nonmonetary mechanism design via artificial currencies
- The power of verification for greedy mechanism design
- Approximation guarantee of OSP mechanisms: the case of machine scheduling and facility location
- Efficient money burning in general domains
- Efficient money burning in general domains
- On the limitations of greedy mechanism design for truthful combinatorial auctions
- Mechanisms with monitoring for truthful RAM allocation
This page was built for publication: Combinatorial auctions without money
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q521808)
