The power of small coalitions under two-tier majority on regular graphs

DOI10.1016/J.DAM.2023.07.011MaRDI QIDQ6048435zbMATH OpenOpenAlexFDO

Authors Pavel Chebotarev, David Peleg

Publication date 14 September 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.03410

zbMATH Keywords

majority of majoritiesregular graphssmall coalitionsvoting systems

Mathematics Subject Classification ID

Applications of graph theory (05C90) Voting theory (91B12)

Abstract: In this paper, we study the following problem. Consider a setting where a proposal is offered to the vertices of a given network $G$, and the vertices must conduct a vote and decide whether to accept the proposal or reject it. Each vertex $v$ has its own valuation of the proposal; we say that $v$ is ``happy if its valuation is positive (i.e., it expects to gain from adopting the proposal) and ``sad if its valuation is negative. However, vertices do not base their vote merely on their own valuation. Rather, a vertex $v$ is a emph{proponent} of the proposal if a majority of its neighbors are happy with it and an emph{opponent} in the opposite case. At the end of the vote, the network collectively accepts the proposal whenever a majority of its vertices are proponents. We study this problem on regular graphs with loops. Specifically, we consider the class ${mathcalG}_{n|d|h}$ of $d$-regular graphs of odd order $n$ with all $n$ loops and $h$ happy vertices. We are interested in establishing necessary and sufficient conditions for the class ${mathcalG}_{n|d|h}$ to contain a labeled graph accepting the proposal, as well as conditions to contain a graph rejecting the proposal. We also discuss connections to the existing literature, including that on majority domination, and investigate the properties of the obtained conditions.

Recommendations

• The power of small coalitions in graphs
• Immunity against local influence
• Majority model on random regular graphs
• Majority domination in graphs
• Central limit theorem for majority dynamics: bribing three voters suffices

Cites work

• k-subdomination in graphs
• Analytical expression of the expected values of capital at voting in the stochastic environment
• Designing stable elections
• Distributed Anonymous Discrete Function Computation
• Do local majorities force a global majority?
• Dominating functions with integer values in graphs—a survey
• Eigenvalue bounds for independent sets
• Fibrations of graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1109393 (Why is no real title available?)
• scientific article; zbMATH DE number 1109397 (Why is no real title available?)
• scientific article; zbMATH DE number 1124597 (Why is no real title available?)
• scientific article; zbMATH DE number 1142760 (Why is no real title available?)
• scientific article; zbMATH DE number 1792629 (Why is no real title available?)
• scientific article; zbMATH DE number 861417 (Why is no real title available?)
• scientific article; zbMATH DE number 1414348 (Why is no real title available?)
• scientific article; zbMATH DE number 5043395 (Why is no real title available?)
• Local and global majorities revisited
• Local and global proportionality
• Local majorities, coalitions and monopolies in graphs: A review
• Lower bounds on several versions of signed domination number
• Lower bounds on the minus domination and \(k\)-subdomination numbers.
• Majority domination in graphs
• Majority Efficient Representation of the Citizens in a Federal Union
• Majority model on random regular graphs
• Majority reinforcement number
• Minority becomes majority in social networks
• Minus domination in regular graphs
• NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY
• Noise sensitivity and chaos in social choice theory
• On majority domination in graphs
• On signed majority total domination in graphs
• Partial signed domination in graphs
• Phase transition of the 2-choices dynamics on core-periphery networks
• Signed and minus dominating functions in graphs
• Size bounds for dynamic monopolies
• Strict majority functions on graphs
• The effect of local majority on global majorityin connected graphs
• The optimal majority threshold as a function of the variation coefficient of the environment
• The theoretical Shapley-Shubik probability of an election inversion in a toy symmetric version of the US presidential electoral system
• Towards a theory of domination in graphs
• Voting originated social dynamics: quartile analysis of stochastic environment peculiarities

Cited in

(1)

• Flip colouring of graphs

This page was built for publication: The power of small coalitions under two-tier majority on regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6048435)