M.Sc Thesis
M.Sc Student Klinger Andrey Stability against Group Deviations in Non-Cooperative Computation Department of Computer Science Professor Moshe Tennenholtz

Abstract

A function is non-cooperative computable [NCC] if honest agents can compute it by reporting truthfully their private inputs, while unilateral deviations by the agents are not beneficial: if a deviation from truth revelation can mislead other agents, then the deviator might end up with a wrong result. Previous work provided full characterization of the Boolean functions which are non-cooperatively computable. Later work has extended that study in various directions. This thesis extends the study of NCC functions to the context of group deviations. A function is K-NCC if deviations by a group of at most K agents are not beneficial: in order to mislead other agents, at least one group member might compute a wrong outcome. A function which is K-NCC for every K is termed strong-NCC. In this thesis we provide a full characterization of the K-NCC functions, for every K, and of strong-NCC functions in particular. We show that the hierarchy of K-NCC functions is strict. Surprisingly, we also show that an anonymous function is NCC if and only if it is strong-NCC; that is, an anonymous function which is non-cooperatively computable is stable against deviations by any coalition of the agents. In addition, we show that group deviations are stable: if there exists a deviating coalition of minimal size K, then there is no sub-coalition of it which will benefit by further deviation from the original deviating strategy.

A more extended setting is one where agents might be paid for the inputs they report. 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 agents are not beneficial in this setting: 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 thesis 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.