This dissertation analyzes problems related to matching in general networks and decision under uncertainty. Chapter 1 introduces the framework of convex matching games. Chapter 2 discusses three distinct applications of the framework. Chapter 3 develops a new test of choice models with expected utility. In Chapter 1, I use Scarf's lemma to show that given a convexity structure that I introduce, the core of a matching game is always nonempty, and the framework I introduce can accommodate general contracting networks, multilateral contracts, and complementary preferences. In Chapter 2, I provide three applications to show how the convexity structure is satisfied in different contexts by different assumptions. In the first application, I show that in large economies, the convexity structure is satisfied if the set of participants in each contract is small compared to the overall economy. The second application considers finite economies, and I show that the convexity structure is satisfied if all agents have convex, but not necessarily substitutable, preferences. The third application considers a large-firm, many-to-one matching market with peer preferences, and I show that the convexity structure is satisfied under convexity of preferences and a competition aversion restriction on workers' preferences over colleagues. In Chapter 3, I show that some form of cyclic choice pattern across distinct information scenarios should be regarded as inconsistent with a utility function that is linear in beliefs.

Li Wenjing. / "April 2002." / Thesis (Ph.D.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (p. 155-167). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Mode of access: World Wide Web. / Abstracts in English and Chinese.

Liu, Jian. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (p. 86-91). / Abstracts in English and Chinese. / Chapter 1 --- Introduction of Matching Mechanisms --- p.1 / Chapter 1.1 --- Background for College Admissions Problem --- p.1 / Chapter 1.2 --- Background for Internet Advertising Market --- p.3 / Chapter 2 --- Application I: College Admissions Problem Revisited --- p.6 / Chapter 2.1 --- Three Basic Mechanisms --- p.6 / Chapter 2.1.1 --- Boston Mechanism --- p.7 / Chapter 2.1.2 --- Gale-Shapley Student Optimal Mechanism --- p.9 / Chapter 2.1.3 --- Top Trading Cycles Mechanism --- p.11 / Chapter 2.2 --- College Admissions Mechanisms Around the World --- p.12 / Chapter 2.2.1 --- Serial Dictatorship in Turkey --- p.13 / Chapter 2.2.2 --- JUPAS in Hong'Kong SAR --- p.14 / Chapter 2.2.3 --- College Admissions in Mainland China --- p.16 / Chapter 2.3 --- Generalized Model for College Admissions: JUPAS Revisited --- p.19 / Chapter 2.4 --- Extension to Marriage Problem --- p.23 / Chapter 2.5 --- Strategy Analysis in Extended Marriage Problem --- p.27 / Chapter 2.6 --- Strategy Analysis in JUPAS --- p.30 / Chapter 2.7 --- Efficiency Investigation via Simulation --- p.33 / Chapter 2.7.1 --- Efficiency Definition --- p.33 / Chapter 2.7.2 --- Simulation Design --- p.36 / Chapter 2.7.3 --- Simulation Results --- p.38 / Chapter 3 --- Application II: Search Engines Market Model --- p.42 / Chapter 3.1 --- The Monopoly Market Model --- p.42 / Chapter 3.1.1 --- The Ex Ante Case --- p.43 / Chapter 3.1.2 --- The Ex Post Case --- p.45 / Chapter 3.1.3 --- Formulated As An Optimization Problem --- p.51 / Chapter 3.2 --- The Duopoly Market Model --- p.54 / Chapter 3.2.1 --- Competition for End Users in Stage I --- p.54 / Chapter 3.2.2 --- Competition for Advertisers in Stage II and III --- p.57 / Chapter 3.2.3 --- Comparison of Competition and Monopoly --- p.65 / Chapter 3.3 --- Numerical Results and Observations --- p.70 / Chapter 3.3.1 --- Baseline Setting --- p.71 / Chapter 3.3.2 --- Effect of Supplies --- p.74 / Chapter 3.3.3 --- Effect of Discount Factors --- p.75 / Chapter 4 --- Related Work --- p.78 / Chapter 5 --- Summary and Future Directions --- p.83 / Bibliography --- p.86

No description available.

Thesis (Ph. D.)--Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 123-124).

Thesis (Ph. D.)--Ohio State University, 2007. / Includes vita and abstract. Includes bibliographical references (leaves 123-124). Also available online via OhioLINK's ETD Center http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1194991095

Thesis advisor: M. Utku Ünver / Thesis advisor: M. Bumin Yenmez / This dissertation consists of two essays in market design. In the first chapter, we study affirmative action policies in college admissions and hiring. A college or firm makes admissions or hiring decisions in which each candidate is characterized by priority ranking and type, which may depend on race, gender, or socioeconomic status. The admissions or hiring committee faces a trade-off between meritocracy and diversity: while a merit-first choice rule may admit candidates of the same type, a diversity-first choice rule may be unfair due to priority violations. To formalize this trade-off, we introduce a measure of meritocracy and a measure of diversity for choice rules. Then, we investigate how to resolve the tension between them. A choice rule that uses both reserves and quotas can be viewed as a compromise and is a generalization of the two extreme rules. The first result is comparative statics for this class of choice rules: we show that as parameters change and the choice rule becomes more meritorious, it also becomes less diverse. The second result is a characterization of the choice rule, which may help admissions or hiring committees to decide their policies. In the second chapter, we introduce a method to measure manipulability of a matching mechanism and use theory and simulation to study constrained mechanisms in school choice. First, we show that the implications from existing measures are strongly dependent on the full preference domain assumption. Our measure is more robust. The implications from existing measures can be carried over as well: while the recent school admissions reforms did not fully eliminate incentives to manipulate, they discouraged manipulation. Second, we use simulations for quantitative analysis. Our results support the recent school admissions reforms quantitatively, as well as qualitatively: they largely eliminated the incentives to manipulate. In addition, while the qualitative implications from theory are parallel to existing measures, the quantitative implications from simulations confirm a significant difference. / Thesis (PhD) — Boston College, 2021. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.

