We study how to design network protocols that minimize the worst-case efficiency loss caused by selfish end users. The goal is to identify the optimal procotol subject to natural implementation constraints. We illustrate this idea in the context of cost-sharing protocols for large networks.