Timezone: »

Learning the Valuations of a $k$-demand Agent
Hanrui Zhang · Vincent Conitzer

Thu Jul 16 06:00 AM -- 06:45 AM & Thu Jul 16 05:00 PM -- 05:45 PM (PDT) @ Virtual
We study problems where a learner aims to learn the valuations of an agent by observing which goods he buys under varying price vectors. More specifically, we consider the case of a $k$-demand agent, whose valuation over the goods is additive when receiving up to $k$ goods, but who has no interest in receiving more than $k$ goods. We settle the query complexity for the active-learning (preference elicitation) version, where the learner chooses the prices to post, by giving a {\em biased binary search} algorithm, generalizing the classical binary search procedure. We complement our query complexity upper bounds by lower bounds that match up to lower-order terms. We also study the passive-learning version in which the learner does not control the prices, and instead they are sampled from some distribution. We show that in the PAC model for passive learning, any {\em empirical risk minimizer} has a sample complexity that is optimal up to a factor of $\widetilde{O}(k)$.

Author Information

Hanrui Zhang (Duke University)
Vincent Conitzer (Duke)

More from the Same Authors