Emissaries and Princess gain valour according to how many alliances they make.

Assassins also gain valour based on the number of stars of the victim... essentially you will be about 1 star less then the victim... it seems to be like most valour which is a 2^n experience progression... in other words you have to kill 2^n people to go up valour... while each target is worth 2^(stars minus one)... something along those lines.