I'd hate to have to do that one... not to mention that the legend specifies that the labels on the map are "Selected tribes" which seems to indicate that there's more... With polygons, you could enclose unnamed tribes into some other territory.
If I absolutely had to do it, I'd go with points, even thought as Hans mentioned, you'd lose the approximate geographical extent shown by the label... You could add a field with an attribute for the text size which will give you an idea of the importance of the tribe as well as a field with orientation that could give you a general, a bad - but general - approximation of the size of the territory. Note ideal, far from it, but at least, you'll won't place the Touareg in the North.
If you're digitizing polygons, I'd take a generic shape, rectangle or ellipse and have fate (even though we know it not really true) that the cartographer expanded it's labels to cover most of the territory (we can't estimate otherwise)...
Other than that, I'd be really confuse about how to do it... I'm not sure my options are optimal given the circumstances, but they're the only way of doing it I can think of...
Good luck and keep us informed! As a cartographer and historian, I'd love to find a good way to represent those so-so-so unclear boundaries I found sometimes on historical maps...