Learning algorithms for online principal-agent problems (and selling goods online)

ABSTRACT

In a principal-agent problem, a principal seeks to motivate an agent to take a certain action beneficial to the principal, while spending as little as possible on the reward. This is complicated by the fact that the principal does not know the agent's utility function (or type). We study the online setting where at each round, the principal encounters a new agent, and the principal sets the rewards anew. At the end of each round, the principal only finds out the action that the agent took, but not his type. The principal must learn how to set the rewards optimally. We show that this setting generalizes the setting of selling a digital good online.We study and experimentally compare three main approaches to this problem. First, we show how to apply a standard bandit algorithm to this setting. Second, for the case where the distribution of agent types is fixed (but unknown to the principal), we introduce a new gradient ascent algorithm. Third, for the case where the distribution of agents' types is fixed, and the principal has a prior belief (distribution) over a limited class of type distributions, we study a Bayesian approach.

REFERENCES

• 1: P. Auer , N. Cesa-Bianchi , Y. Freund , R. E. Schapire, Gambling in a rigged casino: The adversarial multi-armed bandit problem, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.322, October 23-25, 1995
• 2: Babaioff, M., Lavi, R., & Pavlov, E. (2005). Mechanism design for single-value domains. AAAI (pp. 241--247).
• 3: Bahar, G., & Tennenholtz, M. (2005). Sequential-simultaneous information elicitation in multi-agent systems. IJCAI (pp. 923--928).
• 4: Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
• 5: Yair Bartal , Rica Gonen , Pierfrancesco La Mura, Negotiation-range mechanisms: exploring the limits of truthful efficient markets, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988775]
• 6: Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 7: Blumberg, A., & Shelat, A. (2004). Searching for stable mechanisms: Automated design for imperfect players. AAAI (pp. 8--13).
• 8: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 9: Vincent Conitzer , Tuomas Sandholm, Self-interested automated mechanism design and implications for optimal combinatorial auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988793]
• 10: de Farias, D. P., & Megiddo, N. (2003). How to combine expert (or novice) advice when actions impact the environment? NIPS.
• 11: Robert Kleinberg , Tom Leighton, The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.594, October 11-14, 2003
• 12: Mas-Colell, A., Whinston, M., & Green, J. R. (1995). Microeconomic theory. Oxford University Press.
• 13: Parkes, D., & Schoenebeck, G. (2004). GROWRANGE: Anytime VCG-based mechanisms. AAAI (pp. 34--41).
• 14: Ryan Porter, Mechanism design for online real-time scheduling, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988783]
• 15: Rann Smorodinsky , Moshe Tennenholtz, Sequential information elicitation in multi-agent systems, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.528-535, July 07-11, 2004, Banff, Canada
• 16: Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. ICML (pp. 928--936).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Theory