i use the good ole assassin traits to build my kings stats - he gets a nice amount of dread (good for making your enemies run) and some authority (he also will have a good chance of picking up the deciever traits and get some more that way)

all you need to do is build plenty of assassins and use them.... use them a lot - there are areas on my map where there are no agents at all - my assassins purged them all