On the Range of Equilibria Utilities of a Repeated Epidemic Dissemination Game with a Mediator

摘要

We consider eager-push epidemic dissemination in a complete graph. Time isdivided into synchronous stages. In each stage, a source disseminates $u$events. Each event is sent by the source, and forwarded by each node upon itsfirst reception, to $f$ nodes selected uniformly at random, where $f$ is thefanout. We use Game Theory to study the range of $f$ for which equilibriastrategies exist, assuming that players are either rational or obedient to theprotocol, and that they do not collude. We model interactions as an infinitelyrepeated game. We devise a monitoring mechanism that extends the repeated gamewith communication rounds used for exchanging monitoring information, anddefine strategies for this extended game. We assume the existence of a trustedmediator, that players are computationally bounded such that they cannot breakthe cryptographic primitives used in our mechanism, and that symmetricciphering is cheap. Under these assumptions, we show that, if the size of thestream is sufficiently large and players attribute enough value to futureutilities, then the defined strategies are Sequential Equilibria of theextended game for any value of $f$. Moreover, the utility provided to eachplayer is arbitrarily close to that provided in the original game. This showsthat we can persuade rational nodes to follow a dissemination protocol thatuses any fanout, while arbitrarily minimising the relative overhead ofmonitoring.