FastRank: Practical lightweight tolerance to rational behavior in edge assisted streaming

Edge-computing is one of the most promising techniques to leverage the excess capacity that exists at users' premises. Unfortunately, edge-computing may be vulnerable to free-riding, i.e., to nodes that attempt to benefit from the system without providing any service in return. Traditional approaches model free-riders as rational nodes that strive to maximize a utility and apply Game Theory concepts to devise mechanisms that deny any utility gain to nodes that deviate from the protocol. These mechanisms impose significant overhead. This paper proposes a new approach that avoids these overheads by applying concepts of evolutionary game theory. We propose to devise lightweight mechanisms targeted for the optimistic setting where the vast majority of nodes adopts one of a small number of behaviors. More precisely, we assume that most nodes are altruistic or follow non-sophisticated behaviors such as free-riding or white-washing. If a small fraction of nodes follows alternative behaviors, then our lightweight mechanism limits the utility gain of these nodes, making it unlikely that the number of nodes exploiting sophisticated behaviors increases at a fast pace. This allows altruistic nodes to detect their presence in time to switch to more robust mechanisms, before the system reaches a state where the lightweight mechanisms can no longer cope with the existing behaviors. We apply this approach in the context of edge-assisted streaming.