Chung, Christine
(2009)
Evolutionary Solutions and Internet Applications for Algorithmic Game Theory.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
The growing pervasiveness of the internet has created a new class of algorithmic problems: those in which the strategic interaction of autonomous, self-interested entities must be accounted for. So motivated, we seek to (1) use game theoretic models and techniques to study practical problems in load balancing, data streams and internet traffic congestion, and (2) demonstrate the usefulness of evolutionary game theory's adaptive learning model as an analytical and evaluative tool.First we consider the evolutionary game theory concept of stochastic stability, and propose the price of stochastic anarchy as an alternative to the price of anarchy for quantifying the cost of having no central authority. Unlike Nash equilibria, stochastically stable states are the result of natural dynamics of large populations of computationally bounded agents, and are resilient to small perturbations from ideal play. To illustrate the utility of stochastic stability, we study the load balancing game on related machines, which has an unbounded price of anarchy, even in the case of two jobs and two machines. We show that in contrast, even in the general case, the price of stochastic anarchy is bounded.Next, we propose auction-based mechanisms for admission control of continuous queries to a Data Stream Management System. When submitting a query, each user also submits a bid: how much she is willing to pay for her query to run. Our mechanisms must admit queries and set payments in a way that maximizes system revenue while incentivizing customers to use the system honestly. We propose several manipulation-resistant payment mechanisms and prove that one guarantees a profit close to a standard profit benchmark, and the others perform well experimentally.Finally, we study the long standing problem of congestion control at bottleneck routers on the internet. We examine the effectiveness of commonly-used queuing policies when each network endpoint is self-interested and has no information about the other endpoints' actions or preferences. By employing evolutionary game theory, we find that while bottleneck routers face heavy congestion at stochastically stable states under policies being currently deployed, a practical policy that was recently proposed yields fair and efficient conditions with no congestion.
Share
Citation/Export: |
|
Social Networking: |
|
Details
Item Type: |
University of Pittsburgh ETD
|
Status: |
Unpublished |
Creators/Authors: |
|
ETD Committee: |
|
Date: |
30 September 2009 |
Date Type: |
Completion |
Defense Date: |
10 June 2009 |
Approval Date: |
30 September 2009 |
Submission Date: |
28 July 2009 |
Access Restriction: |
No restriction; Release the ETD for access worldwide immediately. |
Institution: |
University of Pittsburgh |
Schools and Programs: |
Dietrich School of Arts and Sciences > Computer Science |
Degree: |
PhD - Doctor of Philosophy |
Thesis Type: |
Doctoral Dissertation |
Refereed: |
Yes |
Uncontrolled Keywords: |
Adaptive Learning; Algorithmic Game Theory; Data Streams; Evolutionary Game Theory; Load Balancing; Network Router Congestion |
Other ID: |
http://etd.library.pitt.edu/ETD/available/etd-07282009-150835/, etd-07282009-150835 |
Date Deposited: |
10 Nov 2011 19:54 |
Last Modified: |
15 Nov 2016 13:47 |
URI: |
http://d-scholarship.pitt.edu/id/eprint/8691 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |