No description available.

Matching problems arise in several real-world scenarios like assigning posts to applicants, houses to trainees and room-mates to one another. In this thesis we consider the bipartite matching problem where one side of the bipartition specifies preferences over the other side. That is, we are given a bipartite graph G = (A ∪ P,E) where A denotes the set of applicants, P denotes the set of posts, and the preferences of applicants are specified by ranks on the edges. Several notions of optimality like pareto-optimality, rank-maximality, popularity have been studied in the literature; we focus on the notion of popularity. A matching M is more popular than another matching M′ if the number of applicants that prefer M to M′ exceeds the number of applicants that prefer M′ to M. A matching M is said to be popular if there exists no matching that is more popular than M. Popular matchings have the desirable property that no applicant majority can force a migration to another matching. However, popular matchings do not provide a complete answer since there exist simple instances that do not admit any popular matching. Abraham et al. (SICOMP 2007) characterized instances that admit a popular matching and also gave efficient algorithms to find one when it exists. We present several generalizations of the popular matchings problem in this thesis. Majority of our work deals with instances that do not admit any popular matching. We propose three different solution concepts for such instances. A reasonable solution when an instance does not admit a popular matching is to output a matching that is least unpopular amongst the set of unpopular matchings. McCutchen (LATIN 2008) introduced and studied measures of unpopularity, namely the unpopularity factor and unpopularity margin. He proved that computing either a least unpopularity factor matching or a least unpopularity margin matching is NP-hard. We build upon this work and design an O(km√n) time algorithm which produces matchings with bounded unpopularity provided a certain subgraph of G admits an A-complete matching (a matching that matches all the applicants). Here n and m denote the number of vertices and the number of edges in G respectively, and k, which is bounded by |A|, is the number of iterations taken by our algorithm to terminate. We also show that if a certain subgraph of G admits an A-complete matching, then we have computed a matching with the least unpopularity factor. Another feasible solution for instances without any popular matching is to output a mixed matching that is popular. A mixed matching is simply a probability distribution over the set of matchings. A mixed matching Q is popular if no mixed matching is more popular than Q. We seek to answer the existence and computation of popular mixed matchings in a given instance G. We begin with a linear programming formulation to compute a mixed matching with the least unpopularity margin. We show that although the linear program has exponentially many constraints, we have a polynomial time separation oracle and hence a least unpopularity margin mixed matching can be computed in polynomial time. By casting the popular mixed matchings problem as a two player zero-sum game, it is possible to prove that every instance of the popular matchings problem admits a popular mixed matching. Therefore, the matching returned by our linear program is indeed a popular mixed matching. Finally, we propose augmentation of the input graph for instances that do not admit any popular matching. Assume that we are dealing with a set of items B (say, DVDs/books) instead of posts and it is possible to make duplicates of these items. Our goal is to make duplicates of appropriate items such that the augmented graph admits a popular matching. However, since allowing arbitrarily many copies for items is not feasible in practice, we impose restrictions in two forms – (i) associating costs with items, and (ii) bounding the number of copies. In the first case, we assume that we pay a price of cost(b) for every extra copy of b that we make; the first copy is assumed to be given to us at free. The total cost of the augmented instance is the sum of costs of all the extra copies that we make. Our goal is to compute a minimum cost augmented instance which admits a popular matching. In the second case, along with the input graph G = (A ∪ B,E), we are given a vector hc1, c2, . . . , c|B|i denoting upper bounds on the number of copies of every item. We seek to answer whether there exists a vector hx1, x2, . . . , x|B|i such that having xi copies of item bi where 1 ≤ xi ≤ ci enables the augmented graph to admit a popular matching. We prove that several problems under both these models turn out to be NP-hard – in fact they remain NP-hard even under severe restrictions on the preference lists. Our final results deal with instances that admit popular matchings. When the input instance admits a popular matching, there may be several popular matchings – in fact there may be several maximum cardinality popular matchings. Hence one may not be content with returning any maximum cardinality popular matching and instead ask for an optimal popular matching. Assuming that the notion of optimality is specified as a part of the problem, we present an O(m + n21 ) time algorithm for computing an optimal popular matching in G. Here m denotes the number of edges in G and n1 denotes the number of applicants. We also consider the problem of computing a minimum cost popular matching where with every post p, a price cost(p) and a capacity cap(p) are associated. A post with capacity cap(p) can be matched with up to cap(p) many applicants. We present an O(mn1) time algorithm to compute a minimum cost popular matching in such instances. We believe that the work provides interesting insights into the popular matchings problem and its variants.

