We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability—weak, strong and super-stability—under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs we determine the complexity of all cases not yet known, and thus give an exact boundary in terms of preference structure between tractable and intractable cases.

Our input is a complete graph G on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is “globally stable” or popular. A matching M is popular if M does not lose a head-to-head election against any matching M’: here each vertex casts a vote for the matching in {M,M’} in which it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show here. This seems to be the first graph theoretic problem that is efficiently solvable when n has one parity and NP-hard when n has the other parity.

Our input is a complete graph G on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is “globally stable” or popular. A matching M is popular if M does not lose a head-to-head election against any matching M’: here each vertex casts a vote for the matching in {M,M’} in which it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show here. This seems to be the first graph theoretic problem that is efficiently solvable when n has one parity and NP-hard when n has the other parity.

An instance of the marriage problem is given by a graph G together with, for each vertex of G, a strict preference order over its neighbors. A matching M of G is popular in the marriage instance if M does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is the set of dominant matchings. A popular matching M is dominant if M wins the head-to-head election against any larger matching. Thus every dominant matching is a max-size popular matching and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings.

The goal of this paper is to show that indeed there are differences in the tractability of stable and dominant matchings, and to investigate further their importance for popular matchings. First, we show that it is easy to check if all popular matchings are also stable, however it is co-NP-hard to check if all popular matchings are also dominant. Second, we show how some new and recent hardness results on popular matching problems can be deduced from the NP-hardness of certain problems on stable matchings, also studied in this paper, thus showing that stable matchings can be employed not only to show positive results on popular matching (as is known), but also most negative ones. Problems for which we show new hardness results include finding a min-size (resp. max-size) popular matching that is not stable (resp. dominant). A known result for which we give a new and simple proof is the NP-hardness of finding a popular matching when G is non-bipartite.

We detect a significant negative effect of mentioning ‘gender’ as a research topic on conducting academic research in Hungary. Using a randomized information treatment involving a comprehensive sample of Hungarian education providers we find that they are less willing to cooperate in a gender related future research compared to a research without this specification. Our results also indicate that this negative sentiment is clearly against gender and not against any topic covering social inequalities in general.

In a liability problem, the asset value of an insolvent firm must be distributed among the creditors and the firm itself, when the firm has some freedom in negotiating with the creditors. We model the negotiations using cooperative game theory and analyze the Shapley value to resolve such liability problems. We establish three main monotonicity properties of the Shapley value. First, creditors can only benefit from the increase in their claims or of the asset value. Second, the firm can only benefit from the increase of a claim but can end up with more or with less if the asset value increases, depending on the configuration of small and large liabilities. Third, creditors with larger claims benefit more from the increase of the asset value. Even though liability games are constant-sum games and we show that the Shapley value can be calculated directly from a liability problem, we prove that calculating the Shapley payoff to the firm is NP-hard.

MT-DP – 2019/24
Olga Takács – János Vincze
The gender pay gap in Hungary: new results with a new methodology

MT-DP – 2019/23
Olga Takács – János Vincze
Blinder-Oaxaca decomposition with recursive  tree-based methods: a technical note

MT-DP – 2019/21
Havas Attila
Measurement of innovation: the use and misuse of indicators and scoreboards

The choice of indicators to measure innovation processes and assess performance is of vital significance. This paper argues that those economic theories give a more accurate, more reliable account of innovation activities that follow a broad approach of innovation, that is, consider all knowledge-intensive activities leading to new products (goods or services), processes, business models, as well as new organisational and managerial solutions, and thus take into account various types, forms and sources of knowledge exploited for innovation by all sorts of actors in all economic sectors. In contrast, the narrow approach to innovation focuses on the so-called high-tech goods and sectors. The broad approach is needed to collect data and other types of information, on which sound theories can be built and reliable and comprehensive analyses of innovation activities can be offered to decision-makers to underpin public policies and company strategies.

MT-DP – 2019/16
Dániel Baksa – István Kónya
Convergence, productivity and debt:  the case of Hungary

MT-DP – 2019/15
Haris Aziz – Ágnes Cseh
Optimal Kidney Exchange with Immunosuppressants

MT-DP – 2019/14
Tamás Solymosi
Weighted nucleoli and dually essential coalitions (extended version)