Algorithms for information and contract design in multi-agent network settings

This thesis considers problems that arise from an asymmetric distribution of information through an algorithmic lens. In these problems, a principal has to interact with multiple selfish agents whose actions determine her outcome. We study two approaches by which the principal can steer their actions in her favor: information design and contract design. In information design, there is an unknown state of the world that influences the agents' actions. The principal can (partially) reveal information about the true state to all agents by issuing a signal. Each agent then updates his belief about the true state and chooses an action. In contract design, the agents take hidden actions. This induces a probability distribution over possible outcomes. The principal may incentivize agents to take certain actions that increase her expected outcome through outcome-dependent payments to the agents. We examine the problem of computing optimal signals and contracts for the principal. First, we study information design for a benevolent principal in nonatomic network congestion games where all edges have affine cost functions. We examine two models. In the first model, the offsets of all cost functions are state-dependent and thus stochastic. We construct a reduction from optimal signaling to computing an optimal collection of supports for the resulting Wardrop equilibria. If only two states are possible, this allows us to efficiently compute optimal signaling strategies when the size of such a collection is bounded by a polynomial in the input size. By using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity settings on parallel-edge networks with a constant number of commodities and states. We also provide a computational study suggesting that the collection size is small in realistic networks. In the second model, the travel demand is state-dependent. For single-commodity networks, we devise a fully polynomial-time approximation scheme (FPTAS) given only two possible states. Moreover, we show that many results for the first model also carry over to this setting. Secondly, we analyze an approach of information design in the opinion formation model by Friedkin and Johnsen (FJ). The unknown state of the world influences the initial opinions of n agents based on which an equilibrium of public opinions emerges. We show that there are simple optimal strategies for many natural principal objectives. After that, we focus on the general class of range-based objectives with respect to desired opinion ranges for each agent. We provide efficient algorithms for several cases, e. g. , when there is only a polynomial number of range combinations that lead to positive value for the principal. For the general case, we show a simple n-approximation for subadditive range-based objectives and that obtaining an n^1-c-approximation is NP-hard for any c > 0, even for additive ones. Lastly, we consider contract design in the FJ model. Each agent has a set of possible actions in form of initial opinions with associated costs for him. The principal wants to maximize the sum of the agents' public opinions in equilibrium. We focus on optimal linear contracts. We show that the problem is free of externalities for the agents and hence the optimization can be done with respect to each agent independently. We find that the problem is NP-hard and obtain an FPTAS.