<p>We develop algorithms to approximately count perfect matchings in bipartite graphs (or permanents of the corresponding adjacency matrices), perfect matchings in nonbipartite graphs (or hafnians), and general matchings in bipartite and nonbipartite graphs (or matching generating polynomials). </p><p>First, we study the problem of approximating the permanent and generating weighted perfect matchings in bipartite graphs from their correct distribution. We present a perfect sampling algorithm using self-reducible acceptance/rejection and an upper bound for the permanent. It has a polynomial expected running time for a class of dense problems, and it gives an improvement in running time by a factor of $n^3$ for matrices that are (.6)-dense. </p><p>Next, we apply the similar approach to study perfect matchings in nonbipartite graphs and also general matchings in general graphs. Our algorithms here have a subexponential expected running time for some classes of nontrivial graphs and are competitive with other Markov chain Monte Carlo methods.</p> / Dissertation

No description available.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24030号 / 情博第786号 / 新制||情||133(附属図書館) / 京都大学大学院情報学研究科知能情報学専攻 / (主査)准教授 宮崎 修一, 教授 岡部 寿男, 教授 阿久津 達也, 教授 湊 真一 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

<p>The first class of problem we study deals with geometric matchings. Given a set<br />of points in the plane, we study perfect matchings of those points by straight line<br />segments so that the segments do not cross. Bottleneck matching is such a matching that minimizes the length of the longest segment. We are interested in finding a bottleneck matching of points in convex position. In the monochromatic case, where any two points are allowed to be matched, we give an O(n ²)-time algorithm for finding a bottleneck matching, improving upon previously best known algorithm of O(n ³) time complexity. We also study a bichromatic version of this problem, where each point is colored either red or blue, and only points of different color can be matched. We develop a range of tools, for dealing with bichromatic non-crossing matchings of points in convex<br />position. Combining that set of tools with a geometric analysis enable us to solve the<br />problem of finding a bottleneck matching in O(n ²) time. We also design an O(n)-time<br />algorithm for the case where the given points lie on a circle. Previously best known results were O(n 3 ) for points in convex position, and O(n log n) for points on a circle.<br />The second class of problems we study deals with dilation of geometric networks.<br />Given a polygon representing a network, and a point p in the same plane, we aim to<br />extend the network by inserting a line segment, called a feed-link, which connects<br />p to the boundary of the polygon. Once a feed link is fixed, the geometric dilation<br />of some point q on the boundary is the ratio between the length of the shortest path<br />from p to q through the extended network, and their Euclidean distance. The utility of<br />a feed-link is inversely proportional to the maximal dilation over all boundary points.<br />We give a linear time algorithm for computing the feed-link with the minimum overall<br />dilation, thus improving upon the previously known algorithm of complexity that is<br />roughly O(n log n).</p> / <p>Prva klasa problema koju proučavamo tičee se geometrijskih mečinga. Za dat skup tačaaka u ravni, posmatramo savr&scaron;ene mečinge tih tačaka spajajućii ih&nbsp; dužima koje &nbsp; se ne smeju sećui. Bottleneck mečing je takav mečing koji minimizuje dužinu najduže duži. Na&scaron; cilj je da nađemo bottleneck mečiing tačaka u konveksnom položaju.Za monohromatski slučaj, u kom je dozvoljeno upariti svaki par tačaka, dajemo algoritam vremenske složenosti O(n ²) za nalaženje bottleneck mečinga. Ovo&nbsp; je bolje od prethodno najbolji poznatog algoritam, čiija je složenost O(n ³). Takođe proučavamo bihromatsku verziju ovog problema, u kojoj je svaka tačka&nbsp; obojena ili u crveno ili u plavo, i dozvoljeno je upariti samo tačke različite boje. Razvijamo niz alata za rad sa bihromatskim nepresecajućim mečinzima tačaka u konveksnom položaju. Kombinovanje ovih alata sa geometrijskom analizom omogućava nam da re&scaron;imo problem nalaženja bottleneck mečinga u O(n ² ) vremenu. Takođe, konstrui&scaron;emo algoritam vremenske složenosti O(n) za slučaj kada&nbsp; sve date tačkke leže na krugu. Prethodno najbolji poznati algoritmi su imali složenosti&nbsp; O(n ³ ) za tačkeke u konveksnom položaju i O(n log n) za tačke na krugu.<br />Druga klasa problema koju proučaavamo tiče se dilacije u geometrijskim mrežama. Za datu mrežu predstavljenu poligonom, i tačku p u istoj ravni, želimo pro&scaron;iriti mrežu&nbsp; dodavanjem duži zvane feed-link koja povezuje p sa obodom poligona. Kada je feed- link fiksiran, defini&scaron;emo geometrijsku dilaciju neke tačke q na obodu kao odnos izme&nbsp; đu&nbsp; dužine najkraćeg puta od p do q kroz pro&scaron;irenu mrežu i njihovog Euklidskog rastojanja. Korisnost feed-linka je obrnuto proporcionalna najvećoj dilaciji od svih ta čaka na obodu poligona. Konstrui&scaron;emo algoritam linearne vremenske složenosti koji nalazi feed-link sa najmanom sveukupnom dilacijom. Ovim postižemo bolji rezultat od prethodno najboljeg poznatog algoritma složenosti približno O(n log n).</p>

Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in many areas of mathematics, computer science, economics, and even medicine. This thesis studies stable matchings in graphs and hypergraphs. We begin by introducing the work of Gale and Shapley. Their main contribution was the proof that every bipartite graph has a stable matching. Our discussion revolves around the Gale-Shapley algorithm and highlights some of the interesting properties of stable matchings in bipartite graphs. We then progress to non-bipartite graphs. Contrary to bipartite graphs, we may not be able to find a stable matching in a non-bipartite graph. Some of the work of Irving will be surveyed, including his extension of the Gale-Shapley algorithm. Irving's algorithm shows that many of the properties of bipartite stable matchings remain when the general case is examined. In 1991, Tan showed how to extend the fundamental theorem of Gale and Shapley to non-bipartite graphs. He proved that every graph contains a set of edges that is very similar to a stable matching. In the process, he found a characterization of graphs with stable matchings based on a modification of Irving's algorithm. Aharoni and Fleiner gave a non-constructive proof of Tan's Theorem in 2003. Their proof relies on a powerful topological result, due to Scarf in 1965. In fact, their result extends beyond graphs and shows that every hypergraph has a fractional stable matching. We show how their work provides new and simpler proofs to several of Tan's results. We then consider fractional stable matchings from a linear programming perspective. Vande Vate obtained the first formulation for complete bipartite graphs in 1989. Further, he showed that the extreme points of the solution set exactly correspond to stable matchings. Roth, Rothblum, and Vande Vate extended Vande Vate's work to arbitrary bipartite graphs. Abeledo and Rothblum further noticed that this new formulation can model fractional stable matchings in non-bipartite graphs in 1994. Remarkably, these formulations yield analogous results to those obtained from Gale-Shapley's and Irving's algorithms. Without the presence of an algorithm, the properties are obtained through clever applications of duality and complementary slackness. We will also discuss stable matchings in hypergraphs. However, the desirable properties that are present in graphs no longer hold. To rectify this problem, we introduce a new ``majority" stable matchings for 3-uniform hypergraphs and show that, under this stronger definition, many properties extend beyond graphs. Once again, the linear programming tools of duality and complementary slackness are invaluable to our analysis. We will conclude with a discussion of two open problems relating to stable matchings in 3-uniform hypergraphs.

