The use of "nofollow" on paid links helps to discourage manipulation of search rankings by site owners who have money to spend on SEO. That, in turn, helps to ensure a better search experience for users.
How do? Nofollow has been built into CMSs for years, and yet if you run a site using a popular one, you will get dozens of spam comments left every day. I don't think it's discouraging a thing. That may well have been Google's thinking, but I just don't see that it's what's actually happening.
I'll just point out that ads making money for the publisher and also being good for the user experience are not mutually exclusive.
Thank you! If you care about your users, you do not play games with their trust. That means NEVER linking to anything, for any reason, with any tag, unless it's of value to them.