Introduction
In the era of "Big Data," market mechanisms often involve millions of participants, from internet-scale ad auctions to cloud resource scheduling. Traditional algorithmic mechanism design focuses on polynomial-time tractability. However, when the number of participants $n$ reaches the millions, even linear-time algorithms ($O(n)$) can become prohibitively slow for real-time applications.
This paper introduces Local Computation Mechanism Design (LCMD), a framework for designing game-theoretic mechanisms that operate in polylogarithmic time and space. An LCMD mechanism responds to local queries—such as "Which item was assigned to Buyer A?"—without ever computing the full global solution.
The LCMD Framework
The core challenge of LCMD is to ensure that local, nearly instantaneous responses remain globally coherent and incentive-compatible. A valid LCMD must satisfy three primary criteria:
- Efficiency: Each query must be answered in $O(\text{polylog } n)$ time and space.
- Consistency: All local responses must be consistent with a single, valid global feasible solution. For example, if a mechanism reports that Man A is matched to Woman B, it must also report that Woman B is matched to Man A when queried.
- Incentive Compatibility: Participants must be incentivized to report their true preferences, even though the mechanism only processes a tiny fraction of the total data for any given query.
Methodological Innovations
The authors bridge the gap between Local Computation Algorithms (LCAs)—which answer queries about a global solution by looking at a local neighborhood of the input—and mechanism design through several key techniques:
Query Trees and Dependency Chains
To determine the outcome for a specific agent, the algorithm recursively queries a small neighborhood of "neighboring" agents. The authors demonstrate that for many problems, this dependency chain remains polylogarithmic with high probability, allowing the computation to stay local.
Truncated Algorithms
For the stable matching problem, the authors introduce an "Abridged" Gale-Shapley algorithm. While the standard Gale-Shapley algorithm can take $O(n^2)$ steps, the abridged version stops after a constant number of rounds. In settings where preferences are $k$-uniform (short, random lists), this truncation still matches the vast majority of participants while maintaining stability for those matched.
Local Payment Schemes
In auctions and scheduling, calculating payments is as critical as the allocation itself. The authors develop randomized payment rules that can be calculated locally, ensuring that the mechanism remains truthful in expectation.
Key Results across Domains
The paper provides LCMD constructions for four major classes of problems:
- Stable Matching: Using the truncated Gale-Shapley approach, the mechanism matches all but an $O(1/k)$ fraction of participants. It achieves "ex-ante" truthfulness, where honesty is the best strategy based on the distribution of others' preferences.
- Job Scheduling: For scheduling on related machines, the authors provide an $O(\log \log n)$-approximation to the optimal makespan that is truthful in expectation.
- Combinatorial Auctions: For unit-demand and $k-minded$ bidders, the framework achieves 1/2-approximation and $1/k$-approximation of the optimal social welfare, respectively.
- Housing Allocation: The authors show that the "Random Serial Dictatorship" algorithm can be fully implemented as an LCA, ensuring perfect consistency and truthfulness.
Theoretical Insights and Trade-offs
A significant finding is the Locality-Approximation Trade-off. The authors prove that certain problems, such as finding a maximum matching, are impossible to solve exactly using an LCA. Consequently, local computation often requires accepting an approximation to the optimal global solution (e.g., a 1/2-approximation for auctions).
Furthermore, the requirement for consistency is often met by using a shared random seed. This seed determines a global ordering or priority that all local queries respect, ensuring that independent computations do not produce contradictory results.
Limitations and Future Work
While LCMD opens new doors for massive-scale mechanism design, it currently relies heavily on distributional assumptions. Most results assume preferences are sampled from uniform or known distributions to ensure the "locality" of the problem. Relaxing these assumptions to handle worst-case inputs remains a significant challenge. Additionally, moving from "truthfulness in expectation" to "universal truthfulness" in local settings is a key area for future research.
Summary updated