Learning and incentives in computer science
Abstract/Contents
- Abstract
- In this thesis we look at topics in algorithmic game theory, with influences from learning theory. We use tools and insights from game theory to look at areas in computer science, such as machine learning and the bitcoin blockchain, that have been developed incognizant of incentives for selfish behavior. Here we 1) show that there are incentives to behave in a way that's harmful for the system, 2) give mechanisms where the incentives for the individual and group are aligned, and 3) measure how harmful (having to account for) selfish behavior is. In particular we study the problem of online prediction with expert advice, where we show that when experts are selfish and care about their reputation, the design of incentive compatible algorithms is tightly coupled to strictly proper scoring rules. We give algorithms that have good regret guarantees, and we prove that it is not possible to match regret guarantees for honest experts. For Bitcoin, we show that the way rewards are shared in mining pools can lead to miners strategically hiding work to improve their payout. This holds true even in the absence of outside options for miners, such as other pools or solo mining. We give a novel reward sharing function that does not have perverse incentives, and analyze its performance analytically and through simulations. On the other hand we look at how data can be used in a variety of game theory applications. We ask the questions 1) how can we use data to replace standard informational assumptions in auction theory, 2) how much data do we need for good results in this area, 3) how can we use data to learn about the utilities of agents when we observe behavior, and finally (as misrecorded data may lead algorithms astray) 4) how can we find anomalies in a data set in an unsupervised manner? For the first two questions we look at position auction environments where we give the first computationally efficient algorithm for i.i.d.~bidders with irregular value distributions, that achieves revenue arbitrarily close to optimal using polynomial samples. Due to the low sample complexity, our approach leads to a no-regret algorithm in the online setting. To address the third question, we give a computationally efficient algorithm that computes, given a correlated equilibrium (which may be a pure or mixed Nash equilibrium), the set of utilities that are consistent with it. Finally, we give an unsupervised anomaly detection algorithm that runs in a stream, and we show its performance through experiments on real and synthetic data.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Schrijvers, Okke |
|---|---|
| Associated with | Stanford University, Department of Computer Science. |
| Primary advisor | Roughgarden, Tim |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Boneh, Dan |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Lambert, Nicolas, 1979- |
| Advisor | Boneh, Dan |
| Advisor | Goel, Ashish |
| Advisor | Lambert, Nicolas, 1979- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Okke Schrijvers. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Okke Joost Schrijvers
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...