Popular edges and dominant matchings by Ágnes CSEH and Telikepalli Kavitha was published in Mathematical programming.
Given a bipartite graph G=(A∪B,E) with strict preference lists and given an edge e∗∈E , we ask if there exists a popular matching in G that contains e∗ . We call this the popular edge problem. A matching M is popular if there is no matching M′ such that the vertices that prefer M′ to M outnumber those that prefer M to M′ . It is known that every stable matching is popular; however G may have no stable matching with the edge e∗ . In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge e∗ , then there is either a stable matching that contains e∗ or a dominant matching that contains e∗ . This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an O(n3) algorithm to find a popular matching containing a given set of edges or report that none exists, where n=|A|+|B| .
Venue: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.11-12 István KÓNYA, Judit KREKÓ, Gábor OBLATH Labor shares in the EU sectoral effects and the role of relative prices The paper studies the labor ... Details »
Venue: MTA HTK 1097 Budapest Tóth Kálmán u. 4. fszt. K0.11-12 Róbert SOMOGYI: Prioritization vs Zero-rating: Discrimination on the Internet Abstract: This paper analyzes two business practices on the mobile internet market, paid prioritization and zero-rating. ... Details »
“Do CAP subsidies stabilise farm income in Hungary and Slovenia?” by Imre FERTŐ and Stefan BOJNEC in Agricultural Economics: Do CAP subsidies stabilise farm ... Details »
Learning to save in a voluntary pension system: toward an agent-based model by András SIMONOVITS and Balázs KIRÁLY was published in Journal of Economic ... Details »
Ambient temperature and sexual activity: Evidence from time use surveys by Tamás HAJDU and Gábor HAJDU was published in Demographic Research. Abstract Background: Previous ... Details »