M.Sc Thesis
M.Sc Student Bahar Gal Information Elicitation in Multi-Party Computation using Simultaneous Sequential Mechanisms Department of Industrial Engineering and Management Professor Moshe Tennenholtz

Abstract

We introduce a general setting for information elicitation in multi-agent systems, where agents may be approached both sequentially and simultaneously in order to compute a function that depends on their private secrets. We consider oblivious mechanisms for sequential-simultaneous information elicitation. In such mechanisms the ordering of agents to be approached is fixed in advance. Surprisingly, we show that these mechanisms, which are easy to represent and implement are sufficient for very general settings, such as for the classical uniform model, where agents' secret bits are uniformly distributed, and for the computation of the majority function and other classical threshold functions. Moreover, we provide efficient algorithms for the verification of the existence of the desired elicitation mechanisms, and for synthesizing such mechanisms. In Section 2 we introduce our model, and general sequential-simultaneous mechanisms. We also briefly illustrate the power that these mechanisms buy us when comparing to previous studies where purely sequential or purely simultaneous mechanisms have been considered. In Section 3 we introduce oblivious mechanisms. We then show an efficient algorithm for verifying the existence of an appropriate oblivious elicitation mechanism, and show that a semi-natural ordering mechanism can be computed as the desired result, if such oblivious mechanism exists. We also remark (by means of example) that there are cases where the restriction to oblivious mechanisms might prevent us from obtaining the desired computation; this leads to the study of settings where the existence of a desired elicitation process implies that it can be done by a corresponding oblivious mechanism, which we can efficiently compute. The uniform model is discussed in section 4, and the majority function, as well as extensions to other threshold functions are discussed in section 5. In all cases efficient algorithms are provided.