Computational efficiency in internet economics and resource allocation
Abstract/Contents
- Abstract
- The Internet has created an environment for operations research to play a role in solving practical problems with large networks and a tremendous amount of data. In this thesis, I am interested in developing mathematical principles and computational methodologies underlying the huge multiple-agent environment created by social economic systems over the Internet. The three major topics covered are: 1. Social network advertising, modeling, and pricing: I propose an analytic model and solution for advertisement on a social network based on the concept of forwarding power. Forwarding power is a concept I derive to quantify the amount of information each node is able to gather from the network, or the power to forward information from its predecessors. In other words, the forwarding power is an individual's ability to forward others' opinions. Based on this new concept for a social network, I formulate an optimization model that maximize social welfare, a goal often favored by system designers. This has the advantage of being a convex program that can be solved in polynomial time. Furthermore, it derives a polynomial-time, implementable, and truthful mechanism for advertisement pricing. 2. Envy-free resource allocation: I study the computational efficiency of the envy-free cake-cutting problem. A solution to this problem would be a resource allocation among several partners such that no one entity would envy the anothers' allocated part. I am interested in understanding the query complexity to achieve this task, under both the oracle function model as well as the polynomial function model. I characterize the complete query complexity by developing an (asymptotically) matching query bound for the oracle function model. I also prove PPAD-completeness for the query complexity under the polynomial time function model. In deriving these results, I developed a comprehensive characterization of query complexity for discrete fixed points and the Tucker problem. 3. Finding pure Nash equilibria in supermodular games: A supermodular game abstracts relations in the players' strategic alternatives, among the participation agents. Tarski's fixed point on lattices forms the mathematical foundation for the supermodular game. For both supermodular games and Taski's fixed points, I find the first efficient algorithm to find one solution and prove hardness results to determine uniqueness (matching bounds for query complexity in the oracle function model and Co-NP-hardness in the polynomial function model). The modeling techniques, fundamental mathematical insights, and algorithmic tools developed in this thesis are expected to be useful for many related applications in Internet economics and resource allocation.
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 | Qi, Qi |
|---|---|
| Associated with | Stanford University, Department of Management Science and Engineering |
| Primary advisor | Ye, Yinyu |
| Thesis advisor | Ye, Yinyu |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Saberi, Amin |
| Advisor | Goel, Ashish |
| Advisor | Saberi, Amin |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Qi Qi. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2012. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Qi Qi
- 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...