2020

2020/7 Ágnes Cseh – Klaus Heeger The stable marriage problem with ties and restricted edges 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 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 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 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 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 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 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)

A közoktatás indikátorrendszere 2019

A közoktatás indikátorrendszere 2019
Budapest, 2019. december 30.
Szerkesztette: Varga Júlia
A kötet szerzői
Hajdu Tamás
Hermann Zoltán
Horn Dániel
Varga Júlia
Kutatási asszisztens: Lénárd Tünde
Olvasószerkesztő: Székács István
E kiadvány megjelenését támogatta a Magyar Tudományos Akadémia és az Európai Bizottság Magyarországi Képviselete
Copyright © Közgazdaság- és Regionális Tudományi Kutatóközpont
Közgazdaság-tudományi Intézet, 2019

Technikai útmutató „A közoktatás indikátorrendszere 2019” című kiadványhoz
Budapest, 2019. december 30.
Szerkesztette: Varga Júlia
A kötet szerzői
Hajdu Tamás
Hermann Zoltán
Horn Dániel
Varga Júlia
Kutatási asszisztens: Lénárd Tünde
E kiadvány megjelenését támogatta a Magyar Tudományos Akadémia és az Európai Bizottság Magyarországi Képviselete
Copyright © MTA Közgazdaság- és Regionális Tudományi Kutatóközpont
Közgazdaság-tudományi Intézet, 2019

A közoktatás indikátorrendszere 2019” című kiadvány a KRTK Közgazdaság-tudományi Intézetében kidolgozott, a magyar közoktatási rendszer jellemzőit leíró indikátor-rendszer harmadik kiadása, mely 2018-ig tartalmazza az indikátorok frissített értékeit.

2015-ben dolgoztuk a ki az MTA KRTK Közgazdaság-tudományi Intézetében a közoktatási indikátorrendszert, azzal a céllal, hogy létrejöjjön Magyarországon egy rendszeres kiadvány, amely egyaránt alkalmas arra, hogy a szakpolitikai döntéshozók könnyen és pontosan tájékozódjanak a közoktatás aktuális állapotáról, illetve trendjeiről, és hogy az érdeklődő szakértő és nem szakértő közönség megismerje a magyar közoktatást jellemző legfontosabb mutatókat. Olyan indikátorokat alakítottunk ki, melyek amellett, hogy számszerűen leírják a jelenlegi helyzetet, lehetőséget adnak a mutatók ismételt megfigyelésére, mivel rendszeres adatgyűjtéseken alapulnak, melyek lehetővé teszik, hogy a kiadvány időközönként frissíthető, megjelentethető legyen. A mostani kiadás követi a 2015-ös első, és 2017-es második kiadás felépítését.

Valamennyi indikátor adatai online elérhetők, letölthetők a kiadványból, az adattáblákban az indikátorok értékeit olyan bontásokban is közöljük, melyek máshol nem hozzáférhetőek. Újdonságot jelent, hogy a 2019. évi kiadványban az  adattáblák már nem csak magyar, hanem angol nyelven is elérhetőek, valamint, hogy a kiadványt kiegészítettük egy angol nyelvű összefoglalóval és angol nyelvű tartalomjegyzékkel is. A kötetet – a korábbi kiadásokhoz hasonlóan – kiegészíti a „Technikai útmutató A közoktatás indikátorrendszere 2019 című kiadványhoz”, mely minden egyes indikátornak ismerteti számítási módját és az egyes indikátorokhoz felhasznált adatok pontos forrását.

2019

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.