I've found the thing that works best is fighting. In particular, get your King's bodyguard into the thick of it for a good period in each battle. He will get a good amount of authority from both the scarred line of traits and the brave line of traits.