AI Paper Atlas

Research map / Learning theory and algorithms / Submodular and game algorithms

Refining Tournament Solutions via Margin of Victory

Markus Brill, Ulrike Schmidt-Kraepelin, Warut Suksompong

AAAI 2020 · Learning theory and algorithms › Submodular and game algorithms · approach: Matching markets and welfare

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use minimum edge reversals to quantify how robust each alternative's winner status isTournament solutions · Pairwise-comparison tournamentsMoVImproved
Compute winner MoV via minimum length-bounded cutsUncovered Set, 3-kings, and Top Cycle · Weighted tournamentscomputational complexityImproved
Use length-bounded cut reductions for k ≥ 4k-kings winners · Unweighted tournamentscomputational complexityHurt
Use the weighted MoV frameworkUncovered Set non-winners · Weighted tournamentscomputational complexityHurt
Use the weighted MoV frameworkTop Cycle non-winners · Weighted tournamentscomputational complexityImproved
Use minimum dominating sets to construct reversalsUncovered Set non-winners · Unweighted tournamentsreversal count: -\lceil \log_2 n\rceilMixed
Use a Copeland-score comparison to find the cheapest destructive reversalsCopeland winners · Weighted tournamentscomputational complexityImproved
Use a network-flow construction to find constructive reversalsCopeland non-winners · Weighted tournamentscomputational complexityImproved
Allow arbitrary weighted reversal costsk-kings non-winners · Weighted tournamentscomputational complexityHurt
Use Banks-set membership to define winner robustnessBanks Set winners · Unweighted tournamentscomputational complexityHurt
Use Banks-set membership to define entry robustnessBanks Set non-winners · Unweighted tournamentscomputational complexityHurt
Use a winner-separation perspective for all considered tournament solutionsWinners · Unweighted tournamentsmaximum reversal count: \lfloor n/2 \rfloorImproved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy