Who first proposed the idea that "Supreme executive power derives from a mandate from the masses"?

Question

King Arthur: The Lady of the Lake, her arm clad in the purest shimmering samite, held aloft Excalibur from the bosom of the water, signifying by divine providence that I, Arthur, was to carry Excalibur. That is why I am your king.
Dennis: Listen. Strange women lying in ponds, distributing swords, is no basis for a system of government. Supreme executive power derives from a mandate from the masses, not from some farcical aquatic ceremony! ("Monty Python and the Holy Grail", naturally).

Who was the first political thinker (ruler, or civil servant, or theorist or writer/philosopher) who proposed this rule about mandate from the governed masses? Any wording is acceptable as long as the spirit matches.

Just to be clear, the idea being referred to can be summarized as:

You can not stably rule a set of people who fully disagree with the idea of your ruling them. You can only rule them when they - for whatever reasons - acquiesce to, if not support - your rule.

NOTE: The question is specifically limited to the rule being framed as a rule. To be more precise, stated in the form of "every government should have a mandate of the masses", as opposed to "well, I think such a mandate is a swell idea for my specific city government, but I won't formally postulate that without such, no other government can work".

Answer 1

In John Locke's Second Treatise on Government Chapter 11, Section 134 (written in 1690), he writes:

The lawful power of making laws to command whole politic societies of men, belonging so properly unto the same intire societies, that for any prince or potentate of what kind soever upon earth, to exercise the same of himself, and not by express commission immediately and personally received from God, or else by authority derived at the first from their consent, upon whose persons they impose laws, it is no better than mere tyranny. Laws they are not therefore which public approbation hath not made so. Hooker's Eccl. Pol. l. i. sect. 10. Of this point therefore we are to note, that sith [sic - should be such] men naturally have no full and perfect power to command whole politic multitudes of men, therefore utterly without our consent, we could in such sort be at no man's commandment living. And to be commanded we do consent, when that society, whereof we be a part, hath at any time before consented, without revoking the same after by the like universal agreement.

Laws therefore human, of what kind so ever, are available by consent. Ibid

While others may have made the argument earlier, he is often credited with at least popularizing the idea that "power is derived from the consent of the governed," and was often cited by the Founding Fathers as the impetus for this idea.

Social Contract Theory as a whole often traces its roots through Hobbes' "state of Nature," (in which, in the absence of a despot to bring order, life was nasty, brutish and short, and as such people would choose a Leviathan - a monarch to beat the stuffing out of them in order to persuade people to adhere to the rules they wanted) and developed throughout the late Enlightenment. Locke extended this idea into government as a "contract" in which people give up autonomy in order to perserve life, liberty, and wealth. This "deal" gives institutions power in order to further individual ends.

Hobbes, Locke, Rosseau, and others are often considered its progenitors, and John Stuart Mill often seen as its flower.

Answer 2

From the Institutes of Emperor Justinian:

Whence the right of emperors to make ordinances having the force of laws? By the Lex Regia, which, whilst it invested each emperor with his powers, clothed him with all public authority. For long this law was expressly renewed upon each accession, but afterwards, the authority it conferred was held to be transmitted to the new emperor by the fact of election.

A commentary on the Institutes from 1865 says:

"After the destruction of the republic by Augustus, the power of the Emperor, though at first nominal-- for he was styled Princeps Reipublica-- gradually increased, till at length he became "the State." Indeed, this result followed almost as a necessary consequence, after the Emperor had concentrated in himself all of the chief offices. The supreme power, imperium, was vested in him by the lex regia passed at the beginning of each reign, by which the people delegated to him their absolute power."

Answer 3

Epicureanism Is probably the earliest example you will find of the concept you refer to, which is normally called the social contract - basically that the governed have agreed to give up some of their power and freedom in exchange for the security and benefits of living in a larger society with laws and systems of governance.

In Epicurus' Principal Doctrines there are a few lines (this is from the wikipedia page on social contracts linked above):

Natural justice is a pledge of reciprocal benefit, to prevent one man from harming or being harmed by another.

Those animals which are incapable of making binding agreements with one another not to inflict nor suffer harm are without either justice or injustice; and likewise for those peoples who either could not or would not form binding agreements not to inflict nor suffer harm.

There never was such a thing as absolute justice, but only agreements made in mutual dealings among men in whatever places at various times providing against the infliction or suffering of harm.

While the wording isn't exactly what you are after, the philosophy is the same - in order to get the benefits of a system of justice, men (people) agree to concessions.