article · Journal of the ACM · 2026
An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design
Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg
Cited by 0Open access
Abstract
In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output. How much harder is it to solve the same problem when the input is not given directly, but instead reported by strategic agents with interests of their own? The unique challenge stems from the fact that the agents may choose to lie about the input in order to manipulate the behavior of the algorithm for their own interests, and tools from Game Theory are therefore required in order to predict how these agents will behave. We develop a new algorithmic framework with which to study such problems. Specifically, we provide a computationally efficient black-box reduction from solving any Bayesian optimization problem on “strategic input,” often called algorithmic mechanism design , to solving a perturbed version of that same optimization problem when the input is directly given, traditionally called algorithm design . We further demonstrate the power of our framework by making significant progress on several long-standing open problems. First, we provide an algorithmic extension of Myerson’s celebrated characterization of single item auctions [105] to multiple items, providing also a computationally efficient implementation of optimal auctions. Next, we design a computationally efficient 2-approximate mechanism for Bayesian job scheduling on unrelated machines, the original problem studied in Nisan and Ronen’s seminal paper introducing the field of Algorithmic Mechanism Design [106]. This matches the guarantee of the best known computationally efficient algorithm when the input is directly given. Finally, leveraging a connection to our framework, we additionally prove hardness of approximation for Bayesian mechanism design with submodular bidders.
Cite this paper
Cai, Y., Daskalakis, C., & Weinberg, S. M. (2026). An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design. Journal of the ACM. https://doi.org/10.1145/3801546
Cai, Yang, et al. “An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design.” Journal of the ACM, 2026, https://doi.org/10.1145/3801546.
Cai, Yang, Constantinos Daskalakis, and S. Matthew Weinberg. 2026. “An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design.” Journal of the ACM. https://doi.org/10.1145/3801546.
Cai, Y., Daskalakis, C. and Weinberg, S.M. (2026) ‘An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design’, Journal of the ACM. Available at: https://doi.org/10.1145/3801546.
@article{cai2026algorithmic,
title = {{An Algorithmic Framework for Black-Box Reductions from Bayesian Mechanism Design to Algorithm Design}},
author = {Cai, Yang and Daskalakis, Constantinos and Weinberg, S. Matthew},
journal = {Journal of the ACM},
year = {2026},
doi = {10.1145/3801546}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.