Matchings with Interval Order Preferences: Efficiency vs Strategy-proofness
We investigate models of two-sided matching markets without transfers. Examples of such markets include marriage market, universities-applicants market and others. Gale and Shapley in 1962 first introduced this kind of problems in the literature. They considered one-to-one and one-to-many markets, where preferences of individuals on the one side over individuals on the other side were strict.
In this paper we analyze a modification of the classical Gale-Shapley admission problem, where preferences of universities are considered to be interval orders. Interval order allows a specific form of indifference in the preference relation. Imagine, each alternative is described with an interval [l, u], and one alternative dominates another if and only if intervals do not overlap and lower bound of the first interval is greater than upper bound of the second interval. Preferences with such property may occur in the cases, when applicants’ scoring system (interview, exam or sum of points) is not exactly accurate.
In the previous paper we have shown the existence of a stable matching and provided the criteria of applicant Pareto-optimality of a stable matching, based on Stable Improvement Cycles.
However, the Pareto-efficient stable mechanism is not (in general) strategy-proof for applicants. We provide a strategy-proof applicant-proposing deferred acceptance with tie-breaking, where tie-breaking procedure is organized in a special way. This special tie-breaking allows to lower chances of an applicant-inefficient stable matching (in comparison to that with random-tie breaking).
Proceedings include extended abstracts of reports presented at the III International Conference on Optimization Methods and Applications “Optimization and application” (OPTIMA-2012) held in Costa da Caparica, Portugal, September 23—30, 2012.
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite graphs, matchings, Petri nets, planar graphs, transport nets). Some algorithms often used in practice on graphs are given. It is considered classical combinatorial configurations and their generating functions, recurrent sequences. It is put in a basis of the book long-term experience of teaching by authors the discipline «Discrete mathematics» at the business informatics faculty, at the computer science faculty of National Research University Higher School of Economics, and at the automatics and computer technique faculty of National research university Moscow power engineering institute. The book is intended for the students of a bachelor degree, trained at the computer science faculties in the directions 09.03.01 Informatics and computational technique, 09.03.02 Informational systems and technologies, 09.03.03 Applied informatics, 09.03.04 Software Engineering, and also for IT experts and developers of software products.
Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m √n log n 2 /m log n ) -Time algorithm (hereinafter n := |V |, m := |E|). Now let us consider the fractional relaxation, i.e. allow T-path packings with arbitrary nonnegative real weights. It is known that there always exists a half-integral solution, that is, one only needs to assign weights 0, 1/2 , 1 to maximize the total weight of T-paths. It is also known that an optimum half-integral packing can be found in strongly-polynomial time but the actual time bounds are far from being satisfactory. In this paper we present a novel algorithm that solves the half-integral problem within O ( m √n log n 2 /m log n )time, thus matching the complexities of integral and half-integral versions.
The paper suggests a new --- to the best of the author's knowledge --- characterization of Pareto-optimal decisions for the case of two-dimensional utility space which is not supposed to be convex. The main idea is to use the angle distances between the bisector of the first quadrant and points of utility space. A necessary and sufficient condition for Pareto optimality in the form of an equation is derived. The first-order necessary condition for optimality in the form of a pair of equations is also obtained.
In Russia from 2009 College admission is based on results of Unified State Exam. Entrant applies to no more than five universities. Admission mechanism is defined by government for all state universities. In the paper the authors model how entrant chooses university for application and, based on the entrant's choice prediction, the shortages of the current admission mechanism are revealed.
Matching problem with preferences being simplest semiorders is analysed. It is proved that a stable matching always exists. Furthermore, for any stable matching there exists a linear extension of preferences, which does not sontradict stability of a matching. In the college admission problem common goal is to find student-optimal stable matching. We provide a simple criteria (Stable Improvement Cycle existence), that allows to check, whether some particular stable matching is student-side Pareto optimal.
The concept of economic equilibrium under uncertainty is applied to a model of insurance market where, in distinction to the classic Borch's model of a reinsurance market, risk exchanges are allowed between the insurer and each insured only, not among insureds themselves. Conditions characterizing an equilibrium are found. A variant of the conditions, based on the Pareto optimality notion and involving risk aversion functions of the agents, is derived. An existence theorem is proved. Computation of the market premiums and optimal indemnities is illustrated by an example with exponential utility functions.
Smoking is a problem, bringing signifi cant social and economic costs to Russiansociety. However, ratifi cation of the World health organization Framework conventionon tobacco control makes it possible to improve Russian legislation accordingto the international standards. So, I describe some measures that should be taken bythe Russian authorities in the nearest future, and I examine their effi ciency. By studyingthe international evidence I analyze the impact of the smoke-free areas, advertisementand sponsorship bans, tax increases, etc. on the prevalence of smoking, cigaretteconsumption and some other indicators. I also investigate the obstacles confrontingthe Russian authorities when they introduce new policy measures and the public attitudetowards these measures. I conclude that there is a number of easy-to-implementanti-smoking activities that need no fi nancial resources but only a political will.
One of the most important indicators of company's success is the increase of its value. The article investigates traditional methods of company's value assessment and the evidence that the application of these methods is incorrect in the new stage of economy. So it is necessary to create a new method of valuation based on the new main sources of company's success that is its intellectual capital.