For discrete test statistics, the distribution of the corresponding $p$-value is discrete and stochastically larger than the uniform distribution. Hence the corresponding hypothesis test based on the p-value (reject if p-value is less than 0.05, for instance) is always conservative in the sense that the probability of making a Type I error will be smaller than 0.05. I know sometimes it is recommended to use the mid-pvalue. But I think there is no proof that using the mid-pvalue still controls the Type I error. Is there any other way to reduce the conservativeness? Can anyone who is familiar with this field give some hint or point out some existing literature on this?
I have never heard it suggested to use a mid p-value. This will not necessarily control your type-one error. As previously stated, the correct way to achieve a size of .05 is to perform a randomized test. However, your type one error is correct whether or not the test is randomized. In the conservative, non-randomized case, your testing procedure has a size smaller than the nominal alpha level. Since an alpha level of .05 is arbitrary anyway, it should be sufficient to report the size of the test.
One method of reducing the conservativeness of some discrete test statistics
(or more generally, just getting more choices of significance level)
Depending on the test, one occasionally useful approach that doesn't require randomizing is to add a tiny fraction of another reasonable statistic to break ties.
For example, imagine we were testing Kendall's tau but in small-to-moderate-sized samples, it's still pretty discrete, so it's hard to achieve close to a desired significance level.
For concreteness, let's say you want a level close to $\alpha = 10\%$ on a two tailed test, with $n=7$.
The achievable significance levels are 6.9% or 13.6%; neither is very close to what's needed!
One thing we could do is add a tiny fraction of a different statistic, one that's not perfectly correlated with the one we have; this means that many arrangements that gave statistics that were previously tied are no longer tied, even though their values are close.
For example, if we use Spearman's rho to break ties, for example by looking at $0.999 \tau + 0.001 \rho$, the values are almost identical to before, but the achievable significance levels are now 8.9% and 10.9% - not perfect, but much better than before - and in this case, the statistic is still distribution free.
Note that the weight on $\rho$ can be made as small as desired.
Here's an illustration - the black is the ECDF of the original Kendall correlation, while the red is the 'break ties' version. I have made the relative contribution of the Spearman much larger here (a weight of 0.1) so you can see the effect more clearly:
Let's zoom in on the region near the 2.5% and 5% level at the left end (one tailed, to correspond to 5% and 10% two-tailed):
As we see, we can get much closer to the desired significance level this way, while retaining just about all the other desirable properties to whatever degree of nearness we wish.
There are various adjustments to make the result even more Kendall-like (e.g. to set it up so the expectation of the small adjustment to the Kendall correlation at each Kendall correlation is zero, but that is rarely an issue for me).
[If you really don't know which of Kendall and Spearman you wanted to use for a nonparametric correlation, a more even mix has a much more normal-looking distribution (though its a bit tricky to work its variance out if you don't work out the exact distribution - one nice feature of using a version with nearly all one or the other statistic is you can use an existing normal approximation more easily, even if it's not as nice a distribution).]
This same approach for getting 'nicer' significance levels (and p-values) can work with other tests; I've seen it used with a sign test (breaking ties with an appropriately rescaled signed-rank statistic) for example.