This dissertation examines how matching -- in marriage markets and labor markets -- can change under certain market circumstances and under different information provisions. The first two chapters analyze marriage market, with a particular focus on the impacts of cross-border marriage in marriage markets. Given the severely male-biased sex ratios in many Asian countries including China and India, demands for foreign brides are expected to grow in the near future. In the first chapter, I theoretically investigate the impacts of cross-border marriage on marital patterns and surplus division of couples. I use a frictionless transferable utility matching framework to analyze how cross-border marriage affects matching patterns and marital shares for couples. In the second chapter, I test the model's predictions, focusing on Taiwan (a wealthier side with male biased sex ratios) and Vietnam (a poorer side with balanced sex ratios in the marriage market). I find that cross-border marriages are predominantly made up of Taiwanese men and Vietnamese women; Taiwanese men are selected from the middle level of the socioeconomic status distribution, and Vietnamese women are positively selected. Moreover, cross-border marriage significantly affects men and women who stay in their own countries without engaging in cross-border marriage, by altering marriage rate, matching partners, and intra-household allocations within the households. My results suggest that changes in trade and immigration policies can have far-reaching implications on marital outcomes and women's bargaining power. The third chapter investigates job and jobseeker matching in labor market. Specifically, it explores whether inaccurate expectations of job seekers about their competitiveness contribute to poor job matching in developing countries. We utilize the largest online job portal in the Middle East and North Africa region to evaluate the effect of an intervention providing information about own competitiveness to job applicants. Providing information about the relative fit of an applicant's background for a particular job causes job seekers to apply for jobs that are better matches given their background. The effects of information are the largest among entry-level workers with higher levels of education, who generally face the highest unemployment rates in the region. The findings are consistent with the hypothesis that changes over time in demand for skills in the job market may lead to inaccurate expectations that hinder labor market matching. Improving the efficiency of online job search may be particularly welfare-enhancing in the Middle East and North Africa region given that the young, highly-educated subpopulation that faces the greatest labor market hurdles also has the highest level of internet connectedness.

Matching market design studies the fundamental problem of how to allocate scarce resources to individuals with varied needs. In recent years, the theoretical study of matching markets such as medical residency, public housing and school choice has greatly informed and improved the design of such markets in practice. Impactful work in matching market design frequently makes use of techniques from computer science, economics and operations research to provide end–to-end solutions that address design questions holistically. In this dissertation, I develop tools for optimization in market design by studying matching mechanisms for school choice, an important societal problem that exemplifies many of the challenges in effective marketplace design. In the first part of this work I develop frameworks for optimization in school choice that allow us to address operational problems in the assignment process. In the school choice market, where scarce public school seats are assigned to students, a key operational issue is how to reassign seats that are vacated after an initial round of centralized assignment. We propose a class of reassignment mechanisms, the Permuted Lottery Deferred Acceptance (PLDA) mechanisms, which generalize the commonly used Deferred Acceptance school choice mechanism and retain its desirable incentive and efficiency properties. We find that under natural conditions on demand all PLDA mechanisms achieve equivalent allocative welfare, and the PLDA based on reversing the tie-breaking lottery during the reassignment round minimizes reassignment. Empirical investigations on data from NYC high school admissions support our theoretical findings. In this part, we also provide a framework for optimization when using the prominent Top Trading Cycles (TTC) mechanism. We show that the TTC assignment can be described by admission cutoffs, which explain the role of priorities in determining the TTC assignment and can be used to tractably analyze TTC. In a large-scale continuum model we show how to compute these cutoffs directly from the distribution of preferences and priorities, providing a framework for evaluating policy choices. As an application of the model we solve for optimal investment in school quality under choice and find that an egalitarian distribution can be more efficient as it allows students to choose schools based on idiosyncracies in their preferences. In the second part of this work, I consider the role of a marketplace as an information provider and explore how mechanisms affect information acquisition by agents in matching markets. I provide a tractable “Pandora's box” model where students hold a prior over their value for each school and can pay an inspection cost to learn their realized value. The model captures how students’ decisions to acquire information depend on priors and market information, and can rationalize a student’s choice to remain partially uninformed. In such a model students need market information in order to optimally acquire their personal preferences, and students benefit from waiting for the market to resolve before acquiring information. We extend the definition of stability to this partial information setting and define regret-free stable outcomes, where the matching is stable and each student has acquired the same information as if they had waited for the market to resolve. We show that regret-free stable outcomes have a cutoff characterization, and the set of regret-free stable outcomes is a non-empty lattice. However, there is no mechanism that always produces a regret-free stable matching, as there can be information deadlocks where every student finds it suboptimal to be the first to acquire information. In settings with sufficient information about the distribution of preferences, we provide mechanisms that exploit the cutoff structure to break the deadlock and approximately implement a regret-free stable matching.

