Sequential-Simultaneous Information Elicitation in Multi-Agent Systems

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.