Complexity of Mechanism Design with Signaling Costs

In mechanism design, it is generally assumed that an agent can submit any report at zero cost (with the occasional further restriction that certain types can not submit certain reports). More generally, however, an agent of type Θ may be able to report Θ1 but only at a cost c(Θ, Θ1). This cost may reflect the effort the agent would have to expend to be indistinguishable from an agent that truthfully reports Θ1. Even more generally, the possible reports (or signals) may not directly correspond to types. In this paper, we consider the complexity of determining whether particular social choice functions can be implemented in this context.

• Publication year

  2015

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2015-05-04

• Fields of study

  Computer Science, Economics

• Identifiers
  DOI 10.65109/rjyl9681
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Algorithms for strategyproof classification

  2012cited by this paper
• Mechanism design: from partial to probabilistic verification

  2012cited by this paper
• Mechanism design with partial verification and revelation principle

  2010cited by this paper
• The security of machine learning

  2010cited by this paper
• Incentive compatible regression learning

  2008cited by this paper
• Alternatives to truthfulness are hard to recognize

  2008influential reference
• Optimal Screening with Costly Misrepresentation.

  2007cited by this paper
• Reducing mechanism design to algorithm design via machine learning

  2007cited by this paper
• Adversarial classification

  2004cited by this paper
• Self-interested automated mechanism design and implications for optimal combinatorial auctions

  2004cited by this paper
• Complexity of Mechanism Design

  2002cited by this paper
• The Minimum Satisfiability Problem

  1994cited by this paper
• Partially Verifiable Information and Mechanism Design

  1986cited by this paper
• Job Market Signaling

  1973cited by this paper
• Mathematics

  1935cited by this paper

• Designing Rules for Choosing a Winner in a Debate

  2025cites this paper
• Persuading a Credible Agent

  2024cites this paper
• Sequential Decision Making With Information Asymmetry

  2022cites this paper
• Polynomial-Time Optimal Equilibria with a Mediator in Extensive-Form Games

  2022cites this paper
• Incentive-Aware PAC Learning

  2021cites this paper
• The Revelation Principle for Mechanism Design with Signaling Costs

  2021influential citation
• Automated Mechanism Design for Classification with Partial Verification

  2021influential citation
• Automated Dynamic Mechanism Design

  2021cites this paper
• Automated Mechanism Design for Strategic Classification: Abstract for KDD'21 Keynote Talk

  2021cites this paper
• The Role of Randomness and Noise in Strategic Classification

  2020cites this paper
• Classification with Strategically Withheld Data

  2020cites this paper
• Automated Mechanism Design with Partial Verification

  2020cites this paper
• Distinguishing Distributions When Samples Are Strategically Transformed

  2019cites this paper
• When Samples Are Strategically Selected

  2019cites this paper
• Summary : The Role of Randomness and Noise in Strategic Classification

  2019cites this paper
• The Disparate Effects of Strategic Manipulation

  2018cites this paper
• The Revelation Principle for Mechanism Design with Reporting Costs

  2016cites this paper