The PSUBOT (pronounced pea-es-you-bought) is an autonomous wheelchair robot for persons with certain disabilities. Its use of voice recognition and autonomous navigation enable it to carry out high level commands with little or no user assistance. We first describe the goals, constraints, and capabilities of the overall system including path planning and obstacle avoidance. We then focus on localization-the ability of the robot to locate itself in space. Odometry, a compass, and an algorithm which matches points to lines are each employed to accomplish this task. The matching algorithm (which matches "points" to "lines") is the main contribution to this work. The .. points" are acquired from a rotating sonar device, and the "lines" are extracted from a user-entered line-segment model of the building. The algorithm assumes that only small corrections are necessary to correct for odometry errors which inherently accumulate, and makes a correction by shifting and rotating the sonar image so that the data points are as close as possible to the lines. A modification of the basic algorithm to accommodate parallel lines was developed as well as an improvement to the basic noise removal algorithm. We found that the matching algorithm was able to determine the location of the robot to within one foot even when required to correct for as many as five feet of simulated odometry error. Finally, the algorithm's complexity was found to be well within the processing power of currently available hardware.

published_or_final_version / Economics and Finance / Doctoral / Doctor of Philosophy

In this thesis, we study a variant of the maximum cardinality matching problem known as the maximum charge problem. Given a graph with arbitrary positive integer capacities assigned on every vertex and every edge, the goal is to maximize the assignment of positive feasible charges on the edges obeying the capacity constraints, so as to maximize the total sum of the charges. We use the primal-dual approach. We propose a combinatorial algorithm for solving the dual of the restricted primal and show that the primal-dual algorithm runs in a polynomial time. / ix, 96 leaves : ill. ; 29 cm

This thesis consists of three self-contained chapters. Chapter 1 develops a two-sector, bivariate matching model, in which each sector uses a different dimension of skill in the production process. I show there exists a unique assignment of agents to sectors and derive comparative statics. The main result is that if jobs are scarce, both an increase in sector one skills' spread and a technological improvement increase the supply of talent in sector one, but decrease it in sector two. In sector two, this raises wages and wage inequality. In sector one, the effects are ambiguous in general, but wages increase for the most and decrease for the least talented agents. Chapter 2 studies the impact of social status on occupational sorting in a two-sector matching framework. Talent is two-dimensional and thus status is not a zero-sum game; it depends both on occupational prestige and within-sector rank (local status). I show that the weights with which these two components enter - the structure of status - crucially influence the way in which agents self-select into sectors and argue that it is likely that these weights differ across occupations. The more important are the individual components of status in a sector, or the less important the collective component, the better the agents who join that industry, which has important implications for total payoffs, wage levels and inequality, and profits. I also show that the stable assignment is typically inefficient, which is driven by the distortion of relative status rewards, not status concerns per se. Chapter 3 investigates whether directors of companies should have limited liability. I develop a three-player model in which: (a) debtholders and equityholders are defined by their control rights and (b) the project is run by the directors. The main result is that increased liability for directors forces them to internalise more of the downside risk of the project and hence reduces their risk-taking. This is optimal if over-investment was a problem initially. I show that the extent to which over-investment is a problem depends on how well debtholders are protected compared to equityholders. If debtholders are strong, increased liability can cause under-investment.

