搜索结果：Majority

Inspired by the majority colorings and C-colorings, we introduce and study the majority C-coloring of graphs. In such a vertex coloring, every vertex shares its color with at least half of its neighbors. The maximum number of colors that can be used in a majority C-coloring of a graph $G$ is called the majority C-chromatic number and denoted by $\mc(G)$. An upper bound on $\mc(G)$ is proved in terms of the order, minimum, and maximum degree. Its sharpness is demonstrated by several results over different graph classes. In particular, $\mc(P_n^k)= \mc(C_n^k)= \lfloor n/(k+1)\rfloor$ is true for the $k$-th power of a path and a cycle if $n \ge k+1$. Further, $\mc(G) = (n-d)/3$ holds if $G$ is a $(\mbox{claw}, K_4)$-free cubic graph and contains $d$ diamonds. %claw-free cubic graph on $n \ge 6$ vertices and contains $d$ diamonds. It is further shown that the majority C-chromatic number is not monotone under edge deletion. In fact, both the lower and upper bounds are sharp in the inequality chain $\mc(G)-2 \leq \mc(G-e) \leq \mc(G) +1$. The minimum and maximum number of edges in an $n$-vertex graph $G$ with $\mc(G)=k$ are determined for every $n$ and $k$. It is also pointed out that th

This paper studies strict majority reasoning in finite electorates using so-called $\textit{social decision frames}$: finite sets of voters equipped with distinguished families of coalitions interpreted as those voting blocs evaluated to form a strict majority. A coherence criterion for qualitative majority judgments is identified and shown to give an exact characterization for representability of strict majorities by finitely additive measures. In addition, a minimal natural logic for reasoning about strict majorities is shown to be sound and complete. These developments motivate examination of associated combinatorial questions concerning incoherence in finite families of sets; partial results and a conjecture are given. Finally, the results of this paper are applied to correct a classical representation theorem for weak qualitative probability structures due to Patrick Suppes and to establish a May-type characterization for ordinary strict majority rule for social decision frames.

We investigate possible list extensions of generalised majority edge colourings of graphs and provide several results concerning these. Given a graph $G=(V,E)$, a list assignment $L:E\to 2^C$ and some level of majority tolerance $α\in(0,1)$, an $α$-majority $L$-colouring of $G$ is a colouring $ω:E\to C$ from the given lists such that for every $v\in V$ and each $c\in C$, the number of edges coloured $c$ which are incident with $v$ does not exceed $α\cdot d(v)$. We present a simple argument implying that for every integer $k\geq 2$, each graph with minimum degree $δ\geq 2k^2-2k$ admits a $1/k$-majority $L$-colouring from any assignment of lists of size $k+1$. This almost matches the best result in a non-list setting and solves a conjecture posed for the basic majority edge colourings, i.e. for $k=2$, from lists. We further discuss restrictions which permit obtaining corresponding results in a more general setting, i.e. for diversified $α=α(c)$ majority tolerances for distinct colours $c\in C$. Consider a list assignment $L:E\to 2^C$ with $\sum_{c\in L(e)}α(c)\geq 1+\varepsilon$ for each edge $e$, and suppose that $α(c)\geq a$ for every $c$ or $|L(e)|\leq\ell$ for all edges $e$, wher

Majority illusion is an undesirable phenomenon in social networks in which agents incorrectly perceive a minority opinion as dominant. This can severely distort collective behavior and decision-making. We study the fundamental question of detecting whether a social network allows for a majority illusion. Formally, in the $q$-Majority Illusion problem, we ask whether there exists a binary labeling of agents in which at least a $q$-fraction of agents have the majority of neighbors with the minority label. We investigate how various structural properties of the underlying social network influence the tractability of this question, and provide a detailed map of its computational complexity.

The global majority problem, often referred to as the Density Classification Task, is a classical benchmark in the context of probing the computational capabilities of automata networks. It poses the simple yet challenging problem of determining, by totally local means, whether an arbitrary initial configuration of binary states can evolve to a final, homogeneous global configuration that reflects the initial global majority. Although it is known that in the specific case of cellular automata with periodic boundaries no rule is able to solve the problem, in other formulations solutions are known and, in others, the problem is still open. Aligned with the latter, here we explore the possibility of solving the problem with automata networks, operating only with the local majority rule, with a focus on identifying non-trivial cases where it can be solved and explaining why they do so.

This note characterizes every qualified majority voting rule in environments with just two alternatives through anonymity, responsiveness, and q-neutrality. Crucially, the latter imposes independence of the labels of the alternatives if and only if some alternative is strictly top-ranked by at least q voters. Thus, this note generalizes May's (1952, Theorem, p. 682) characterization of the simple majority voting rule to qualified majority voting rules. In doing so, it shows that qualified majority voting rules are distinguished by their degree of neutrality.

The paper proposes a novel problem in multi-class Multiple-Instance Learning (MIL) called Learning from the Majority Label (LML). In LML, the majority class of instances in a bag is assigned as the bag's label. LML aims to classify instances using bag-level majority classes. This problem is valuable in various applications. Existing MIL methods are unsuitable for LML due to aggregating confidences, which may lead to inconsistency between the bag-level label and the label obtained by counting the number of instances for each class. This may lead to incorrect instance-level classification. We propose a counting network trained to produce the bag-level majority labels estimated by counting the number of instances for each class. This led to the consistency of the majority class between the network outputs and one obtained by counting the number of instances. Experimental results show that our counting network outperforms conventional MIL methods on four datasets The code is publicly available at https://github.com/Shiku-Kaito/Counting-Network-for-Learning-from-Majority-Label.

Majority Illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an incorrect perception of the majority in a large network. In this paper, we present polynomial-time algorithms which can eliminate majority illusion in a network by altering as few connections as possible. Additionally, we prove that the more general problem of ensuring all neighbourhoods in the network are at least a $p$-fraction of the majority is NP-hard for most values of $p$.

Kamyczura introduced the notion of a majority additive $k$-coloring of a graph $G$ as a function $c: V(G) \to \{1,2,\ldots,k\}$ such that $$\left|\left\{u \in N_G(v):\sum_{w \in N_G(u)} c(w) = s \right\}\right|\leq \max\left\{1,\frac{d_G(v)}{2}\right\}$$ for every vertex $v$ of $G$ and every positive integer $s$. We show that every graph $G$ of maximum degree $Δ$ admitting a majority additive coloring has a majority additive $\mathcal{O}\left(Δ^2\right)$-coloring. Under additional restrictions we improve this to sublinear in $Δ$. We show that determining whether a majority additive $k$-coloring exists for a given graph is NP-complete for all $k\geq 2$.

Let $G=(V,E)$ be a simple graph of order $n$. A Majority Roman Dominating Function (MRDF) on a graph G is a function $f: V\rightarrow\{-1, +1, 2\}$ if the sum of its function values over at least half the closed neighborhoods is at least one , this is , for at least half of the vertices $v\in V$, $f(N[v])\geq 1$. Moreover, every vertex u with $f(u)=-1$ is adjacent to at least one vertex $w$ with $f(w)=2$. The Majority Roman Domination number of a graph $G$, denoted by $γ_{MR}(G)$ , is the minimum value of $\sum_{v\in{V(G)}}f(v)$ over all Majority Roman Dominating Function $f$ of $G$. In this paper we study properties of the Majority Roman Domination in graphs and obtain lower and upper bounds the Majority Roman Domination number of some graphs.

A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors. Kreutzer, Oum, Seymour, van der Zypen and Wood proved that every digraph has a majority 4-coloring and conjectured that every digraph admits a majority 3-coloring. We verify this conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3. We obtain analogous results for list coloring: We show that every digraph with list chromatic number at most 6 or list dichromatic number at most 3 is majority 3-choosable. We deduce that digraphs with maximum out-degree at most 4 or maximum degree at most 7 are majority 3-choosable. On the way to these results we investigate digraphs admitting a majority 2-coloring. We show that every digraph without odd directed cycles is majority 2-choosable. We answer an open question posed by Kreutzer et al. negatively, by showing that deciding whether a given digraph is majority 2-colorable is NP-complete. Finally we deal with a fractional relaxation of majority coloring proposed by Kreutzer et al. and show that every digraph has a fractional majority 3.9602-coloring. We show that every digra

In any vertex coloring of a graph some edges have differently colored ends (\emph{good} edges) and some are monochromatic (\emph{bad} edges). In a proper coloring all edges are good. In a \emph{majority coloring} it is enough that for every vertex $v$, the number of bad edges incident to $v$ does not exceed the number of good edges incident to $v$. A well known result of Lovász \cite{Lovasz} asserts that every finite graph has a majority $2$-coloring. A similar statement for countably infinite graphs is a challenging open problem, known as the \emph{Unfriendly Partition Conjecture}. We consider a natural list variant of majority coloring. A graph is \emph{majority $k$-choosable} if it has a majority coloring from any lists of size $k$ assigned arbitrarily to the vertices. We prove that every countable graph is majority $4$-choosable. We also consider a natural analog of majority coloring for directed graphs. We prove that every countable digraph is also majority $4$-choosable. We pose list and directed analogs of the Unfriendly Partition Conjecture, stating that every countable graph is majority $2$-choosable and every countable digraph is majority $3$-choosable.

We introduce the notion of a majority category --- the categorical counterpart of varieties of universal algebras admitting a majority term. This notion can be thought to capture properties of the category of lattices, in a way that parallels how Mal'tsev categories capture properties of the category of groups. Among algebraic majority categories are the categories of lattices, Boolean algebras, and Heyting algebras. Many geometric categories such as the category of topological spaces, metric spaces, ordered sets, any topos, ect., are comajority categories (i.e.~their duals are majority categories), and we show that, under mild assumptions, the only categories which are both majority and comajority, are the preorders. Mal'tsev majority categories provide an alternative generalization of arithmetical categories to protoarithmetical categories in the sense of Bourn. We show that every Mal'tsev majority category is protoarithmetical, provide a counter-example for the converse implication, and show that in the Barr-exact context, the converse implication also holds. We can then conclude that a category is arithmetical if and only if it is a Barr-exact Mal'tsev majority category, recove

Condorcet domains are subsets of permutations arising in voting theory: regarding their permutations as preference orders on a list of candidates, one avoids Condorcet's paradox when aggregating the preferences via a simple majority relation. We use poset theory to show that, for the subclass of Condorcet domains of tiling type, the majority rule has stronger properties. We then develop techniques to predict the majority rule explicitly for the uniform vote tally on Condorcet domains of tiling type, and apply this to several well-known examples.

We consider the problem of finding a compromise between the opinions of a group of individuals on a number of mutually independent, binary topics. In this paper, we quantify the loss in representativeness that results from requiring the outcome to have majority support, in other words, the "price of majority support". Each individual is assumed to support an outcome if they agree with the outcome on at least as many topics as they disagree on. Our results can also be seen as quantifying Anscombes paradox which states that topic-wise majority outcome may not be supported by a majority. To measure the representativeness of an outcome, we consider two metrics. First, we look for an outcome that agrees with a majority on as many topics as possible. We prove that the maximum number such that there is guaranteed to exist an outcome that agrees with a majority on this number of topics and has majority support, equals $\ceil{(t+1)/2}$ where $t$ is the total number of topics. Second, we count the number of times a voter opinion on a topic matches the outcome on that topic. The goal is to find the outcome with majority support with the largest number of matches. We consider the ratio between

Global Majority users are exposed to multitudes of harm when interacting with online platforms. This essay illuminates how exploitation in the advances of Artificial Intelligence is tied to historical exploitation and how the use of blanket terminology overshadows the layers of exploitation and harm ``Global Majority'' populations face. It first discusses the multitude of harm content moderators from the Global Majority face, arguing against the current trend of protection through exploitation, then it illustrates the nuances and differences within the Global Majority, and finally, it outlines actionable items to move away from such harm.

We introduce a new replicable boosting algorithm which significantly improves the sample complexity compared to previous algorithms. The algorithm works by doing two layers of majority voting, using an improved version of the replicable boosting algorithm introduced by Impagliazzo et al. [2022] in the bottom layer.

A majority coloring of an undirected graph is a vertex coloring in which for each vertex there are at least as many bi-chromatic edges containing that vertex as monochromatic ones. It is known that for every countable graph a majority 3-coloring always exists. The Unfriendly Partition Conjecture states that every countable graph admits a majority 2-coloring. Since the 3-coloring result extends to countable DAGs, a variant of the conjecture states that 2 colors are enough to majority color every countable DAG. We show that this is false by presenting a DAG for which 3 colors are necessary. Presented construction is strongly based on a StackExchange conversation regarding labellings of infinite graphs that is linked in the references.

We study the Consensus problem among $n$ agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called $j$-Majority: when activated, every agent samples $j$ other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: $(j+1)$-Majority (for $j > 1$) converges stochastically faster than $j$-Majority for any initial opinion configuration. In our analysis we use Strassen's Theorem to prove the existence of a coupling. This gives an aff