I don't quite understand sigmaxipi's idea, but from what I can tell, it's not the same as mine.

In my proposal, your counter-example isn't a problem, because something that is less complex (easier to specify) is given a higher utility bound.