Approximate equilibria in large games
Abstract/Contents
- Abstract
- The complexity of studying Nash equilibrium in large games often scales with the size of the system: as it increases, computing the exact Nash equilibrium can soon become intractable. However, when the number of players in the system approaches infinity and no individual player has a significant impact on the system, we can approximate the system by considering each single player no longer playing against other individual players but a single aggregation of all other players. In this paper, we apply this idea to study and approximate Nash equilibria in two large scale games. In part I, we consider a model of priced resource sharing that combines both queueing behavior and strategic behavior. We study a priority service model where a single server allocates its capacity to agents in proportion to their payment to the system, and users from different classes act to minimize the sum of their cost for processing delay and payment. As the exact processing time of this system is hard to compute and cannot be characterized in closed form, we introduce the concept of aggregate equilibrium to approximate the exact Nash equilibrium, by assuming each individual player plays against a common aggregate priority that characterizes the large system. We then introduce the notion of heavy traffic equilibrium as an alternative approximation of the Nash equilibrium, derived by considering the asymptotic regime where the system load approaches capacity. We show that both aggregate equilibrium and heavy traffic equilibrium are asymptotically exact in heavy traffic. We present some numerical results for both approximate equilibria, and discuss efficiency and revenue, and in particular provide a bound for the price of anarchy of the heavy traffic equilibrium. In part II, we study the reputation system of large scale online marketplace. We develop a large market model to study reputation mechanisms in online marketplaces. We consider two types of sellers: commitment sellers, who are intrinsically honest but may be unable to accurately describe items because of limited expertise; and strategic sellers, who are driven by a profit maximization motive. We focus on stationary equilibria for this dynamic market, in particular, on separating equilibria where strategic sellers are incentivized to describe the items they have for sale truthfully, and characterize the conditions under which such equilibria exist. We then complement our theoretical results with computational analysis and provide insights on the features of markets that may incentivize truthfulness in equilibrium.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2012 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Wu, Yu, (Quantitative analyst) |
|---|---|
| Associated with | Stanford University, Department of Management Science and Engineering |
| Primary advisor | Johari, Ramesh, 1976- |
| Thesis advisor | Johari, Ramesh, 1976- |
| Thesis advisor | Aperjis, Christina |
| Thesis advisor | Bambos, Nicholas |
| Advisor | Aperjis, Christina |
| Advisor | Bambos, Nicholas |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Yu Wu. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Ph.D. Stanford University 2012 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Yu Wu
- 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...