Incentive compatible regression learning

ABSTRACT

We initiate the study of incentives in a general machine learning framework. We focus on a game-theoretic regression learning setting where private information is elicited from multiple agents with different, possibly conflicting, views on how to label the points of an input space. This conflict potentially gives rise to untruthfulness on the part of the agents. In the restricted but important case when every agent cares about a single point, and under mild assumptions, we show that agents are motivated to tell the truth. In a more general setting, we study the power and limitations of mechanisms without payments. We finally establish that, in the general setting, the VCG mechanism goes a long way in guaranteeing truthfulness and economic efficiency.

REFERENCES

• 1: Maria-Florina Balcan , Avrim Blum, Mechanism Design via Machine Learning, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.605-614, October 23-25, 2005 [doi>10.1109/SFCS.2005.50]
• 2: Marco Barreno , Blaine Nelson , Russell Sears , Anthony D. Joseph , J. D. Tygar, Can machine learning be secure?, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan [doi>10.1145/1128817.1128824]
• 3: Peter L. Bartlett , Shahar Mendelson, Rademacher and gaussian complexities: risk bounds and structural results, The Journal of Machine Learning Research, 3, 3/1/2003
• 4: Nader H. Bshouty , Nadav Eiron , Eyal Kushilevitz, PAC learning with nasty noise, Theoretical Computer Science, v.288 n.2, p.255-275, 16 October 2002 [doi>10.1016/S0304-3975(01)00403-0]
• 5: E. H. Clarke. Multipart pricing of public goods. Public Choice, 11:17--33, 1971.
• 6: Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132607]
• 7: S. A. Goldman and R. H. Sloan. Can PAC learning algorithms tolerate random attribute noise? Algorithmica, 14(1):70--84, 1995.
• 8: T. Groves. Incentives in teams. Econometrica, 41:617--631, 1973.
• 9: David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
• 10: G. Kalai. Learnability and rationality of choice. Journal of Economic Theory, 113(1):104--117, 2003.
• 11: Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
• 12: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 13: Nicholas Littlestone, Redundant noisy attributes, attribute errors, and linear-threshold learning using winnow, Proceedings of the fourth annual workshop on Computational learning theory, p.147-156, August 05-07, 1991, Santa Cruz, California, United States
• 14: A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeco-nomic Theory. Oxford University Press, 1995.
• 15: H. Moulin. Generalized Condorcet-winners for single peaked and single-plateau preferences. Social Choice and Welfare, 1(2):127--147, 1984.
• 16: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 17: 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]
• 18: D. Pollard. Convergence of Stochastic Processes. Springer-Verlag, 1984.
• 19: A. D. Procaccia, A. Zohar, Y. Peleg, and J. S. Rosenschein. Learning voting trees. In Proceedings of the 22nd Conference on Artificial Intelligence (AAAI), pages 110--115, 2007.
• 20: A. D. Procaccia, A. Zohar, and J. S. Rosenschein. Automated design of voting rules by learning from examples. In Proceedings of the 1st International Workshop on Computational Social Choice (COMSOC), pages 436--449, 2006.
• 21: M. Rothkopf. Thirteen reasons the Vickrey-Clarke-Groves process is not practical. Operations Research, 55(2):191--197, 2007.
• 22: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 23: W. Vickrey. Counter speculation, auctions, and competitive sealed tenders. Journal of Finance, 16(1):8--37, 1961.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Design, Theory