If you're not certain they will vote for ( IE if they don't like you which is expected on emperor), don't hold a vote !!!
IIRC it's every 20 turns but don't quote me on that as I have never seen it in action. Never had a game that lasted that long, except maybe a few in which I made I build it myself.