How close does it get?: From near-optimal network algorithms to suboptimal equilibrium outcomes

In this thesis, we first consider a pricing problem of links in networks. We prove inapproximability results and develop approximation algorithms with approximation guarantees that are best possible. Secondly, given a network where each edge has a certain probability of existence, we want to determine the path that has the highest probability of being the shortest path. We prove hardness results and develop a Monte Carlo-type algorithm that, with high probability, returns the correct path. Next, we examine the problem of scheduling jobs on related machines while minimizing the sum of completion times. The approximation guarantee of a simple greedy algorithm is the same as the price of anarchy (PoA) of a game-theoretic version of the problem. We outline a technique that can recover previously known PoA bounds and has the potential to improve them. Further, we analyze the PoA with respect to the social welfare of a first-price auction hosted by a corrupt auctioneer. They approach winning bidders with the offer to lower their bids in return for a fraction of the gains. After obtaining tight robust PoA bounds, we make a no-overbidding assumption, yielding a more fine-grained PoA landscape. Finally, we study the problem of designing truthful mechanisms for players that are (partially) altruistic. We give both a characterization of and a recipe for truthful mechanisms and observe that smaller payments need to be extracted from the players to ensure truthfulness