While I agree with where you're coming from, I think you're overstating it just a little. It only seems like something that should be considered a public utility because Google has anticompetitively bundled what should be several distinct types of products together as one take-it-or-leave-it package. Android (really Google Play Services) should not be tied to the Play Store App (think how MS was forced to include a browser choice screen in the EU). Likewise the Play Store Curation/Hosting Service should not be tied to the Play Store App (ie Aurora store etc should work and be fully supported by Play Store Curation/Hosting Service through the Service having a well-documented open API). Then Play Store Curation/Hosting Service would have to compete on its own merits, rather than anticompetitive tying with two instances of Metcalfe's law (Android users plus app developers).