This paper takes a game theoretic approach to the design and analysis of online algorithms and illustrates the approach on the finite-horizon ski-rental problem. This approach allows beyond worst-case analysis of online algorithms. First, we define "subgame optimality" which is stronger than worst case optimality in that it requires the algorithm to take advantage of an adversary not playing a worst case input. Algorithms only focusing on the worst case can be far from subgame optimal. Second, we consider prior-independent design and analysis of online algorithms, where rather than choosing a worst case input, the adversary chooses a worst case independent and identical distribution over inputs. Prior-independent online algorithms are generally analytically intractable; instead we give a fully polynomial time approximation scheme to compute them. Highlighting the potential improvement from these paradigms for the finite-horizon ski-rental problem, we empirically compare worst-case, subgame optimal, and prior-independent algorithms in the prior-independent framework.

Performance incentives tied to joint outcomes — such as equity for startup executives or bonuses for marketing teams — are a common tool for motivating teams. How should such incentive schemes be designed and how should they take into account the team's production function? We examine these questions in a simple non-parametric model of a team working on a joint project. Each member of the team chooses a costly effort level. These actions jointly determine a real-valued team performance according to a sufficiently smooth, increasing function of the efforts, which may entail interactions such as complementarities among agents' efforts. Any performance level determines a probability distribution over observable project outcomes.

Forecast aggregation combines the predictions of multiple forecasters to improve accuracy. However, the lack of knowledge about forecasters' information structure hinders optimal aggregation. Given a family of information structures, robust forecast aggregation aims to find the aggregator with minimal worst-case regret compared to the omniscient aggregator. Previous approaches for robust forecast aggregation rely on heuristic observations and parameter tuning. We propose an algorithmic framework for robust forecast aggregation. Our framework provides efficient approximation schemes for general information aggregation with a finite family of possible information structures. In the setting considered by Arieli et al. [2018] where two agents receive independent signals conditioned on a binary state, our framework also provides efficient approximation schemes by imposing Lipschitz conditions on the aggregator or discrete conditions on agents' reports. Numerical experiments demonstrate the effectiveness of our method by providing a nearly optimal aggregator in the setting considered by Arieli et al. [2018].

Equity compensation is widely used to motivate members of a team, such as a startup, to work toward a common goal. A natural question, about which little is known, is how the structure of collaborations should influence the design of equity compensation. We analyze this problem in a standard quadratic-payoffs network game model of production with heterogeneous complementarities. Each member of the team chooses a level of costly effort. This effort makes a "standalone" contribution to the firm's output, but there are also production complementarities: some pairs of workers generate an output proportional to the product of their efforts. In our model, the pattern of these complementarities is exogenously given and defines a network.

Last-mile is the centerpiece of broadband connectivity, as poor last-mile performance generally translates to poor quality of experience. In this work we investigate last-mile latency using traceroute data from RIPE Atlas probes located in 646 ASes and focus on recurrent performance degradation. We find that in normal times probes in only 10% ASes experience persistent last-mile congestion but we recorded 55% more congested ASes during the COVID-19 outbreak. Persistent last-mile congestion is not uncommon, it is usually seen in large eyeball networks and may span years. With the help of CDN access log data, we dissect results for major ISPs in Japan, the most severely affected country in our study, and ascertain bottlenecks in the shared legacy infrastructure.

Internet measurement research frequently needs to map infrastructure components, such as routers, to their physical locations. Although public and commercial geolocation services are often used for this purpose, their accuracy when applied to network infrastructure has not been sufficiently assessed. Prior work focused on evaluating the overall accuracy of geolocation databases, which is dominated by their performance on end-user IP addresses. In this work, we evaluate the reliability of router geolocation in databases. We use a dataset of about 1.64M router interface IP addresses extracted from the CAIDA Ark dataset to examine the country- and city-level coverage and consistency of popular public and commercial geolocation databases. We also create and provide a ground-truth dataset of 16,586 router interface IP addresses and their city-level locations, and use it to evaluate the databases' accuracy with a regional breakdown analysis. Our results show that the databases are not reliable for geolocating routers and that there is room to improve their country- and city-level accuracy. Based on our results, we present a set of recommendations to researchers concerning the use of geolocation databases to geolocate routers.