  To save time and money, businesses and individuals have begun outsourcing
their data and computations to cloud computing services. These entities would,
however, like to ensure that the queries they request from the cloud services
are being computed correctly. In this paper, we use the principles of economics
and competition to vastly reduce the complexity of query verification on
outsourced data. We consider two cases: First, we consider the scenario where
multiple non-colluding data outsourcing services exist, and then we consider
the case where only a single outsourcing service exists. Using a game theoretic
model, we show that given the proper incentive structure, we can effectively
deter dishonest behavior on the part of the data outsourcing services with very
few computational and monetary resources. We prove that the incentive for an
outsourcing service to cheat can be reduced to zero. Finally, we show that a
simple verification method can achieve this reduction through extensive
experimental evaluation.
