LLM-based Proxies for Preference Elicitation in Combinatorial Auctions

Abstract

Elicitation in combinatorial auctions is challenging as bidder preferences may be inherently difficult to describe and consequently communicate to an auctioneer. Classical work in elicitation focuses on using query-based techniques inspired by proper learning—often via proxies that interface between bidders and an auction mechanism—to incrementally learn bidder preferences as needed to compute efficient allocations. Although such elicitation mechanisms enjoy theoretical query efficiency, the amount of communication required may still be too cognitively taxing for bidders in practical scenarios. Significant recent advancements in natural language processing, particularly Large Language Models (LLMs), suggest the use of natural language for eliciting preferences. In this thesis, we propose an efficient LLM-based proxy design for eliciting preferences from bidders in a combinatorial auction setting where communication is limited. Our proposed mechanism combines LLM pipelines and DNF-proper-learning techniques to quickly approximate preferences with limited communication. To validate our LLM-based approach to proxy design, we create a testing sandbox for evaluating elicitation mechanisms that make use of natural language as a means of communication. Additionally, we address the scalability of our approach by demonstrating how we can ensure complexity that is polynomial in the number of items, in both simulating bidder responses and the inference process of the proxy. By leveraging sparse preference representations and restricting inference to smaller bundle sizes, our simulation remains faithful to the ground-truth preferences and our proxy sustains high efficiency for the auction, respectively, while ensuring polynomial complexity. Reaching approximately efficient outcomes five times faster than classical proper-learning-based elicitation mechanisms, our LLM-based approach demonstrates the potential of natural-languagebased elicitation approaches. Moreover, the LLM-based proxies provide outcomes that converge, with sufficient communication, to those arising from DNF-proper-learning techniques.