  This paper considers the setting where a cloud server services a static set
or a dynamic sequence of tasks submitted by multiple clients. Every client
wishes to assure honest execution of tasks by additionally employing a trusted
third party (TTP) to re-compute the tasks with a certain probability. The cloud
server makes a deposit for each task it takes, each client allocates a budget
(including the wage for the server and the cost for possibly hiring TTP) for
each task submitted, and every party has its limited fund for either deposits
or task budgets. We study how to allocate the funds optimally to achieve the
three-fold goals: a rational cloud server honestly computes each task; the
server's wage is maximized; the overall delay for task verification is
minimized. We apply game theory to formulate the optimization problems, and
develop the optimal or heuristic solutions for three application scenarios. For
each of the solutions, we analyze it through either rigorous proofs or
extensive simulations. To the best of our knowledge, this is the first work on
optimizing fund allocation for verifiable outsourcing of computation in the
setting of one server and multiple clients, based on game theory.
