TL;DR
This paper investigates the communication cost of ensuring truthful behavior in economic mechanisms. The authors prove a fundamental lower bound showing that implementing incentive-compatible mechanisms can require communication that scales linearly with the number of players, even in simple scenarios. This highlights a significant overhead beyond simply computing the desired outcome.
What Problem Does This Paper Address?
In mechanism design, we often want to achieve a specific social outcome (e.g., selling an item to the highest bidder) while ensuring that self-interested agents report their true preferences. This is known as incentive compatibility. While we can often design mechanisms that are incentive-compatible, the process of computing the necessary payments to achieve this can require significant communication between the agents. This paper quantifies this "communication cost of selfishness," specifically focusing on the overhead incurred when agents need to communicate to determine equilibrium-supporting prices. The authors aim to understand how much additional communication is needed beyond what's required to simply compute the social choice function itself.
Methods
The paper uses tools from communication complexity theory to establish lower bounds on the communication required for incentive compatibility. Key techniques include:
- Fooling Sets: A standard technique in communication complexity where a set of inputs is constructed such that any communication protocol must distinguish between them, leading to a lower bound on the number of bits required.
- Constructing Specific Social-Choice Functions (SCFs): The authors design novel SCFs (like "NOT-TOO-FARk" and "C-PUBLIC-GOODk") that are specifically crafted to exhibit a large gap between the communication needed to compute the outcome and the communication needed to compute both the outcome and the incentive-compatible payments.
- Analyzing Single-Parameter Domains: The research focuses on simplified scenarios where each player's "type" (their valuation) can be represented by a single number. This allows for more concrete analysis and construction of lower bounds.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Linear Overhead is Fundamental: The most striking insight is the proof that the communication overhead for incentive compatibility can be linear in the number of players ($n \cdot x$, where $x$ is the complexity of the outcome). This is a significant result, as it suggests that simply having more participants dramatically increases the communication burden for truthful mechanisms, even in simple settings.
- Simple Domains are Not Simple: The paper demonstrates that this linear overhead is not just an artifact of complex economic scenarios. It holds even in "single-parameter domains" where outcomes are binary (win/lose) and payments are normalized (losers pay zero).
- Trade-off Between Outcome and Payment Complexity: The core of the lower bound proofs lies in constructing SCFs where computing the outcome is cheap (e.g., a few bits per player), but determining the specific payments that make it incentive-compatible requires much more information exchange.
- Specific Economic Problems Have Low Overhead: While the general lower bound is linear, the paper also shows that for some classic problems like single-item auctions and public goods, the overhead is surprisingly small (constant or logarithmic in the number of players). This highlights that the structure of the economic problem matters greatly.
Key Results
- Linear Lower Bound: The paper establishes a lower bound of $\Omega(n \cdot x)$ for the communication overhead of incentive compatibility for certain social-choice functions, where $n$ is the number of players and $x$ is the communication complexity of computing the outcome. This is the first known lower bound of this nature.
- Constant/Logarithmic Upper Bounds for Specific Problems:
- For single-item auctions, the overhead is shown to be at most 3 (constant). For two players, it's even better, $1 + O(\log k)$, where $k$ is the precision of valuations.
- For public goods, the overhead is shown to be at most $2 + \epsilon$ for $n \ge 3$ players, and approximately 2 for $n=2$ players.
- Welfare Maximization: For welfare-maximizing functions, the overhead is shown to be at most $n \cdot k$ (where $k$ is the bit-precision of valuations), but this bound is for VCG prices which may involve positive transfers. The problem becomes more complex without positive transfers.
Limitations and Future Work
- Normalization Assumption: The main lower bound result holds under the assumption that "losers pay zero." The authors explicitly state that it is an open question whether this result can be generalized to domains without this normalization.
- Welfare Maximization Without Positive Transfers: The paper poses open questions about whether linear or sub-linear communication overhead can be achieved for computing equilibrium-supporting prices in welfare-maximizing settings without the "no positive transfers" assumption.
- Core Outcomes: While computing core outcomes generally has low overhead, the paper notes that a more practical core outcome (Ausubel-Milgrom) can have unbounded communication overhead.
- General Multi-Parameter Domains: The paper focuses on single-parameter domains for its main lower bound. The complexity of SCFs in multi-parameter domains is noted as "little understood," suggesting this as a direction for future research.
Summary updated