The power of verification for one-parameter agents

DOI10.1016/j.jcss.2008.10.001zbMath1169.68027OpenAlexW1965047789MaRDI QIDQ1004286

Vincenzo Auletta, Giuseppe Persiano, Paolo Penna, 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

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

Related Items

The Subset Sum game, Strategyproof facility location in perturbation stable instances, Truthful optimization using mechanisms with verification, Optimal collusion-resistant mechanisms with verification, Average-case approximation ratio of scheduling without payments, Combinatorial auctions with verification are tractable, A new lower bound for deterministic truthful scheduling

Cites Work

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