AN ABSTRACT OF THE THESIS OF ISMAIL GUNEYDAS, for the Master of Science degree in Computer Science, presented on 5th November 2008, at Southern Illinois University Carbondale. TITLE: ACTOR POSITIONING IN WIRELESS SENSOR AND ACTOR NETWORKS USING MATCHING THEORY. MAJOR PROFESSOR: Dr. KEMAL AKKAYA In most of the Wireless sensor and actor network (WSAN) applications, the locations for the actors are determined autonomously by the collaboration of actors and/or sensors in order to eliminate human intervention as much as possible. Particularly, sensors can collaborate in a distributed manner and elect cluster-heads (CHs) among them which will be taking into account the distribution of the sensors within the region. In such cases, the actors can then move to such sensor locations (i.e., replace them as cluster-heads) as they have the ability to move by talking to nearby sensors/actors. Such movement, however, should be done wisely in order to minimize the total distance that will be traveled by the actors so that their lifetimes can be extended. Nevertheless, this may not be possible since not all the actor and CH locations will be known to each actor. In addition, the actors may not be reachable to each other and thus conflicts in assignments can easily occur. In this thesis, we propose an actor-CH location matching algorithm which will detect the CH locations and assign the actors to such locations in a distributed manner with the minimized travel distance. We adapt the Gale-Shapley (G-S) stable matching algorithm from Matching Theory in order to prevent conflicts and minimize the travel distance. In this matching algorithm, actors are regarded as men and CHs are regarded as women. First, we detect the CH locations through running a quorum-based search within the sensor network. Later, G-S is run on actor and CH locations. Once the locations are determined, each actor moves to that location. We evaluated the performance of our approach through simulation and have shown that our approach can produce results very close to the brute force approach.

Despite promotion by well-known economists and supporting economic theory, econometric analyses of voucher systems often find that they have been unsuccessful in improving traditional measures of educational success. This paper examines a possible explanation of this phenomenon by comparing the drivers of educational achievement and of school popularity by examining private school choice. The findings of this paper indicate that there is a disconnect between school success and school popularity, which adversely effects both the demand and supply-side benefits of voucher systems. Additionally, this paper reviews matching mechanisms that seek to efficiently match students with schools based on both student and school preferences.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / No Brasil, a busca pela reduÃÃo das ineficiÃncias observadas na alocaÃÃo de vagas em instituiÃÃes de ensino superior via o tradicional vestibular levou à formulaÃÃo e implantaÃÃo de um mecanismo alternativo de seleÃÃo para admissÃo superior: o Sistema de SeleÃÃo Unificada (SISU), criado em 2010. O mecanismo, tecnicamente falando, à um algoritmo de matching com as seguintes caracterÃsticas: i) cada estudante que recebe oferta de matrÃcula decide por aceitar ou rejeitar a oferta recebida; ii) rejeiÃÃes de ofertas provocam a realizaÃÃo de novas propostas; e iii) propostas sÃo aceitas temporariamente, podendo cada oferta aceita ser âtrocadaâ por uma oferta considerada âmelhorâ. Ou seja, o SISU à um mecanismo semelhante ao Algoritmo Deferred Acceptance (Algoritmo Gale-Shapley) com os cursos propondo. Apesar da importÃncia do SISU, a literatura econÃmica sobre o tema à basicamente inexistente. Nesse sentido, a presente dissertaÃÃo buscou, à luz da teoria dos jogos, entender e caracterizar os incentivos propiciados pelo SISU atravÃs de dois mecanismos teÃricos desenvolvidos, o SISUα e o SISUβ. Ambos sÃo modelados como mecanismos de matching dinÃmicos. Caracterizamos estratÃgias nÃo dominadas para o SISUβ e o SISUα. Utilizando o SISUα como a melhor aproximaÃÃo disponÃvel para o SISU, concluÃmos que a introduÃÃo do SISU apresentou um importante avanÃo em relaÃÃo ao vestibular em termos de ganhos de eficiÃncia do matching entre alunos e cursos. / In Brazil, the quest for reducing observed inefficiencies in the allocation of seats in higher education institutions through traditional examination (Vestibular) led to the formulation and implementation of an alternative mechanism of selection: the Unified Selection System (SISU), created in 2010. Technically speaking, the mechanism is a matching algorithm with the following characteristics: i) each student who receives an offer decides to accept or reject the received offer; ii) rejections of offers prompt new proposals; iii) proposals are accepted temporarily, and each offer can be âreplacedâ by an offer considered âbetterâ. That is, the SISU is a mechanism similar to the Deferred Acceptance Algorithm (Gale-Shapley Algorithm). Despite the importance of SISU, the economic literature on the subject is basically nonexistent. In this sense, this dissertation sought, in light of game theory, to understand and characterize the incentives provided by SISU through two developed theoretical mechanisms, the SISUα and SISUβ. Both are modeled as dynamic matching mechanisms. We characterize undominated strategies for SISUβ and SISUα. Using SISUα as the best approximation available to SISU, we conclude that the introduction of SISU showed a significant improvement on Vestibular in terms of gains of efficiency from matching between students and courses.

