I'm trying to win a domination victory on deity as it is the only victory type I haven't managed on deity. I usually play random leader as I think you should be able to win with any leader if you're good enough but I have been choosing the leader as I'm trying for a specific victory which I'm not very good at. Hence I've chosen Matthias so I can benfit from the city state levy. But it's not going well. A couple of games I've been hugely outpaced in terms of envoys in the the very early game. My most recent attempt saw the Aztecs have 5 envoys in the one city state I'd met by turn 33/330. I had 1 from meeting it first. How did they do that?! I haven't even been given a quest yet.