Harnessing the search for rational bid schedules with stochastic search and domain-specific heuristics

In previous work we proposed an approach for computing an agent's preferences over different schedules of tasks, and for soliciting desirable bid combinations to cover the tasks. The proposed approach finds schedules that maximize the agent's Expected Utility. The maximization problem is hard because the domain is piece-wise continuous, with the number of pieces and local maxima growing exponentially in the worst case scenario. For agents who are averse to taking risks, maximization algorithms tend to converge to degenerate maxima of no practical interest. In this paper we demonstrate three maximization methods based on domain-specific heuristics. We also present a new stochastic maximization approach, and benchmark it in two substantially different problem setups.