Budget-Feasible Mechanism Design for Cost-Benefit Optimization in Gradual Service Procurement

We consider a procurement problem where a software agent procures multiple services from self-interested providers with private costs and uncertain reliabilities to complete a budget-limited task before a strict deadline. Over the last decade, several truthful budgetfeasible procurement mechanisms have been developed to extract the true cost information from strategic providers. Most of these mechanisms have focused on maximizing the procurer's value (e.g., the task's success probability), and hence procuring as many services as the budget allows, even if the returned benefit is lower than the incurred cost. In this paper, however, we focus on the more realistic objective of balancing the cost-benefit tradeoff and propose a novel approach for designing budget-feasible mechanisms that invoke services gradually over time and whenever they are cost-optimal. A major barrier to achieving this goal was the strong dependencies among the decision variables caused by budget constraints. We overcome this barrier by proposing a conservative decomposable approximation to budget constraints. This is the first such approximation technique, which opens a path toward designing budget-feasible mechanisms for contingent planning problems.