I like the idea. It sounds like a defeated tribe would lose only autonomy and not their lands/progress. A winning tribe gains access to the loser's land but doesn't actually wipe them out. The only thing I don't know about is the time limit on trying to cast off the oppressors. Maybe leave the option open for an unlimited duration so the overlords have to be careful and always watch out for uprisings.

If players really hate being vassals and know they can't defeat the overlords (or can't come to consensus on what to do) they can individually leave their tribe and quietly slink away to start again somewhere more remote. It allows the losers a choice in their own fate even if none of the options are ideal.

Definitely something to discuss and consider.