Bribeproof Mechanisms for Two-Values Domains

DOI10.1007/978-3-662-53354-3_23MaRDI QIDQ2819466zbMATH OpenOpenAlexFDO

Authors Matúš Mihalák, Paolo Penna, Peter Widmayer

Publication date 29 September 2016

Published in Algorithmic Game Theory (Search for Journal in Brave)

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

zbMATH Keywords

binary allocationbribeproof mechanismmonetary transferpath auctiontwo-values domains

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: Schummer (Journal of Economic Theory 2000) introduced the concept of bribeproof mechanism which, in a context where monetary transfer between agents is possible, requires that manipulations through bribes are ruled out. Unfortunately, in many domains, the only bribeproof mechanisms are the trivial ones which return a fixed outcome. This work presents one of the few constructions of non-trivial bribeproof mechanisms for these quasi-linear environments. Though the suggested construction applies to rather restricted domains, the results obtained are tight: For several natural problems, the method yields the only possible bribeproof mechanism and no such mechanism is possible on more general domains.

Recommendations

• On the constancy of bribe-proof solutions
• Truthfulness flooded domains and the power of verification for mechanism design
• The Verifiability of Two-Party Protocols
• Bribe-proof rules in the division problem
• On the complexity of bribery with distance restrictions
• Partially Verifiable Information and Mechanism Design
• Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
• Collusion-resistant mechanisms with verification yielding optimal solutions

Cites work

• A deterministic truthful PTAS for scheduling related machines
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• Algorithmic mechanism design
• Bribeproof Mechanisms for Two-Values Domains
• Collusion-resistant mechanisms for single-parameter agents
• Collusive dominant-strategy truthfulness
• Eliciting preferences to assign positions and compensation
• Fair and group strategy-proof good allocation with money
• Group strategyproof cost sharing: the role of indifferences
• scientific article; zbMATH DE number 3670138 (Why is no real title available?)
• Improved Lower Bounds for Non-utilitarian Truthfulness
• Incremental cost sharing: Characterization by coalition strategy-proofness
• Manipulation through bribes
• Multi-unit auctions: beyond Roberts
• On the constancy of bribe-proof solutions
• Optimal Auction Design
• Optimal collusion-resistant mechanisms with verification
• Optimal lower bounds for anonymous scheduling mechanisms
• Pairwise strategy-proofness and self-enforcing manipulation
• Setting lower bounds on truthfulness (extended abstract)
• Strategy-proof and efficient allocation of an indivisible good on finitely restricted preference domains
• The performance of deferred-acceptance auctions
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity

Cited in

(4)

• On the constancy of bribe-proof solutions
• Manipulation through bribes
• Collusion-proof mechanisms for multi-unit procurement
• Bribeproof Mechanisms for Two-Values Domains

This page was built for publication: Bribeproof Mechanisms for Two-Values Domains

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