Game Authority for Robust Distributed Selfish-Computer Systems (Preliminary Version)

Game theory has an elegant way of modeling somestructural aspects of social games. The predicted outcome of thesocial games holds as long as ?the rules of the game? are kept.Therefore, a game authority (which enforces the ?rules?) isimplied. We present the first design for that game authority, andthe first suiting middleware for executing an algorithmic mechanismin distributed systems. The middleware restricts the agents to?play by the rules?, and excludes non-selfish agents since weconsider them as Byzantine. We base our design on a self-stabilizingByzantine agreement that allows processors to audit each other?sactions. We show that when the agents are restricted to actselfishly the resource allocation is asymptotically optimal(according to our novel performance ratio; multi-round anarchycost). Our design also includes services that allow owners to sharea collaborative effort for coalition optimization usinggroup-preplay negotiation. Since there are no guarantees forsuccessful termination of selfish negotiations, we consider?democratic? approaches for promoting ?free choice?