Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Subject: search.filters.subject.Matching

Search Results

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    ALLOCATIONS IN LARGE MARKETS
    (2017) Esfandiari, Hossein; Hajiaghayi, MohammadTaghi; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Rapid growth and popularity of internet based services such as online markets and online advertisement systems provide a lot of new algorithmic challenges. One of the main challenges is the limited access to the input. There are two main reasons that algorithms have limited data accessibility. 1) The input is extremely large, and hence having access to the whole data at once is not practical. 2) The nature of the system forces us to make decisions before observing the whole input. Internet-enabled marketplaces such as Amazon and eBay deal with huge datasets registering transaction of merchandises between lots of buyers and sellers. It is important that algorithms become more time and space efficient as the size of datasets increase. An algorithm that runs in polynomial time may not have a reasonable running time for such large datasets. In the first part of this dissertation, we study the development of allocation algorithms that are appropriate for use with massive datasets. We especially focus on the streaming setting which is a common model for big data analysis. In the graph streaming, the algorithm has access to a sequence of edges, called a stream. The algorithm reads edges in the order in which they appear in the stream. The goal is to design an algorithm that maintains a large allocation, using as little space as possible. We achieve our results by developing powerful sampling techniques. Indeed, one can implement our sampling techniques in the streaming setting as well as other distributed settings such as MapReduce. Giant online advertisement markets such as Google, Bing and Facebook raised up several interesting allocation problems. Usually, in these applications, we need to make the decision before obtaining the full information of the input graph. This enforces an uncertainty on our belief about the input, and thus makes the classical algorithms inapplicable. To address this shortcoming online algorithms have been developed. In online algorithms again the input is a sequence of items. Here the algorithm needs to make an irrevocable decision upon arrival of each item. In the second part of this dissertation, we aim to achieve two main goals for each allocation problem in the market. Our first goal is to design models to capture the uncertainty of the input based on the properties of problems and the accessible data in real applications. Our second goal is to design algorithms and develop new techniques for these market allocation problems.
  • Thumbnail Image
    Item
    Essays on Matching Markets and Their Equilibria
    (2016) Utgoff, Naomi M.; Ausubel, Lawrence M; Economics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Matching theory and matching markets are a core component of modern economic theory and market design. This dissertation presents three original contributions to this area. The first essay constructs a matching mechanism in an incomplete information matching market in which the positive assortative match is the unique efficient and unique stable match. The mechanism asks each agent in the matching market to reveal her privately known type. Through its novel payment rule, truthful revelation forms an ex post Nash equilibrium in this setting. This mechanism works in one-, two- and many-sided matching markets, thus offering the first mechanism to unify these matching markets under a single mechanism design framework. The second essay confronts a problem of matching in an environment in which no efficient and incentive compatible matching mechanism exists due to matching externalities. I develop a two-stage matching game in which a contracting stage facilitates subsequent conditionally efficient and incentive compatible Vickrey auction stage. Infinite repetition of this two-stage matching game enforces the contract in every period. This mechanism produces inequitably distributed social improvement: parties to the contract receive all of the gains and then some. The final essay demonstrates the existence of prices which stably and efficiently partition a single set of agents into firms and workers, and match those two sets to each other. This pricing system extends Kelso and Crawford's general equilibrium results in a labor market matching model and links one- and two-sided matching markets as well.
  • Thumbnail Image
    Item
    ESSAYS ON PHARMACEUTICAL ADVERTISING
    (2015) DAI, WEJIA (DAISY); JIN, GINGER Z; SWEETING, ANDREW; Economics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The dissertation focuses on two distinctive issues in pharmaceutical advertising. One on the matching choices between advertisers and advertising agencies, and the other on the effect of paid-link advertising on consumer search for online pharmacies. The goal of this dissertation is to empirically uncover the underlying economic mechanisms. Moreover, the analysis of matching problem provides new insights on the formation of vertical relationships between clients and professional service agencies and has implications for professional service market consolidations. And the examination of consumer searches for pharmaceuticals online sheds lights on consumers' concerns over quality and affordability of prescription drugs and draws attention on advertising regulation. In the first two chapters, I focus on two essential features of the market for professional services. One is the necessary mutual agreement in forming relationships, and the other is that a client perceives conflict when hiring the same service agency as his product market competitor. To incorporate these two features, I construct and estimate a two-sided matching model and allow agents' choices to depend on conflict. The results show that conflict does indeed reduce match surplus, and the reduction is greater for a pair of agents who have matched with each other in the previous period. Also, preserving previously formed matches yields much higher surplus than forming new matches. Based on these estimates, I conduct a counterfactual exercise to illustrate the effect of conflict on allocation of matches and another counterfactual exercise to illustrate the effect of a merger between advertising agencies on market equilibrium. In the third chapter, coauthored with Matthew Chesnes and Ginger Jin, we examine how government's sudden ban of foreign online pharmacies from paid search on Google and other search engines changes consumer searches for the banned websites. Using click-through data from comScore, we find that non-NABP-certified pharmacies receive fewer clicks after the ban, and this effect is heterogenous. In particular, pharmacies not certified by the NABP but certified by other sources, referred to as tier-B sites, experience a reduction in total clicks, and some of their lost paid clicks are replaced by organic clicks. These results have implications for the change in consumer search cost and health concern.
  • Thumbnail Image
    Item
    Essays on Matching and Auction Theory
    (2011) Johnson, Terence R.; Ausubel, Lawrence; Vincent, Daniel; Economics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation uses mechanism design theory to show how a matchmaker should design two-sided matching markets when agents are privately informed about their qualities or characteristics as a partner and can make monetary payments. Chapter Two uses a mechanism design approach to derive sufficient conditions for assortative matching to be profit-maximizing for the matchmaker or maximize social welfare, and then shows how to implement the optimal match and payments through two-sided position auctions as a Bayesian Nash equilibrium. Chapter Three broadens these results by showing how the implementation concept can be relaxed to ex post equilibrium through the use of market designs similar to the Vickrey-Clarke-Groves mechanism, as well as implemented through the use of dynamic games. Chapter Four shows how the ideas used in Chapters Two and Three can be extended to a multi-dimensional type framework, moving away from the supermodular paradigm that is the workhorse of models of matching with incomplete information.
  • Thumbnail Image
    Item
    Causal Inference with Group-Based Trajectories and Propensity Score Matching: Is High School Dropout a Turning Point?
    (2006-04-28) Sweeten, Gary Allen; Bushway, Shawn D; Criminology and Criminal Justice; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Life course criminology focuses on trajectories of deviant or criminal behavior punctuated by turning point events that redirect trajectories onto a different path. There is no consensus in the field on how to measure turning points. In this study I ask: Is high school dropout a turning point in offending trajectories? I utilize two kinds of matching methods to answer this question: matching based on semi-parametric group-based trajectory models, and propensity score matching. These methods are ideally suited to measure turning points because they explicitly model counterfactual outcomes which can be used to estimate the effect of turning point events over time. It has been suggested that dropout is the end result of a process of disengagement from school. In order to assess the effect of the event of dropout, it is necessary to separate dropout from the processes that lead to it. The extent to which this is accomplished by matching is assessed by comparing dropouts to matched non-dropouts on numerous background characteristics. As such, it is desirable to use a wide range of measures to compare the two groups. I use the National Longitudinal Survey of Youth 1997 to address this question. Delinquency is measured in two ways: a six-item variety scale and a scale based on a graded-response model. Dropout is based on self-reports of educational attainment supplemented with official transcripts provided by high schools. Because of the breadth of topics covered in this survey, it is very well-suited to matching methods. The richness of these data allows comparisons on over 300 characteristics to assess whether the assumptions of matching methods are plausible. I find that matching based on trajectory models is unable to achieve balance in pre-dropout characteristics between dropouts and non-dropouts. Propensity score matching successfully achieves balance, but dropout effects are indistinguishable from zero. I conclude that first-time dropout between the ages of 16 and 18 is not a turning point in offending trajectories. Implications for life course criminology and dropout research are discussed.