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.
