Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Evolutionary Solutions and Internet Applications for Algorithmic Game Theory

Chung, Christine (2009) Evolutionary Solutions and Internet Applications for Algorithmic Game Theory. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

[img]
Preview
PDF
Primary Text

Download (1MB) | Preview

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:
Share |

Details

Item Type: University of Pittsburgh ETD
Status: Unpublished
Creators/Authors:
CreatorsEmailPitt UsernameORCID
Chung, Christinecc95@cornell.edu
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairPruhs, Kirkkirk@cs.pitt.eduKRP2
Committee MemberLabrinidis, Alexandroslabrinid@cs.pitt.eduLABRINID
Committee MemberBlum, Avrimavrim@cs.cmu.edu
Committee MemberChrysanthis, Panospanos@cs.pitt.eduPANOS
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 View Item