The Avtokrator was the absolute ruler of the Empire of Videssos. The Avtokrator was assisted by an influential bureaucracy, which was powerful enough to enforce its choice for the throne, even in the face of military opposition. The bureaucracy and military were traditionally rivals for influence over the emperor, and by extension, the empire.
As Harry Turtledove has not revealed every Avtokrator, this list is by no means complete. The list is chronological based on the evidence available.
Stavrakios, known as the "Great", reigned a century after the empire was founded (two hundred years before the birth of Rhavas and 1100 years before the arrival of the Roman Legion); during his reign, the Videssians invaded both Makuran and Halogaland. Stavrakios sacked Mashiz and was said to have defeated the Makuraner King of Kings in single combat. The Empire grew to its greatest extent under his reign. His rule was also the most stable.
Later generations who viewed his portraits were of the opinion that, despite his imperial raiment, he looked more like a veteran underofficer than an Emperor.
Palamas reigned three centuries after the founding of the empire (nine hundred years prior to the arrival of the Roman Legion.) A plaza in the City of Videssos was named in his honor.
See: Maleinos II
See: Maniakes II
See: Anthimos III
Ioannakis II died 300 years before the arrival of the Roman Legion.
Khoirosphaktes reigned roughly 200 years before the arrival of the Roman Legion. He was remembered for establishing a fort in Pardraya on the Kouphis River as a gift to a powerful Khamorth khagan. It was abandoned after his death. The fort came to be remembered as "Khoirosphaktes' Folly". Khoirosphaktes also sent the khagan an elephant, who promptly returned it.
See: Strobilos Sphrantzes
See: Mavrikios Gavras
See: Ortaias Sphrantzes
See: Thorisin Gavras
Turtledove has named other Avtokrators throughout the series, but has not always provided sufficient information about when they reigned, or the information provided contradicts the rest of the canon.
In The Misplaced Legion, Laskaris is said to have sacked Mashiz 739 years before the arrival of the Roman Legion. He is also described as having personally taken the helmet from Rishtaspa of Makuran's corpse, which became a trophy for the empire.
However, these actions are credited to Stavrakios in every other volume of the series, and Laskaris is never mentioned again after this. Implicitly, Turtledove retconned Laskarsis into Stavrakios (deliberately or otherwise).
Rhazates was an Avtokrator who ruled the Empire of Videssos for a very brief period many years before the ascension of Krispos. He was crowned as Avtokrator on the steps of the High Palace, but on being announced to his subjects, the crowd laughed at him because he was grossly overweight. He returned to the palace but was overthrown in a coup d'etat within days.
On being crowned Avtokrator many years later, Krispos remembered reading Rhazates's story in the chronicles with a bit of apprehension before Barsymes introduced him to a similar crowd of onlookers. Krispos understood the incident as a warning that, while Videssos was not a democracy de jure, a would-be Avtokrator who had not won the popular support of the capital's common population could never be secure in his emperorship.
In Hammer and Anvil we are told that upon the death of an emperor named Yermanos, the empire fell into civil war. The date of his reign is unknown.
Anthimos I & II, Ioannikis I, and Maleinos IEdit
From the numerals following various reign names, we can infer that there were three avtokrators by the name of Anthimos, three by the name of Ioannikis, and two by the name of Maleinos. We know nothing of the first two Anthimoi, the first Ioannikis, or the first Maleinos.