Publications [#356399] of Vincent Conitzer

Conference articles PUBLISHED

1. Zhang, H; Conitzer, V, Learning the valuations of a k-demand agent, 37th International Conference on Machine Learning, ICML 2020, vol. PartF168147-15 (January, 2020), pp. 11000-11009, ISBN 9781713821120
   (last updated on 2024/04/18)

   Abstract:
   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 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 empirical risk minimizer has a sample complexity that is optimal up to a factor of eO(k).