Every Bit Helps: Achieving the Optimal Distortion with a Few Queries

A fundamental task in multi-agent systems is to match n agents to n alternatives (e.g., resources or tasks). Often, this is accomplished by eliciting agents' ordinal rankings over the alternatives instead of their exact numerical utilities. While this simplifies elicitation, the incomplete information leads to inefficiency, captured by a worst-case measure called distortion. A recent line of work shows that making just a few queries to each agent regarding their cardinal utility for an alternative can significantly improve the distortion, with Amanatidis et al. [1] achieving O( √ n) distortion with two queries per agent. We generalize their result by achieving O(n 1/λ ) distortion with λ queries per agent, for any constant λ, which is optimal given a previous lower bound by Amanatidis et al. [2]. We also extend our finding to the general social choice problem, where one of m alternatives must be chosen based on the preferences of n agents, and show that O((minn, m) 1/λ ) distortion can be achieved with λ queries per agent, for any constant λ, which is also optimal given prior results. Thus, for both problems, our work settles open questions regarding the optimal distortion achievable using a fixed number of cardinal value queries.