Co-Utility: Self-Enforcing protocols for the mutual benefit of participants

Protocols govern the interactions between agents, both in the information society and in the society at large. Protocols based on mutually beneficial cooperation are especially interesting because they improve the societal welfare and no central authority is needed to enforce them (which eliminates a single point of failure and possible bottlenecks). In order to guide the design of such protocols, we introduce co-utility as a framework for cooperation between rational agents such that the best strategy for each agent is to help another agent achieve her best outcome. Specifically, in this work we study and characterize self-enforcing protocols in game-theoretic terms. Then, we use this characterization to develop the concept of co-utile protocol and study under which circumstances co-utility arises. Furthermore, we give a detailed study of co-utile protocol design in the case of anonymous query submission to a web search engine. The theoretical analysis is complemented with empirical results obtained from an implementation in a simulated multi-agent environment, which illustrates how co-utility can make cooperation self-enforcing and improve the agents' welfare.