K-SNCC: group deviations in subsidized non-cooperative computing

ABSTRACT

A function is subsidized non-cooperative computable [SNCC] if honest agents can compute it by reporting truthfully their private inputs, while unilateral deviations by the players are not beneficial: if a deviation from truth revelation can mislead other agents, this deviation will decrease the deviator's chances of correct computation, or, it will not affect these chances but the expected payment to the deviator will decrease; in addition, deviations can not increase the expected monetary payments to a deviator without decreasing his chances of correct computation. This paper extends the study of SNCC functions to the context of group deviations. A function is K-SNCC if deviations by a group of at most K agents are not beneficial. We provide a full characterization of the K-SNCC functions, both for the independent values and the correlated values settings.

REFERENCES

• 1: Ittai Abraham , Danny Dolev , Rica Gonen , Joe Halpern, Distributed computing meets game theory: robust mechanisms for rational secret sharing and multiparty computation, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146393]
• 2: I. Ashlagi, A. Klinger, and M. Tennenholtz. K-ncc: Stability against group deviations in non-cooperative computation. In WINE, pages 564--569, 2007.
• 3: R. Aumann. Acceptable points in general cooperative n-person games. In A. Tucker and R. Luce, editors, Contribution to the Theory of Games, Vol. IV, Annals of Mathematics Studies, 40, pages 287--324. 1959.
• 4: Joseph Halpern , Vanessa Teague, Rational secret sharing and multiparty computation: extended abstract, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007447]
• 5: A. Mas-Colell, M. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1995.
• 6: Robert McGrew , Ryan Porter , Yoav Shoham, Towards a general theory of non-cooperative computation, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846249]
• 7: Yoav Shoham , Moshe Tennenholtz, Non-cooperative computation: boolean functions with correctness and exclusivity, Theoretical Computer Science, v.343 n.1-2, p.97-113, 10 October 2005 [doi>10.1016/j.tcs.2005.05.009]
• 8: R. Smorodinsky and M. Tennenholtz. Overcoming free riding in multi-party computations--the anonymous case. Games and Economic Behavior, 55(2):385--406, May 2006. available at http://ideas.repec.org/a/eee/gamebe/v55y2006i2p385-406.html.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory