Carbon emission verification is one of the key factors required for proper implementation of a cap-and-trade (C&T) system. However, to obtain more revenue, emission generating companies (GCs) may collude with third-party verifiers (3 PVs) and conceal real carbon emission data. Based on actual practice of Shenzhen's C&T system, a three-player game model has been devised in this paper to analyze the behaviors among GCs, 3 PVs and government. Given the government's current piecewise linear re-verification policy, the optimal reported carbon intensity for GCs has been provided. Our research reveals that if the actual carbon intensity is larger than historical carbon intensity GCs may report less carbon intensity and conceal actual carbon emission. To deal with this issue, a new exponential re-verification policy is proposed. Based on authentic data from Shenzhen's C&T system, the experimental results show that the government should devote more attention to GCs with a decreasing industrial product output value-added (IVA) than to those with high carbon emissions when selecting GCs for re-verification. Our experiments also illustrate that the new policy outperforms the current one on both total concealed amount of carbon emission and total re-verification cost if the initial re-verification probability is set within a specific range.