A duke no longer has to be the lord of a region; he could simply have lords sworn to him.
Or, the duke could be lord of a poor badland, and have a city and a rural sworn to him.
Etc, etc. It's just a position in the feudal hierarchy--subservient only to the king, and with lords under him.
