How to minimize distortion in k-committee elections with limited cardinal information?
Constant-Factor Distortion Mechanisms for k-Committee Election
This paper explores how to select a "committee" of options from a larger set, based on the preferences of multiple agents, even when those preferences are imperfectly known. It focuses on minimizing the sum of the l-largest costs, a flexible objective covering both utilitarian and egalitarian approaches.
For LLM-based multi-agent systems, the key takeaway is the introduction of mechanisms to efficiently handle ordinal preference information (rankings) with minimal reliance on costly cardinal information (precise values). The proposed "black-box reduction" and "adaptive sampling" techniques offer pathways to build practical multi-agent systems where eliciting full and precise preferences from LLMs might be impractical or resource-intensive. These techniques enable approximate preference aggregation with provable distortion guarantees, meaning the selected committee isn't too far from optimal, even with limited preference information. The use of value queries could translate to well-designed prompts to elicit just enough information from LLMs without excessive querying.