Information Procurement and Delivery: Robustness in Prediction Markets and Network Routing.

Abstract

In this dissertation we address current problems in information procurement and delivery. Uncertainty commonly reduces the efficacy of information procurement systems, such as prediction markets, and information delivery systems, such as Internet backbone networks. We address the problems of uncertainty by designing robust algorithms and protocols that function well under uncertainty.

Telecommunication backbone networks are used for delivering information across the Internet. Current backbone networks mostly employ protocols that include sender-receiver based congestion control. However, as protocols that do not have congestion control available become more prevalent, the network routers themselves must perform congestion control. In order to maximize network throughput, routing policies for backbone networks that take into account router based congestion control must be devised. We propose a mathematical model that can be used to design improved routing policies, while also taking into account existing flow management methods. Our model incorporates current active congestion control methods, and takes into account demand uncertainty when creating routing policies. The resulting routing policies tended to be at least 20% better than those currently used in a real world network in our experiments.

Prediction markets are information aggregation tools in which participants trade on the outcome of a future event. One commonly used form of prediction market, the market scoring rule market, accurately aggregate the beliefs of traders assuming the traders are myopic, meaning they do not consider future payoffs, and are risk neutral. In currently deployed prediction markets neither of these assumptions typically holds. Therefore, in order to analyze the effectiveness of such markets, we look at the impact of non-myopic risk neutral traders, as well as risk averse traders on prediction markets. We identify a setting where non-myopic risk neutral traders may bluff, and propose a modified prediction market to disincentivize such behavior. Current prediction markets do not accurately aggregate all risk averse traders' beliefs. Therefore, we propose a new prediction market that does. The resulting market exponentially reduces the reward given to traders as the number of traders increases; we show that this exponential reduction is necessary for any prediction market that aggregates the beliefs of risk averse traders.