Preference Elicitation and Query Learning
Avrim Blum, Jeffrey Jackson, Tuomas Sandholm, Martin Zinkevich; 5(Jun):649--667, 2004.
Abstract
In this paper we explore the relationship between
"preference elicitation", a learning-style problem that arises in
combinatorial auctions, and the problem of learning via queries
studied in computational learning theory. Preference elicitation is
the process of asking questions about the preferences of bidders so as
to best divide some set of goods. As a learning problem, it can be
thought of as a setting in which there are multiple target concepts
that can each be queried separately, but where the goal is not so much
to learn each concept as it is to produce an "optimal example". In
this work, we prove a number of similarities and differences between
two-bidder preference elicitation and query learning, giving both separation
results and proving some connections between these problems.
[abs][pdf][ps.gz][ps]