Dissertation/Thesis Abstract

Select problems at the intersection of computer science and economics
by Naroditskiy, Victor, Ph.D., Brown University, 2010, 169; 3430201
Abstract (Summary)

We apply computer science techniques to try to solve a selection of problems that arise in economics and electronic commerce. The problems we address and our results are summarized below.

The first problem is from the field of Mechanism Design. The goal is to find a procedure for allocating identical items among agents with private values in the manner that maximizes the total utility of the agents. We approach this problem computationally: solutions are found algorithmically rather than through mathematical derivations. Our computational approach yields a nearly optimal solution greatly improving prior results. In the case with 3 agents and 2 items, we were able to find a provably optimal solution.

Next, we address a game-theoretic problem of finding Nash Equilibria in auctions. We investigate when a computational procedure finds an equilibrium in first and second price auctions with discrete bids and values.

The rest of the thesis is devoted to automated decision making in electronic commerce domains. Three domains are considered: sponsored search, supply chain management, and simultaneous auctions. The last two domains are studied in the context of the SCM and Travel divisions of the Trading Agent Competition (TAC).

Our contributions to automated decision making are both practical and theoretical. On the practical side, the bidding strategy we designed for sponsored search auctions is currently being used by a large advertiser. Our work on TAC Travel culminated in winning the competition in 2006. In the TAC SCM competition, the agent we built was among the top 5 out of over 20 agents almost every year of the competition. For theoretical contributions, we characterized optimal strategies for bidding in simultaneous auctions when prices are known and complemented this analysis with an empirical comparison of different strategies. We identified that bidding decisions in TAC SCM can be modeled as a non-linear knapsack problem and proved the asymptotic optimality of a greedy algorithm for solving a class of non-linear knapsack problems.

Indexing (document details)
Advisor: Greenwald, Amy
School: Brown University
School Location: United States -- Rhode Island
Source: DAI-B 71/11, Dissertation Abstracts International
Subjects: Finance, Computer science
Keywords: Automated decision making, Bids, Intersection, Mechanism Design, Price auctions, Trading agents, Values
Publication Number: 3430201
ISBN: 978-1-124-30216-4
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy