oh i just remember, realism was main in your game.
so in this case i would add friendships to the cavemen, and they'd need to interact every now and then with their friends to keep the friendship going and with sufficient "friendlyness" between tribes those tribes could ally.
(this would also allow to temporarily have more friendships/allies as you put more effort in them at some time, because you need to coöperate against a stronger tribe or something, pretty much making the player a politician xD )
thats already in there, just like the SIMs.
but even better, you can get friends to travel with you and fight for you.
you can also get them to join your band (the equivalent of a household in The SIMs).