Academic Commons

Theses Doctoral

Essays on Market Design and Auction Theory

Koh, Youngwoo

This dissertation consists of three essays on market design and auction theory. In the first chapter, we develop a model of decentralized college admissions in which students' preferences for colleges are uncertain, and colleges must incur costs when their enrollments exceed their capacities. Colleges' admission decisions then become a tool for strategic yield management, because the enrollment at a college depends on not only students' uncertain preferences but also other colleges' admission decisions. We find that colleges' equilibrium admission decisions exhibit "strategic targeting''---colleges may forgo admitting (even good) students likely sought after by the others and may admit (not as good) students likely overlooked by the others. Randomization in admissions may also emerge. The resulting assignment fails to be efficient (among students, among colleges and among all parties including colleges and students) and leads to justified envy among students. When the colleges consider multiple dimensions of students merits, their evaluations are unlikely to be perfectly correlated. In such a case, colleges may avoid head-on competition by distorting their evaluation to place excessive weight on less correlated dimensions, such as extra curricular activities and non-academic aspects of students' application portfolios. Restricting the number of applications or allowing for wait-listing might alleviate colleges' yield management problem, but the resulting assignments are still inefficient and admit justified envy. Centralized matching via Gale and Shapley's Deferred Acceptance algorithm eliminates colleges' yield management problem and justified envy among students and attains efficiency. It also attains the outcome that is jointly optimal among colleges, but some colleges may be worse off relative to decentralized matching. The second chapter studies a keyword auction model where bidders have constrained budgets. In the absence of budget constraints, Edelman, Ostrovsky, and Schwarz (2007) and Varian (2007) analyze "locally envy-free equilibrium'' or "symmetric Nash equilibrium'' bidding strategies in generalized second-price (GSP) auctions. However, bidders often have to set their daily budgets when they participate in an auction; once a bidder's payment reaches his budget, he drops out of the auction. This raises an important strategic issue that has been overlooked in the previous literature: Bidders may change their bids to inflict higher prices on their competitors because under GSP, the per-click price paid by a bidder is the next highest bid. We provide budget thresholds under which equilibria analyzed in Edelman, Ostrovsky, and Schwarz (2007) and Varian (2007) are sustained as "equilibria with budget constraints'' in our setting. We then consider a simple environment with one position and two bidders and show that a search engine's revenue with budget constraints may be larger than its revenue without budget constraints. In the third chapter, we study the procurement of an innovation in which firms exert effort and create innovations, where the quality of innovation is stochastic. Both the effort level and the quality of innovation are unverifiable, and the procurer cannot extract up-front payment from the firms. Given the uncertainty of quality realization, there is a trade-off regarding the number of participating firms in the procurement process: If many firms participate in the process, they may be discouraged from expending their initial investment because each of them has a small chance of winning (we call this incentive effect). At the same time, as the number of participants increases, the procurer has a growing chance of getting a higher quality because of the randomness of the quality realization (sampling effect). Therefore, the procurer faces a nontrivial problem of how many firms to invite in the procurement process. We consider two prominent contest mechanisms, a first-price auction and a fixed-prize tournament. We show that if the randomness is large enough, it is optimal for the buyer to invite as many firms as possible in both mechanisms, and the fixed-prize tournament outperforms the first-price auction. In the limit at which the randomness vanishes, inviting only two firms is optimal in both mechanisms, and the first-price auction outperforms the fixed-prize tournament. Under the first-price auction, we show that any equilibrium converges to an equilibrium as the randomness diminishes and provide a characterization of the limit equilibrium. We also provide a constructive example of a mixed-strategy equilibrium with two firms when the randomness is moderate.



  • thumnail for Koh_columbia_0054D_11470.pdf Koh_columbia_0054D_11470.pdf application/pdf 1.26 MB Download File

More About This Work

Academic Units
Thesis Advisors
Che, Yeon-Koo
Ph.D., Columbia University
Published Here
June 7, 2013