I only have the experience of one game published, but I can tell what I've done and the results I've had.
Before starting promotion:
The app/game has to be good. If you make a lot of promotion over a poor app you'll get a lot of uninstalls and bad reviews.
Make a good icon and a good landing page, with good screenshots. People is more likely to download something if it's eye catching. If have a bad icon, you can do a campaign and show 100K impressions of your app, but the conversion rate will be very low.
You'll have to do a little ASO, finding the right kewords and make a good description using those words, also translating is good...
Now promote it.
You have free methods, like social advertisement (facebook...), send your game to some websites, youtubers... and you can do some review exchange with other developers (
reviewsmotion is good for that). Try to publish your app/game in other stores, I tried opera store and I got a lot of downloads in the first month (about 30 a day, while in google play it was way less downloads), after first month downloads become sporadic in opera.
And then you have paid methods. I tried appbrain for my first campaign, and liked it because it's a cost per install campaign. Wich means that you pay only every time your game is installed. You can target countries and change the bid (the cost of each install). If your bid is too low for the countries you're targeting, the downloads will be very very slow because you'll have very few impressions. ie: If you target USA you'll have to pay more money per install than if you target India...
Then you have incentivized installs. I've tried
ayetstudios, and
app2top is also very popular. App2top are bots, no real users, that's why I haven't tried it. Ayet is based in a rewarding method. There is an app (cashpirate) in wich users are rewarded every time they download an app (they ge a little $) So be aware that they will download your app because of the reward, not because they like it. So you'll have a lot of installs followed by almost the same number of uninstalls (some users may like it and keep installed if the app/game is good, but not many)
This method is cheaper, and it's used basically to get more downloads and to get higher in charts. It's better to do this in the first month, because your app can be charted in top new apps-games category in some country, wich will give you more organic (natural) installs.
In my case I was getting about 50 installs a day, and after a 50$ high retention campaign (users have to keep app installed for 3 days) I doubled it.
I must say that I made another campaign 2 weeks later with almost no visible results. I think it's more effective if you target only one country (don't do do worldwide campaigns) and get a lot of downloads in one day, because this way you have more chances to be featured in any chart this way.
And that's what I did. Now let me tell what happened next:
I stopped any promotion after the first month because I didn't see great results and was feeling like I was wasting my money (I spent about $200 in promotion) and let the game grow organically. Slowly I was getting more and more users, but poor numbers in a so populated market. And without doing anything, about 2 weeks ago I don't know what happened but my game "exploded". I mean, suddenly the installs started to grow and grow and now I'm getting about 3000 - 5000 installs a day. With these numbers I've allready recovered my investment and soon will cross the 50K installs line.
I really don't know what's going on and and if it will last, but now I'm crossing my fingers and have stopped the development of any other game to focus in updates and upgrades for my game to try to keep this going...
Maybe if I hadn't done the promotion now this wouldn't be happening, who knows... there are millions af apps and google is constantly changing things, so all of this is a bit unpredictable.