Blog keresés
Generic filters
Exact matches only
Search in title
Search in content
Filter by Custom Post Type

Publikációk - MT/DP műhelytanulmányok

2020

2020/7 Ágnes Cseh – Klaus Heeger The stable marriage problem with ties and restricted edges MT/DP műhelytanulmányok Kiadvány letöltése

2020/7 The stable marriage problem with ties and restricted edges Ágnes Cseh – Klaus Heeger

In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching.

Kiadvány letöltése (pdf)
2020/6 Ágnes Cseh – Attila Juhos Pairwise preferences in the stable marriage problem MT/DP műhelytanulmányok Kiadvány letöltése

2020/6 Pairwise preferences in the stable marriage problem Ágnes Cseh – Attila Juhos

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.

Kiadvány letöltése (pdf)
2020/5 Ágnes Cseh – Tamás Fleiner – Petra Harján Pareto optimal coalitions of fixed size MT/DP műhelytanulmányok Kiadvány letöltése

2020/5 Pareto optimal coalitions of fixed size Ágnes Cseh – Tamás Fleiner – Petra Harján

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.

Kiadvány letöltése (pdf)
2020/4 Ágnes Cseh– Telikepalli Kavitha Popular Matchings in Complete Graphs MT/DP műhelytanulmányok Kiadvány letöltése

2020/4 Popular Matchings in Complete Graphs Ágnes Cseh– Telikepalli Kavitha

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.

Kiadvány letöltése (pdf)
2020/3 Ágnes Cseh – Yuri Faenza – Telikepalli Kavitha – Vladlena Powers Understanding popular matchings via stable matchings MT/DP műhelytanulmányok Kiadvány letöltése

2020/3 Understanding popular matchings via stable matchings Ágnes Cseh – Yuri Faenza – Telikepalli Kavitha – Vladlena Powers

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.

Kiadvány letöltése (pdf)
2020/2 Tünde Lénárd – Dániel Horn – Hubert János Kiss Does political pressure on ‘gender’ engender danger for scientific research? Evidence from a randomized controlled trial MT/DP műhelytanulmányok Kiadvány letöltése

2020/2 Does political pressure on ‘gender’ engender danger for scientific research? Evidence from a randomized controlled trial Tünde Lénárd – Dániel Horn – Hubert János Kiss

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.

Kiadvány letöltése (pdf)
2020/1 Péter Csóka – Ferenc Illés – Tamás Solymosi On the Shapley value of liability games MT/DP műhelytanulmányok Kiadvány letöltése

2020/1 On the Shapley value of liability games Péter Csóka – Ferenc Illés – Tamás Solymosi

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.

Kiadvány letöltése (pdf)

2019

2019/21 Havas Attila Measurement of innovation: the use and misuse of indicators and scoreboards MT/DP műhelytanulmányok Kiadvány letöltése

2019/21 Measurement of innovation: the use and misuse of indicators and scoreboards Havas Attila

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

/accepted / megjelenés alatt/

2019/20 Havas Attila A tudomány-, technológia- és innovációpolitika elméleti megalapozása a különböző közgazdasági iskolákban MT/DP műhelytanulmányok Kiadvány letöltése

2019/20 A tudomány-, technológia- és innovációpolitika elméleti megalapozása a különböző közgazdasági iskolákban Havas Attila

MT-DP – 2019/20
Havas Attila
A tudomány-, technológia- és innovációpolitika elméleti megalapozása a különböző közgazdasági iskolákban

/megjelenés alatt/

Felhasználási feltételek
Impresszum
Intézményünk országos és nemzetközi hálózati kapcsolatát az NIIF program biztosítja
Közgazdaság- és Regionális Tudományi Kutatóközpont Közgazdaság-tudományi Intézet
© Copyright 2019. Minden jog fenntartva.