Tribal chiefs seem to have been (and be - there's still hunter-gatherers around, y'know) just well-respected people, they couldn't actually tell anyone what to do.It's not like I was around at the time, but I'd bet tribal chiefs and regular warfare were pretty common in these societies which goes against the anarchy ethos.
Warfare - yes, and loads of it. Casualties were/are extremely low by today's standards though, on account of unsophisticated weaponry and a complete lack of any kind of sustained organisation (because no-one could tell anyone else what to do)
Dunno why you have it in for anarchists, dude. Being massively impractical is a fairly minor sin