The power of verification for one-parameter agents

DOI10.1016/J.JCSS.2008.10.001zbMATH Open1169.68027OpenAlexW1965047789MaRDI QIDQ1004286FDOQ1004286

Authors V. Auletta, Paolo Penna, Giuseppe Persiano, Roberto De Prisco

Publication date 2 March 2009

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2008.10.001

zbMATH Keywords

mechanism designalgorithmic game theorytheory of algorithms

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Nonnumerical algorithms (68W05) Specification and verification (program logics, model checking, etc.) (68Q60) Other game-theoretic models (91A40)

Recommendations

• Automata, Languages and Programming
• New Constructions of Mechanisms with Verification
• Truthful optimization using mechanisms with verification
• Verifiably truthful mechanisms
• Approximation and Online Algorithms

Cites work

• Algorithmic mechanism design (extended abstract)
• Algorithms – ESA 2005
• Algorithms, games, and the internet
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Implementation with partial verification
• Optimal Auction Design
• Routing selfish unsplittable traffic
• STACS 2005
• Setting lower bounds on truthfulness (extended abstract)
• Worst-case equilibria

Cited in

(17)

• On scheduling mechanisms beyond the worst case
• Combinatorial auctions with verification are tractable
• The power of verification for greedy mechanism design
• Truthful optimization using mechanisms with verification
• Verifiably truthful mechanisms
• Automata, Languages and Programming
• Computer-aided verification for mechanism design
• Truthfulness flooded domains and the power of verification for mechanism design
• Fast payment schemes for truthful mechanisms with verification
• Average-case approximation ratio of scheduling without payments
• New Constructions of Mechanisms with Verification
• A new lower bound for deterministic truthful scheduling
• Approximation and Online Algorithms
• Optimal collusion-resistant mechanisms with verification
• Optimal on-line allocation rules with verification
• Strategyproof facility location in perturbation stable instances
• The Subset Sum game

This page was built for publication: The power of verification for one-parameter agents

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