Thesis advisor: M. Utku Ünver / Thesis advisor: Tayfun Sönmez / This thesis is a collection of three essays in market design concerning designs of matching markets with aggregate constraints, affirmative action schemes, and investigating boundaries of simultaneous efficiency-stability relaxation for one-to-one matching mechanisms.In Chapter 1, I establish and propose a possible solution for a college housing crisis, a severe ongoing problem taking place in many countries. Every year many colleges provide housing for admitted students. However, there is no college admissions process that considers applicants’ housing needs, which often results in college housing shortages. In this chapter, I formally introduce housing quotas to the college admissions problem and solve it for centralized admissions with common dormitories. The proposed setting is inspired by college admissions where applicants apply directly to college departments, and colleges are endowed with common residence halls. Such setting has many real-life applications: hospital/residents matching in Japan (Kamada and Kojima, 2011, 2012, 2015), college admissions with scholarships in Hungary (Biró, 2012), etc. A simple example shows that there may not be a stable allocation for the proposed setting. Therefore, I construct two mechanisms that always produce some weakened versions of a stable matching: a Take-House-from-Applicant-stable and incentive compatible cumulative offer mechanism that respects improvements, and a Not-Compromised-Request-from-One-Agent-stable (stronger version of stability) cutoff minimising mechanism. Finally, I propose an integer programming solution for detecting a blocking-undominated Not-Compromised-Request-from-One-Agent-stable matching. Building on these results, I argue that presented procedures could serve as a helpful tool for solving the college housing crisis. In Chapter 2, I propose a number of solutions to resource allocation problems in an affirmative action agenda. Quotas are introduced as a way to promote members of minority groups. In addition, reserves may overlap: any candidate can belong to many minority groups, or, in other words, have more than one trait. Moreover, once selected, each candidate fills one reserve position for each of her traits, rather than just one position for one of her traits. This makes the entire decision process more transparent for applicants and allows them to potentially utilize all their traits. I extend the approach of Sönmez and Yenmez (2019) who proposed a paired-admissions choice correspondence that works under no more than two traits. In turn, I allow for any number of traits focusing on extracting the best possible agents, such that the chosen set is non-wasteful, the most diverse, and eliminates collective justified envy. Two new, lower- and upper-dominant choice rules and a class of sum-minimizing choice correspondences are introduced and characterized. In Chapter 3, I implement optimization techniques for detecting the efficient trade off between ex-post Pareto efficiency (for one side of a two-sided matching market) and ex-ante stability for small one-to-one matching markets. Neat example (Roth, 1982) proves that there is no matching mechanism that achieves both efficiency (for one side of the one-to-one matching market) and stability. As representative mechanisms I choose deferred-acceptance for stability, and top trading cycles for Pareto efficiency (both of them are strategy-proof for one side of the market). I compare performances of a randomized matching mechanism that simultaneously relaxes efficiency and stability, and a convex combination of two representative mechanisms. Results show that the constructed mechanism significantly improves efficiency and stability in comparison to mentioned convex combination of the benchmark mechanisms. / Thesis (PhD) — Boston College, 2023. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.

This study applied the generalized matching equation (GME) to pitch selection in MLB during the 2016 regular season. The GME was used to evaluate the pitch selection of 21 groups of pitchers as well as 144 individual pitchers. The GME described pitch selection well for four of the 21 pitching groups and 32 of the 144 individual pitchers. Of the remaining groups and individual pitchers, behavior may be explained by rule following behavior or be impacted by distant reinforcers such as salary. All 21 groups demonstrated a bias for fastballs as well as 119 of the 144 individual pitchers. The results extend the use of the GME to natural contexts and suggest an alternative view to evaluating pitchers. / Applied Behavioral Analysis

