Learning the Valuations of a $k$-demand Agent

Hanrui Zhang, Vincent Conitzer
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:11066-11075, 2020.

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 \emph{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 \emph{empirical risk minimizer} has a sample complexity that is optimal up to a factor of $\widetilde{O}(k)$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-zhang20f, title = {Learning the Valuations of a $k$-demand Agent}, author = {Zhang, Hanrui and Conitzer, Vincent}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {11066--11075}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/zhang20f/zhang20f.pdf}, url = {https://proceedings.mlr.press/v119/zhang20f.html}, 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 \emph{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 \emph{empirical risk minimizer} has a sample complexity that is optimal up to a factor of $\widetilde{O}(k)$.} }
Endnote
%0 Conference Paper %T Learning the Valuations of a $k$-demand Agent %A Hanrui Zhang %A Vincent Conitzer %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-zhang20f %I PMLR %P 11066--11075 %U https://proceedings.mlr.press/v119/zhang20f.html %V 119 %X 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 \emph{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 \emph{empirical risk minimizer} has a sample complexity that is optimal up to a factor of $\widetilde{O}(k)$.
APA
Zhang, H. & Conitzer, V.. (2020). Learning the Valuations of a $k$-demand Agent. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:11066-11075 Available from https://proceedings.mlr.press/v119/zhang20f.html.

Related Material