All important persons (in your case: the cave men) have their own personal ambitions and goals (get wealthy, become leader etc.).
The counties, duchies and kingdoms (in your case: the tribes) have their own goals (reclaim lost territory, form a kingdom etc.).
Let the backstabbing commence!
sounds like a good approach. both leader goals, and faction goals.
the difficult thing about modeling "politics" in this case, is the large number of factions and their small size.
this is before there were real "tribes". in real life, a band was 10 to 30 individuals, usually a group of extended families. the biggest bands never topped 100 people.
in the game, bands are capped at 10 individuals, as the player controls a band of their own, like squaddies in a shooter that you can tab between at any time. 10 seemed like more than enough for one player to handle at once. and having bigger bands doesn't get you much, a higher chance that someone will have the item or skill you want, thats about it.
while the size of bands is capped at 10, the frequency of bands and random caveman encounters still reflects an accurate estimate of population density at the time. also, the game models migration, so bands come and go.
the result is, no "country" has more than 10 guys, a "country" only lasts for about 3 months before they pack up and head for greener pastures, and there are about 36,000 "countries" in the game at any given time.
so traditional faction/politics stuff doesn't just drop right in and work correctly. its more like 36,000 households out on the frontier with no formal government, than it is 36,000 factions vying for power. then again, maybe that's the same thing, just on a smaller scale.