Companies should require a "reputation score" certified by multiple independent auditors, before being allowed to host an app store/game store.

Having a continued history of market position abuse would be an instant fail on that certification process.

And how exactly would that encourage competition ?