We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight - both positive and impossibility - results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.

We study non-atomic congestion games on parallel-link networks with polynomial latencies. We investigate the power of machine-learned predictions in the design of coordination mechanisms aimed at minimizing the impact of selfishness. Our main results demonstrate that enhancing coordination mechanisms with simple advice on the input rate can optimize the social cost whenever the advice is accurate (consistency ), while only incurring minimal losses even when the predictions are arbitrarily inaccurate (bounded robustness ). Moreover, we provide a full characterization of consistent mechanisms, which holds for all monotone cost functions, and show that our proposed mechanism is optimal with respect to robustness. We further explore the notion of error-tolerance within this context, i.e., we provide an approximation guarantee that degrades smoothly as a function of the prediction error, up to a predetermined threshold, while achieving a bounded robustness.

Our work revisits the design of mechanisms via the learning-augmented framework. In this model, the algorithm is enhanced with imperfect (machine-learned) information concerning the input, usually referred to as prediction. The goal is to design algorithms whose performance degrades gently as a function of the prediction error and, in particular, perform well if the prediction is accurate, but also provide a worst-case guarantee under any possible error. This framework has been successfully applied recently to various mechanism design settings, where in most cases the mechanism is provided with a prediction about the types of the players. We adopt a perspective in which the mechanism is provided with an output recommendation. We make no assumptions about the quality of the suggested outcome, and the goal is to use the recommendation to design mechanisms with low approximation guarantees whenever the recommended outcome is reasonable, but at the same time to provide worst-case guarantees whenever the recommendation significantly deviates from the optimal one. We propose a generic, universal measure, which we call quality of recommendation, to evaluate mechanisms across various information settings. We demonstrate how this new metric can provide refined analysis in existing results. This model introduces new challenges, as the mechanism receives limited information comparing to settings that use predictions about the types of the agents. We study, through this lens, several well-studied mechanism design paradigms, devising new mechanisms, but also providing refined analysis for existing ones, using as a metric the quality of recommendation. We complement our positive results, by exploring the limitations of known classes of strategyproof mechanisms that can be devised using output recommendation.