In the eighth century BCE, the relatively small and relatively simple Dark Age settlements of the Greek world start changing, as a demographic boom takes place. At the beginning of the fifth century, we are looking at a much more complex ecology of poleis, each with its own particular internal institutional structure as well as external relations. My driving question in this study is why and how these particular institutions were formed in the intervening seventh and sixth centuries BCE to produce this complexity and progress. This is a question that spans the fields of literary and historical analysis: institutions emerge as a result of a society's fears and hopes, and often out of a set of competing alternatives; these are well documented in the products of the public song culture of early Greece. More specifically, I argue that in early Greece, resolving disputes, which by definition is a costly endeavor in terms of time spent and enmities risked, was not carried out by elite rulers simply because it was part of their job description. On the contrary, there was a significant payoff to be gained if one developed a reputation as a successful arbitrator: in the absence of a legislative process, the elites who became established as sources of legal order would see the rest of the community start referring to them as authorities. Institutions then emerge in several cities precisely in order to curtail the payoff and power of the arbitrator, but their introduction has far-ranging implications, as it shapes and accelerates state formation.