The aim of the paper is to discuss the way that the online job banks send resumes to businesses for job seekers, and most businesses and job seekers have chosen online job banks as channel management for job wanted due to the rapid development of information technology for recent years. What businesses find employees and job seekers find jobs through the online job banks can be classified into two kinds, one is active candidates for the job, and another is matching pair by the online job banks. The online job banks help job seekers to send resumes to businesses by means of both ways, and how the online job banks send resumes to businesses for job seekers will affect the outcome. Therefore, this paper focuses on original way of sending resumes used by the online job banks, and also uses Gale-Shapley algorithm to devise different way of sending resumes which the online job banks possibly use in the future and consequently by comparing two ways of sending resumes, it can analyze what ways of sending resumes can be adopted by the online job banks under different situations.

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.

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.

Apresentamos a teoria sobre mercados de dois lados, centralizados e descentralizados, para analisar o mercado de admissão de estudantes aos Centros de Pós-graduação em Economia no Brasil ao longo dos últimos 15 anos. Iniciamos descrevendo a história da organização deste mercado até a época atual. As falhas do sistema descentralizado e as hipóteses sobre o insucesso do procedimento centralizado de 1997 são discutidas. Observações empíricas são utilizadas para propor um modelo teórico que represente aproximadamente o atual mecanismo descentralizado e explique a aparente duradoura aplicação desse mecanismo. Por fim, tecemos considerações a respeito das possibilidades de aprimoramento deste mercado com modificações do mecanismo existente. / We present the theory of two-sided matching markets, with centralized and decentralized mechanisms, in order to analyze a Brazilian market in which graduated students seek positions in postgraduate programs in economics. We first describe the institutional history of this market. The failures of the decentralized procedure and the hypothesis about the failure of the 1997 centralized mechanism are discussed. Empirical observations are used to propose a theoretical model that represents the actual decentralized matching procedure of the market. Based in this model we explain the apparent long-lasting use of this decentralized mechanism. Finally, we make considerations about the possibilities of developments in this market by modifying the mechanism used today.

Apresentamos a teoria sobre mercados de dois lados, centralizados e descentralizados, para analisar o mercado de admissão de estudantes aos Centros de Pós-graduação em Economia no Brasil ao longo dos últimos 15 anos. Iniciamos descrevendo a história da organização deste mercado até a época atual. As falhas do sistema descentralizado e as hipóteses sobre o insucesso do procedimento centralizado de 1997 são discutidas. Observações empíricas são utilizadas para propor um modelo teórico que represente aproximadamente o atual mecanismo descentralizado e explique a aparente duradoura aplicação desse mecanismo. Por fim, tecemos considerações a respeito das possibilidades de aprimoramento deste mercado com modificações do mecanismo existente. / We present the theory of two-sided matching markets, with centralized and decentralized mechanisms, in order to analyze a Brazilian market in which graduated students seek positions in postgraduate programs in economics. We first describe the institutional history of this market. The failures of the decentralized procedure and the hypothesis about the failure of the 1997 centralized mechanism are discussed. Empirical observations are used to propose a theoretical model that represents the actual decentralized matching procedure of the market. Based in this model we explain the apparent long-lasting use of this decentralized mechanism. Finally, we make considerations about the possibilities of developments in this market by modifying the mechanism used today.