Given two sets of points $A$ and $B$ ($|A| = m$, $|B| = n$), we seek to find a minimum-weight many-to-many matching which seeks to match each point in $A$ to at least one point in $B$ and vice versa. Each matched pair (an edge) has a weight. The goal is to find the matching that minimizes the total weight. We study two kinds of problems depending on the edge weight used. The first edge weight is the Euclidean distance, $d_1$. The second is edge weight is the square of the Euclidean distance, $d_2$. There already exists an $O(k\log k)$ algorithm for $d_1$, where $k=m+n$. We provide an $O(mn)$ algorithm for the $d_2$ problem. We also solve the problem of finding the minimum-weight matching when the sets $A$ and $B$ are allowed to be translated on the real line. We present an $O(mnk \log k)$ algorithm for the $d_1$ problem and an $O(3^{mn})$ algorithm for the $d_2$. Furthermore, we also deal with the special case where $A$ and $B$ lie on a circle of a specific circumference. We present an $O(k^2 \log k)$ algorithm and $O(kmn)$ algorithm for solving the minimum-weight matching for the $d_1$, and $d_2$ weights respectively. Much like the problem on the real line, we extend this problem to allow the sets $A$ and $B$ to be rotated on the circle. We try to find the minimum-weight many-to-many matching when rotations are allowed. For $d_1$ we present an $O(k^2mn \log k)$ algorithm and a $O(3^{mn})$ algorithm for $d_2$. / Thesis (Master, Computing) -- Queen's University, 2010-11-08 20:48:18.968

This thesis consists of three independent papers. They are put in reverse chronological order according to when they were initiated. The first paper, which is a joint work with Özgür Evren, extends the standard rational choice framework with the option to postpone the act of selecting an alternative. In that paper, we propose an axiomatic model of choice over risky prospects that restricts the classical rationality axioms solely to those instances in which the decision maker does not defer. The cardinal approach we follow allows us to identify the preference relation of the decision maker over lotteries, even if the choice data is very scarce due to deferral. Moreover, we also derive the value of deferring choice from a given set of options, which turns out to be an affine utility function over choice sets. At each choice situation, the decision maker compares the utility of each available alternative with that of deferral so as to decide on opting for an alternative immediately. The second paper is a model of status quo bias with choice avoidance. It describes the choice behavior of an otherwise standard decision maker whose choices are affected by the presence of a status quo alternative. The status quo emerges as a temporary choice, which may be reversed upon arrival of new (introspective or objective) information, or upon finding new alternatives. The third paper considers the network formation problem from a matching perspective. In that paper, agents want to link with each other and each has preferences over the subsets of others. We consider various solution concepts regarding the stability of a matching between the agents, establish relations between these concepts under several preference restrictions, and provide sufficient conditions for these solutions to be nonempty. / Diss. Stockholm : Handelshögskolan i Stockholm, 2011