In the analysis of current online ad auctions essential parameters such as click-through rates are often assumed to be known. The disregard of the uncertainty that is present in reality leads to several serious problems. In the talk we will highlight two: (i) there is no principled exploration of new ads, and (ii) there is no incentive for advertisers to only subscribe to well targeted key-words. In fact, there is an interesting opportunity for very poorly targeting advertisers to exploit this fact. We present a new auction that solves both problems. The key trick for this auction is that advertisers are not only requested to submit a bid, but also a belief over their own click-through rate.