This thesis comprises of two separate game theoretic models that fall under the general umbrella of network formation games. The first is a coalitional model of interaction in social networks that is based on the idea of social distance, in which players seek interactions with similar others. Our model captures some of the phenomena observed on such networks, such as homophily driven interactions and the formation of small worlds for groups of players. Using social distance games, we analyze the interactions between players on the network, study the properties of efficient and stable networks, relate them to the underlying graphical structure of the game, and give an approximation algorithm for finding optimal social welfare. We then show that efficient networks are not necessarily stable, and stable networks do not necessarily maximise welfare. We use the stability gap to investigate the welfare of stable coalition structures, and propose two new solution concepts with improved welfare guarantees. The second model is a compact formulation of matchings with externalities. Our formulation achieves tractability of the representation at the expense of full expressivity. We formulate a template of solution concept that applies to games where externalities are involved, and instantiate it in the context of optimistic, neutral, and pessimistic reasoning. Then we investigate the complexity of the representation in the context of many-to-many and one-to-one matchings, and provide both computational hardness results and polynomial time algorithms where applicable.

In the first chapter, I analyze the US banking industry in order to explain two facts. First, larger banks have lower but less volatile returns on loans compared to smaller banks over the years. Second, larger borrowers have better financial records, i.e. verifiable "hard" information, and they are more likely to match with larger banks, as documented by Berger et al.(2005). I show that these two facts can be explained using a segmented loan markets model with loan contracts between banks and borrowers. Moreover, I show that the difference between the banks returns is not due to diversification advantage of larger banks. Instead, it is because of the fact that larger banks can operate in both large and small loan markets, whereas small banks can only operate in small loans market. Therefore large banks are able to match with larger and less risky borrowers more frequently, which are less likely to default. Moreover, I take the model to infinite horizon allowing bank size to be endogenous to answer multiple policy questions about the future of small business finance and consolidation. I use the data set from the Consolidated Reports of Condition and Income provided by FDIC for 1984-2010 to motivate our research question and to estimate the model. My second chapter revisits the welfare cost of anticipated inflation in an incomplete markets environment where agents can substitute time for money by increasing their shopping frequency. Shopping activity provides an insurance channel to individuals against changes in the return on nominal balances through inflation as documented by Aguiar and Hurst (2007) and McKenzie and Schargrodsky (2011). In my model economy, a higher level of inflation affects people through two channels. First, it distorts the portfolio decision between real and nominal balances, second it redistributes wealth from those who hold more money to those who hold less. People, on average, respond to a higher level of inflation by increasing their price search activity, as they relative return on nominal balances goes down. I find that a 5 percent increase in inflation causes the welfare level go down by 2 percent if people are allowed to substitute time for money, and by 10 percent if we take this channel away from the model. Finally, in the third chapter, I compare the indirect measure of inflation expectations derived by Ireland (1996b) to the direct measures obtained from expectations surveys in multiple countries. Our results show that the inflation bounds calculated for US and UK data are more volatile than survey results, and are too narrow to contain them due to low standard errors in consumption growth series stemming from high persistence. For Chilean and Turkish cases, however, computed bound for inflation expectations seems to fit the survey results better. Out of three different surveys on inflation expectations in Turkey compared with the bounds computed using Turkish data, expectations obtained by the Consumer Tendency Survey fall within these bounds throughout the whole sample period. The success in the Turkish and Chilean cases can be attributed to the fact that volatility in the consumption series, whereas the failure in US and UK cases are most probably stemming from the fact that the current theoretical model is missing a risk-premium component. / text

Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in many areas of mathematics, computer science, economics, and even medicine. This thesis studies stable matchings in graphs and hypergraphs. We begin by introducing the work of Gale and Shapley. Their main contribution was the proof that every bipartite graph has a stable matching. Our discussion revolves around the Gale-Shapley algorithm and highlights some of the interesting properties of stable matchings in bipartite graphs. We then progress to non-bipartite graphs. Contrary to bipartite graphs, we may not be able to find a stable matching in a non-bipartite graph. Some of the work of Irving will be surveyed, including his extension of the Gale-Shapley algorithm. Irving's algorithm shows that many of the properties of bipartite stable matchings remain when the general case is examined. In 1991, Tan showed how to extend the fundamental theorem of Gale and Shapley to non-bipartite graphs. He proved that every graph contains a set of edges that is very similar to a stable matching. In the process, he found a characterization of graphs with stable matchings based on a modification of Irving's algorithm. Aharoni and Fleiner gave a non-constructive proof of Tan's Theorem in 2003. Their proof relies on a powerful topological result, due to Scarf in 1965. In fact, their result extends beyond graphs and shows that every hypergraph has a fractional stable matching. We show how their work provides new and simpler proofs to several of Tan's results. We then consider fractional stable matchings from a linear programming perspective. Vande Vate obtained the first formulation for complete bipartite graphs in 1989. Further, he showed that the extreme points of the solution set exactly correspond to stable matchings. Roth, Rothblum, and Vande Vate extended Vande Vate's work to arbitrary bipartite graphs. Abeledo and Rothblum further noticed that this new formulation can model fractional stable matchings in non-bipartite graphs in 1994. Remarkably, these formulations yield analogous results to those obtained from Gale-Shapley's and Irving's algorithms. Without the presence of an algorithm, the properties are obtained through clever applications of duality and complementary slackness. We will also discuss stable matchings in hypergraphs. However, the desirable properties that are present in graphs no longer hold. To rectify this problem, we introduce a new ``majority" stable matchings for 3-uniform hypergraphs and show that, under this stronger definition, many properties extend beyond graphs. Once again, the linear programming tools of duality and complementary slackness are invaluable to our analysis. We will conclude with a discussion of two open problems relating to stable matchings in 3-uniform hypergraphs.