Edit: Of course there have been barter based markets, but aren't markets actually more effective when there is a central authority?
A market is a way to organize a group of people in a decentralized way, but its existence and correct operation requires a different, centralized group that manages it. Market participants are decentralized, market regulators are not. Now, the solution for the "what if I don't want centralization in the market regulation space?" problem is recursion. You create a market for markets.
What happens if you don't centralize? You get something like global trade, which is a meta-market for national trade markets (which are centralized). Global trade is decentralized - in the sense that men with most guns tell everyone else what to do, because there's no central authority to prevent that.
Markets (at least, free markets) are exactly a way of organizing a group without the need for a central authority.