Online algorithms for markets

The thesis consists of two parts, both dealing with issues of uncertainty and incentives in markets. In the first part we examine the online properties of markets. In most of the Mechanism Design literature, markets are studied under the assumption that all participants are present at the same time and can seamlessly interact with each other. This may not always be the case in practice. We consider markets where buyers and sellers appear in sequence, one after another, without overlapping and it is the duty of an intermediary to coordinate with them. We take the role of that intermediary and our goal is redistribute items among them to maximise certain objectives, namely the profit, social welfare or gain from trade. We focus on posted price mechanisms, which are robust and truthful. There are two natural, complementary variants of the order of arrival of the agents. In the first case, an adversary dictates their order, but the intermediary has prior, distributional information about their valuations, similar to the prophet inequality setting. In the second, the adversary selects their valuations but their order is a uniformly random permutation. We obtain asymptotically tight worst-case guarantees for both cases, under a competitive analysis benchmark. In the second part, we study the strategic implications that arise from adding one extra option to the miners participating in the bitcoin proto- col. We propose that when adding a block, miners also have the ability to pay forward an amount to be collected by the first miner who successfully extends their branch, giving them the power to influence the incentives for mining. We formulate a stochastic game for the study of such incentives and show that with this added option, smaller miners can guarantee that the best response of even substantially more powerful miners is to follow the expected behavior intended by the protocol designer. Moreover, pay-forward can be used to alleviate the predicted instability when block rewards are small compared with respect to transaction fees, by smoothing out the variability of the rewards collected from transaction fees.