Optimization and decision-making under uncertainty
Abstract/Contents
- Abstract
- We consider several online and repeated decision problems with uncertainty features in resource allocation, energy storage management and internet advertising using worst-case and stochastic models. In the first part, we use worst-case models to design and analyze online algorithms that make irrevocable decisions without any future information. In the online resource allocation problem, a seller allocates items that can be produced at non-decreasing marginal costs per unit to buyers arriving in an online fashion. The objective is to maximize the social welfare which is the sum of the buyers' values less the total production cost. We then consider the energy storage management problem motivated by applications of energy storage networks in smart grids. Given renewable power supplies that generate power unpredictably, a grid operator wants to route power from these online power supplies to offline consumer demands using storage units subject to decay factors. The objective is to maximize the total utility of satisfied demands less the total production cost of routed power. In the second part, we consider the problems of budget management and contract design in internet advertising using stochastic models where a publisher allocates ad impressions given distributional information of advertisers' private valuations. In the budget management problem, the publisher manages advertisers' budgets on their behalf and adjusts allocations and payments such that the advertisers' cumulative expenditures are at most their budgets. Our goal is to study various budget management mechanisms on the bases of the publisher's profit, advertisers' utilities, incentive compatibility properties and uniqueness and stability of an equilibrium notion. For the contract design problem for selling online display advertisements, the publisher wants to sell ad impressions by bundling them via contracts before selling via auctions. The publisher wants to design a sequence of contracts that yields the maximum revenue, where advertisers are assigned priorities and buy bundles of impressions that are not yet purchased by those with higher priorities. Our contributions are both theoretical and empirical. We develop new algorithms and mechanisms with near optimality guarantees and provide characterizations of optimal solutions. We also provide empirical studies based on real datasets to validate our theoretical findings and derive further insights.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2018; ©2018 |
| Publication date | 2018; 2018 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Kim, Anthony |
|---|---|
| Degree supervisor | Charikar, Moses |
| Degree supervisor | Saberi, Amin |
| Thesis advisor | Charikar, Moses |
| Thesis advisor | Saberi, Amin |
| Thesis advisor | Valiant, Gregory |
| Degree committee member | Valiant, Gregory |
| Associated with | Stanford University, Computer Science Department. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Anthony Kim. |
|---|---|
| Note | Submitted to the Computer Science Department. |
| Thesis | Thesis Ph.D. Stanford University 2018. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2018 by Anthony Eli Kim
- 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...