We have a number of startups in our portfolio that build iOS and Android apps.
To my knowledge, none of them pay for traffic to their apps.
But they constantly get pitched by different 3rd parties with the promise of better exposure and distribution in the app store.
Some offer to buy low cost…
Discovery problem + quantifiable value of install is always going to lead to paid search and the like. Hopefully social becomes an increasingly important — and harder to game — vector across all search problems, but I don’t think it’s a substitute. (Viz “friend of installer targeting” on facebook, and the large amount of money Zynga spends on it.)