It should be noted that if you have any tradeoff between average and total util you can still get MAPed into the RP: just add enough 'total' utility in the A+-->B move so this compensates for the drop in average, and then iterate.

Lexical priority would work (read average util, and only use total util as a tiebreaker), but this view seems to stand or fall with average util: if we find average util too costly, average util+lexically inferior total util is unlikely to be significantly cheaper.