The same way it works with newspapers, I'd say. Check that it is there when you expect it to be there.

Even with newspapers advertisers don't simply accept the circulation numbers that the publishers report. They pay third parties to provide independent numbers. It's not just about whether the ad appears but rather knowing how many people saw it.

So maybe there could be 3rd party company to check such things. Also ads could be sold at auction. I.e. auction for 24h display of ad in header from $1 on some news site.

Actually that's not a bad idea. Why not hit the site that the ad's are reportedly on from some IP addresses unknown to the ad provider. Do this over and over again until you have enough data to assume that say 1/5th of impressions are you then compare that to a neutral 3rd party source (Google Analytics comes to mind) of the total hits for that day. 5000 hits / 1/5 of those are impressions of your ad = 1000 impressions. Compare this to the numbers provided by the ad provider itself. All you'd need to do is spot check and it should keep everyone honest. I'm surprised people don't do this already.

Independent Auditing happens in all kinds of industries and for all kinds of reasons

There is no reason a neutral 3rd party can not review logs, software, or other data to ensure in house ad metrics are accurate.

Advertisers can track clicks very easily on their own via google analytics and other platforms. What's so hard about that?

Because if it's CPM, then you're paying for users on the publisher who simply view it.

Advertisers have not cared much to date. For example the amount of money they pour into Facebook ads despite massive click fraud.

They could always use a platform that is pay-per-action, so that you aren't paying unless people actually buy things.

(I work on the ad systems team of an affiliate marketing company, where essentially all advertisement contracts are done on a PPA basis, rather than PPC)