It is the aim of this paper to review some of the work done on stable matching, and on stable marriage problems in particular. Variants of the stable marriage problem will be considered, and the similarities and differences from a mathematical point of view will be highlighted. The correlation between preference and stability is a main theme, and the way in which diluted or incomplete preferences affect stability is explored. Since these problems have a wide range of practical applications, it is of interest to develop useful algorithms for the derivation of solutions. Time-complexity is a key factor in designing computable algorithms, making work load a strong consideration for practical purposes. Average and worst-case complexity are discussed. The number of different solutions that are possible for a given problem instance is surprising, and counter-intuitive. This leads naturally to a study of the solution sets and the lattice structure of solutions that emerges for any stable marriage problem. Many theorems derive from the lattice structure of stable solutions and it is shown that this can lead to the design of more efficient algorithms. The research on this topic is well established, and many theorems have been proved and published, although some published proofs have omitted the detail. In this paper, the author selects some key theorems, providing detailed proofs or alternate proofs, showing the mathematical richness of this field of study. Various applications are discussed, particularly with relevance to the social sciences, although mention is made of applications in computer science, game theory, and economics. The current research that is evident in this subject area, by reference to technical papers in periodicals and on the internet, suggests that it will remain a key topic for some time to come. / MATHEMATICAL SCIENCES / MSC (MATHEMATICS)

by Po-Ming Wong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 94-100). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.2 --- Image Data --- p.2 / Chapter 1.2.1 --- Feature Detection --- p.2 / Chapter 1.3 --- Neural Networks --- p.4 / Chapter 1.4 --- Invariant Object Recognition --- p.5 / Chapter 1.5 --- Thesis Outline --- p.7 / Chapter 2 --- Feature Extraction --- p.8 / Chapter 2.1 --- Review of the Principle Component Analysis (PCA) Method --- p.9 / Chapter 2.1.1 --- Theory --- p.10 / Chapter 2.2 --- Covariance Operator --- p.13 / Chapter 2.3 --- Corner Extraction Method --- p.16 / Chapter 2.3.1 --- Corner Detection on the Surface of an Object --- p.16 / Chapter 2.3.2 --- Corner Detection at Boundary Region --- p.17 / Chapter 2.3.3 --- Steps in Corner Detection Process --- p.21 / Chapter 2.4 --- Experiment Results and Discussion --- p.23 / Chapter 2.4.1 --- Features Localization --- p.27 / Chapter 2.4.2 --- Preparing Feature Points for Matching Process --- p.32 / Chapter 2.5 --- Summary --- p.32 / Chapter 3 --- Invariant Graph Matching Using High-Order Hopfield Network --- p.36 / Chapter 3.1 --- Review of the Hopfield Network --- p.37 / Chapter 3.1.1 --- 3D Image Matching Algorithm --- p.40 / Chapter 3.1.2 --- Iteration Algorithm --- p.44 / Chapter 3.2 --- Third-order Hopfield Network --- p.45 / Chapter 3.3 --- Experimental Results --- p.49 / Chapter 3.4 --- Summary --- p.58 / Chapter 4 --- Hopfield Network for 2D and 3D Mirror-Symmetric Image Match- ing --- p.59 / Chapter 4.1 --- Introduction --- p.59 / Chapter 4.2 --- Geometric Symmetry --- p.60 / Chapter 4.3 --- Motivation --- p.62 / Chapter 4.4 --- Third-order Hopfield Network for Solving 2D Symmetry Problems --- p.66 / Chapter 4.5 --- Forth-order Hopfield Network for Solving 3D Symmetry Problem --- p.71 / Chapter 4.6 --- Experiment Results --- p.78 / Chapter 4.7 --- Summary --- p.88 / Chapter 5 --- Conclusion --- p.90 / Chapter 5.1 --- Results and Contributions --- p.90 / Chapter 5.2 --- Future Work --- p.92 / Bibliography --- p.94