We study the problem of formally explaining why a candidate was not selected by a given tournament rule, by identifying sub-tournaments in which the candidate loses independently of how the rest of the tournament is completed. We define destructive minimal supports as any minimal sub-tournament satisfying this property, which in formal explainable artificial intelligence corresponds to abductive explanations for the question"Why does the loser lose the tournament?". For six common tournament solutions (maximin, uncovered set and its weighted variant, top cycle, Copeland, and Borda) we provide characterizations of when a candidate is either a necessary loser or a possible winner, we determine the size of the smallest destructive minimal supports, complemented by polynomial-time algorithms for their computation except for the case of Borda and Copeland rules which we conjecture to also be polynomial.
In adaptive quantitative group testing with exactly two defective items, each test reports how many defectives lie in a chosen subset. We study configurations in which the possible defective pairs form the edges of a star forest. Aigner proved a necessary majorization condition on the ordered star sizes for identifying...
A tournament T is k-inducible if there are k linear orders on its vertex set such that, for every arc $i \to j$ of T, a majority of the orders rank i above j. For odd k, let N(k) be the least order at which some tournament is not k-inducible. Only N(3) = 8 is known exactly; for N(5) the best bounds were $12 \le N(5) \l...
We study the computational complexity of satisfying proportional representation -- in particular proportional, extended, and fully justified representation (PJR, EJR, and FJR) -- in participatory budgeting and committee elections with additive utilities. First, we give a complete picture of the complexity of the axioms...
Carmel Baharav, Jakob de Raaij, Agnes Totschnig· 2 citations· ⚡1
It is established that multi-winner voting with argumentative ballots (MVArg) is strictly more expressive than multi-winner voting with approval ballots (MV) and the notions of cohesion and justified representation are conservative generalisations of their counterparts in MV.
In temporal voting, a fixed set of voters makes a collective decision in each of several rounds, and proportionality requires that groups with shared interests be represented across these decisions. Full justified representation (FJR) is among the strongest proportionality axioms known to be satisfiable in this setting...
We create a set of 6 axioms relating to strategic voting and study them on single transferable vote (STV), Meek STV, Bloc, Chamberlin-Courant, Monroe, and k-Borda. For Chamberlin-Courant, Monroe, and k-Borda, we implement ``optimistic''and ``pessimistic''models for handing incomplete ballots, thus turning each of the t...
