Combinatorial agency

ABSTRACT

Much recent research concerns systems, such as the Internet, whose components are owned and operated by different parties, each with his own "selfish" goal. The field of Algorithmic Mechanism Design handles the issue of private information held by the different parties in such computational settings. This paper deals with a complementary problem in such settings: handling the "hidden actions" that are performed by the different parties.Our model is a combinatorial variant of the classical principalagent problem from economic theory. In our setting a principal must motivate a team of strategic agents to exert costly effort on his behalf, but their actions are hidden from him. Our focus is on cases where complex combinations of the efforts of the agents influence the outcome. The principal motivates the agents by offering to them a set of contracts, which together put the agents in an equilibrium point of the induced game. We present formal models for this setting, suggest and embark on an analysis of some basic issues, but leave many questions open.

REFERENCES

• 1: M. Babaioff, M. Feldman, and N. Nisan. The Price of Purity and Free-Labor in Combinatorial Agency. In Working Paper, 2005.
• 2: M. Babaioff, M. Feldman, and N. Nisan. Combinatorial agency, 2006. www.sims.berkeley.edu/~moshe/comb-agency.pdf.
• 3: Michal Feldman , John Chuang , Ion Stoica , Scott Shenker, Hidden-action in multi-hop routing, Proceedings of the 6th ACM conference on Electronic commerce, p.117-126, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064022]
• 4: B. Holmstrom. Moral Hazard in Teams. Bell Journal of Economics, 13:324--340, 1982.
• 5: A. Mass-Colell, M. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1995.
• 6: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 7: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 8: J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput., 12(4):777--788, 1983.
• 9: A. Ronen and L. Wahrmann. Prediction Games. WINE, pages 129--140, 2005.
• 10: 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
• 11: R. Smorodinsky and M. Tennenholtz. Overcoming Free-Riding in Multi-Party Computations - The Anonymous Case. Forthcoming, GEB, 2005.
• 12: E. Winter. Incentives and Discrimination. American Economic Review, 94:764--773, 2004.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Payment schemes

General Terms:
Design, Economics, Theory

Keywords:
agency theory, contracts, hidden-action, incentives, mechanism design, moral hazard, price of unaccountability, principal-agent model