2018/08/06 by Coste, Jeremy, Flesch, Breenn, Laison, Joshua D. +2 · 1 citation
#05C20 #05C69 #91B14 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1808.02076
A k-majority tournament T on a finite set of vertices V is defined by a set of 2k-1 linear orders on V, with an edge u → v in T if u>v in a majority of the linear orders. We think of the linear orders as voter preferences and the vertices of T as candidates, with an edge u → v in T if a majority of voters prefer candidate u to candidate v. In this paper we introduce weighted k-majority tournaments, with each edge u → v weighted by the number of voters preferring u. We define the maximum approval gap γw(T), a measure by which any dominating set of T beats the next most popular candidate. This parameter is analogous to previous work on the size of minimum dominating sets of (unweighted) k-majority tournaments. We prove that k/2 ≤ γw(T) ≤ 2k-1 for any weighted k-majority tournament T, and construct tournaments with γw(T)=q for any rational number k/2 ≤ q ≤ 2k-1. We also consider the minimum number of vertices m(q,k) in a k-majority tournament with γw(T)=q.