Learning Competitive Equilibria in Exchange Economies with Bandit Feedback

Wenshuo Guo, Kirthevasan Kandasamy, Joseph Gonzalez, Michael Jordan, Ion Stoica
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:6200-6224, 2022.

Abstract

The sharing of scarce resources among multiple rational agents is one of the classical problems in economics. In exchange economies, which are used to model such situations, agents begin with an initial endowment of resources and exchange them in a way that is mutually beneficial until they reach a competitive equilibrium (CE). The allocations at a CE are Pareto efficient and fair. Consequently, they are used widely in designing mechanisms for fair division. However, computing CEs requires the knowledge of agent preferences which are unknown in several applications of interest. In this work, we explore a new online learning mechanism, which, on each round, allocates resources to the agents and collects stochastic feedback on their experience in using that allocation. Its goal is to learn the agent utilities via this feedback and imitate the allocations at a CE in the long run. We quantify CE behavior via two losses and propose a randomized algorithm which achieves sublinear loss under a parametric class of utilities. Empirically, we demonstrate the effectiveness of this mechanism through numerical simulations.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-guo22a, title = { Learning Competitive Equilibria in Exchange Economies with Bandit Feedback }, author = {Guo, Wenshuo and Kandasamy, Kirthevasan and Gonzalez, Joseph and Jordan, Michael and Stoica, Ion}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {6200--6224}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/guo22a/guo22a.pdf}, url = {https://proceedings.mlr.press/v151/guo22a.html}, abstract = { The sharing of scarce resources among multiple rational agents is one of the classical problems in economics. In exchange economies, which are used to model such situations, agents begin with an initial endowment of resources and exchange them in a way that is mutually beneficial until they reach a competitive equilibrium (CE). The allocations at a CE are Pareto efficient and fair. Consequently, they are used widely in designing mechanisms for fair division. However, computing CEs requires the knowledge of agent preferences which are unknown in several applications of interest. In this work, we explore a new online learning mechanism, which, on each round, allocates resources to the agents and collects stochastic feedback on their experience in using that allocation. Its goal is to learn the agent utilities via this feedback and imitate the allocations at a CE in the long run. We quantify CE behavior via two losses and propose a randomized algorithm which achieves sublinear loss under a parametric class of utilities. Empirically, we demonstrate the effectiveness of this mechanism through numerical simulations. } }
Endnote
%0 Conference Paper %T Learning Competitive Equilibria in Exchange Economies with Bandit Feedback %A Wenshuo Guo %A Kirthevasan Kandasamy %A Joseph Gonzalez %A Michael Jordan %A Ion Stoica %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-guo22a %I PMLR %P 6200--6224 %U https://proceedings.mlr.press/v151/guo22a.html %V 151 %X The sharing of scarce resources among multiple rational agents is one of the classical problems in economics. In exchange economies, which are used to model such situations, agents begin with an initial endowment of resources and exchange them in a way that is mutually beneficial until they reach a competitive equilibrium (CE). The allocations at a CE are Pareto efficient and fair. Consequently, they are used widely in designing mechanisms for fair division. However, computing CEs requires the knowledge of agent preferences which are unknown in several applications of interest. In this work, we explore a new online learning mechanism, which, on each round, allocates resources to the agents and collects stochastic feedback on their experience in using that allocation. Its goal is to learn the agent utilities via this feedback and imitate the allocations at a CE in the long run. We quantify CE behavior via two losses and propose a randomized algorithm which achieves sublinear loss under a parametric class of utilities. Empirically, we demonstrate the effectiveness of this mechanism through numerical simulations.
APA
Guo, W., Kandasamy, K., Gonzalez, J., Jordan, M. & Stoica, I.. (2022). Learning Competitive Equilibria in Exchange Economies with Bandit Feedback . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:6200-6224 Available from https://proceedings.mlr.press/v151/guo22a.html.

Related Material