This thesis focuses on two central classes of problems in discrete optimization: matching and scheduling. Matching problems lie at the intersection of different areas of mathematics, computer science, and economics. In two-sided markets, Gale and Shapley's model has been widely used and generalized to assign, e.g., students to schools and interns to hospitals. The goal is to find a matching that respects a certain concept of fairness called stability. This model has been generalized in many ways. Relaxing the stability condition to popularity allows to overcome one of the main drawbacks of stable matchings: the fact that two individuals (a blocking pair) can prevent the matching from being much larger. The first part of this thesis is devoted to understanding the complexity of various problems around popular matchings. We first investigate maximum weighted popular matching problems. In particular, we show various NP-hardness results, while on the other hand prove that a popular matching of maximum weight (if any) can be found in polynomial time if the input graph has bounded treewidth. We also investigate algorithmic questions on the relationship between popular, stable, and Pareto optimal matchings. The last part of the thesis deals with a combinatorial scheduling problem arising in cyber-security. Moving target defense strategies allow to mitigate cyber attacks. We analyze a strategic game, PLADD, which is an abstract model for these strategies.

The first result of this thesis is a generation theorem for bricks. A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of a decomposition procedure of Kotzig, and Lovasz and Plummer. We prove that every brick except for the Petersen graph can be generated from K_4 or the prism by repeatedly applying certain operations in such a way that all the intermediate graphs are bricks. We use this theorem to prove an exact upper bound on the number of edges in a minimal brick with given number of vertices and to prove that every minimal brick has at least three vertices of degree three. The second half of the thesis is devoted to an investigation of graphs that admit Pfaffian orientations. We prove that a graph admits a Pfaffian orientation if and only if it can be drawn in the plane in such a way that every perfect matching crosses itself even number of times. Using similar techniques, we give a new proof of a theorem of Kleitman on the parity of crossings and develop a new approach to Turan's problem of estimating crossing number of complete bipartite graphs. We further extend our methods to study k-Pfaffian graphs and generalize a theorem by Gallucio, Loebl and Tessler. Finally, we relate Pfaffian orientations and signs of edge-colorings and prove a conjecture of Goddyn that every k-edge-colorable k-regular Pfaffian graph is k-list-edge-colorable. This generalizes a theorem of Ellingham and Goddyn for planar graphs.

Thesis advisor: Utku Unver / This dissertation consists of three essays in microeconomic theory: two focusing on insurance theory and one on matching theory. The first chapter is concerned with catastrophe insurance. Motivated by the aftermath of hurricane Katrina, it studies a strategic model of catastrophe insurance in which consumers know that they may not get reimbursed if too many other people file claims at the same time. The model predicts that the demand for catastrophe insurance can ``bend backwards'' to zero, resulting in multiple equilibria and especially in market failure, which is always an equilibrium. This shows that a catastrophe market can fail entirely due to demand-driven reasons, a result new to the literature. The model suggests that pricing is key for the credibility of catastrophe insurers: instead of increasing demand, price cuts may backfire and instead cause a ``race to the bottom.'' However, small amounts of extra liquidity can restore the system to stable equilibrium, highlighting the importance of a functioning reinsurance market for large risks. These results remain robust both for expected utility consumer preferences and for expected utility's most popular alternative, rank-dependent expected utility. The second chapter develops a model of quality differentiation in insurance markets, focusing on two of their specific features: the fact that costs are uncertain, and the fact that firms are averse to risk. Cornerstone models of price competition predict that firms specialize in products of different quality (differentiate their products) as a way of softening price competition. However, real-world insurance markets feature very little differentiation. This chapter offers an explanation to this phenomenon by showing that cost uncertainty fundamentally alters the nature of price competition among risk-averse firms by creating a drive against differentiation. This force becomes particularly pronounced when consumers are picky about quality, and is capable of reversing standard results, leading to minimum differentiation instead. The chapter concludes with a study of how the costs of quality affect differentiation by considering two benchmark cases: when quality is costless and when quality costs are convex (quadratic). The third chapter focuses on the theory of two-sided matching. Its main topic are inefficiencies that arise when agent preferences permit indifferences. It is well-known that two-sided matching under weak preferences can result in matchings that are stable, but not Pareto efficient, which creates bad incentives for inefficiently matched agents to stay together. In this chapter I show that in one-to-one matching with weak preferences, the fraction of inefficiently matched agents decreases with market size if agents are sufficiently diverse; in particular, the proportion of agents who can Pareto improve in a randomly chosen stable matching approaches zero when the number of agents goes to infinity. This result shows that the relative degree of the inefficiency vanishes in sufficiently large markets, but this does not provide a "cure-all'' solution in absolute terms, because inefficient individuals remain even when their fraction is vanishing. Agent diversity is represented by the diversity of each person's preferences, which are assumed randomly drawn, i.i.d. from the set of all possible weak preferences. To demonstrate its main result, the chapter relies on the combinatorial properties of random weak preferences. / Thesis (PhD) — Boston College, 2012. / Submitted to: Boston College. Graduate School of Arts and Sciences. / Discipline: Economics.