In the Carolingian period (8-9th c) duke, count and marquis were political offices of representatives of the king and not necessarily the heritable, landed aristocracy we associate with those titles later on the middle ages. The titles persisted, the meaning of the words and the power vested in them changed substantially in the several hundred years after the Carolingian period - if they even had stability as late as 900 they did not after that.

Duke, count and marquis are of course modern english terminology and spelling. A marcensis (marquis) was a Carolingian office found in a few border lands (frontiers) at the fringes of Carolingian empire, most famously perhaps the 'spanish marches' along the Pyrenees facing Al Andalus; often the title was fully comes marcensis, or 'count of the frontier'. Here you can see that the office descriptions of count and marquis are not much different, except by geographic concern. The idea of being on a defensive frontier entailed perhaps special administrative, commercial and military powers.

The word 'march' derives from latin marca, meaning border or frontier and passed into old French as marche, and marcensis become marquis. In the same way we have latin comes for counts and dux for duke.

Much like the titles 'count' and 'duke', the later middle ages 'marquis' does not bear any political relationship to their early middle ages origins, but may maintain association with their geographic origins. These titles lose their original association of public office in a strict sense and become associated with private aristocracy, tied to land and inheritance.

Finally, the Carolingians did not have 'fiefs'; a fief did not exist prior to the central middle ages in any form - we should take care not to force late medieval land, political and social relations onto older use of the word.