Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that “approximately popular” branchings always exist.
Nem található esemény a közeljövőben.
A KRTK Közgazdaság-tudományi Intézet teljesítményéről A KRTK KTI a RePEc/IDEAS rangsorában, amely a világ közgazdaság-tudományi tanszékeit és intézeteit rangsorolja publikációs teljesítményük alapján, a legjobb ... Read More »
Tisztelt Kollégák! Tudományos kutatóként, intézeti vezetőként egész életünkben a kutatói szabadság és felelősség elve vezetett bennünket. Meggyőződésünk, hogy a tudomány csak akkor érhet el ... Read More »
Srí Lanka: a 2022-es gazdasági válság leckéje – A. Krueger Lessons from Sri Lanka Anne O. Krueger Jul 25, 2022 – Project Syndicate ... Read More »
A permanens válság korában élünk – J. Meadway We’re living in an age of permanent crisis – let’s stop planning for a ‘return ... Read More »
A 2021 végén, illetve 2022 elején tapaszalt 6, illetve 7%-os cserearányromlás brutális reáljövedelem-kivonást jelentett a magyar gazdaságból. A külső egyensúly alakulásával foglalkozó elemzések többnyire ... Read More »