Strategyproof deterministic lotteries under broadcast communication

The design of deterministic and fair mechanisms for selection among a set of self-motivated agents based solely on these agents' input is a major challenge in multiagent systems. This challenge is especially difficult when the agents can only communicate via a broadcast channel. We propose the notion of selection games: a special case of zero-sum games where the only possible outcomes are selections of a single agent among the set of agents. We assume the lack of an external coordinator, and therefore we focus on mechanisms which have a solution where the agents play weakly dominant strategies. Our first major result shows that dominated strategies could be added to any selection mechanism, so that the resulting mechanism becomes quasi-symmetric. For fairness, we require the mechanism to be non-imposing; that is, the mechanism should allow any agent to be selected in such a solution. We first show that such mechanisms do not exist when there are two or three agents in the system. However, surprisingly, we show that such mechanisms exist when there are four or more agents. Moreover, in our second major result, we show that there exist selection mechanisms that implement any distribution over the agents, when the agents play mixed dominant strategies. These results also have significance for electronic commerce, ranking systems, and social choice.