טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAricha Inbar
SubjectMulti-Party Computation Games and Sequential Mechanisms
DepartmentDepartment of Applied Mathematics
Supervisor Professor Rann Smorodinsky


Abstract

Consider a situation with N agents and each agent has a private secret. As opposed to standard models, in our set-up the agents incur a cost for accessing the secret. All agents have a joint interest in computing a function that depends on the vector of their private inputs. However, as accessing the secret is costly, agents would like to free-ride on others’ contribution and provide a ’guess’ of their secret, instead of accessing it and reporting the true value.

We look for mechanisms that elicit agents’ secrets and perform the desired computation. A mechanism ’implements G on the set S of secret vectors’ if it implements the social choice function G, for all secret vectors in S. Namely, if there exists an equilibrium in which it is able to elicit (sufficiently many) agents’ secrets and perform the computation, for all secret vector in S. We focus on the advantage of a sequential mechanism over a simultaneous one. Also, we represent a characterization/reduction theorem which reduces the search domain of a mechanism which ’implements G on S’.

This paper generalizes the framework of multi-party computations with asymmetric and costly information, introduced by Smorodinsky and Tennenholtz. In their original work, Smorodinsky and Tennenholtz consider social choice functions which are anonymous and an environment of private i.i.d secrets. In this work we generalize the main results to non-anonymous functions and general distributions over secrets (including correlations).