The Power of Small Coalitions under Two-Tier Majority on Regular Graphs Pavel ChebotarevDavid Peleg

2025-05-06 1 0 2.21MB 28 页 10玖币

侵权投诉

The Power of Small Coalitions

under Two-Tier Majority on Regular Graphs

Pavel Chebotarev ∗David Peleg †

July 19, 2023

Abstract

In this paper, we study the following problem. Consider a setting where a

proposal is oﬀered 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 vhas its own valuation of the proposal; we say that vis “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 vis a proponent of the

proposal if the majority of its neighbors are happy with it and an opponent

in the opposite case. At the end of the vote, the network collectively accepts

the proposal whenever the majority of its vertices are proponents. We study

this problem for regular graphs with loops. Speciﬁcally, we consider the

class Gn|d|hof d-regular graphs of odd order nwith all nloops and hhappy

vertices. We are interested in establishing necessary and suﬃcient conditions

for the class Gn|d|hto 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.

1 Introduction

Background and motivation: A potentially desirable property of decision-making policies, hereafter

termed the faithfulness, is that every approved decision is desired by the majority of the participating

population. More explicitly, consider a proposed decision, whose approval will make a subset Hof the

population V“happy” and the complementary set S=V\H“sad.” Then a decision-making policy is

faithful if it ensures that a proposal is approved only if |H|>|V|/2.

A straightforward faithful decision-making policy is a purely democratic policy in which individual

behavior is selﬁsh. Under this policy, each agent in the population Vvotes in favor of the proposal if

∗Technion—Israel Institute of Technology, Haifa 3200003, Israel; A.A. Kharkevich Institute for Information Transmis-

sion Problems of RAS, Moscow 127051, Russia. Email: pavel4e@technion.ac.il.

†Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel.

Email: david.peleg@weizmann.ac.il.

arXiv:2210.03410v4 [math.CO] 17 Jul 2023

and only if it is happy with it, the votes have equal weight, and the ﬁnal decision is based on majority.

This policy is sometimes referred to as the “selﬁsh” or “egoistic” democratic policy.

Equally faithful is a democratic voting policy where each agent is aware of the preferences of all other

agents, and votes according to the wishes of the majority of the population (again with votes having

equal weight and decision by majority). In this case, the voting will in fact end up with a consensus.

This policy is sometimes referred to as the “altruistic” democratic policy.

In the current paper we are concerned with two-stage decision-making policies collectively known as

“majority of majorities,” where the ﬁrst stage involves local majority votes carried out inside a number

of voting bodies (subsets of the population), and the second stage involves a majority vote among the

outcomes obtained at these voting bodies. In some cases, such a policy can alternatively be viewed as

a single-stage voting policy falling “in-between” the egoistic and altruistic policies, where each agent is

aware of the preferences of a local subset of the population (viewed as its “neighborhood”), and votes

according to the wishes of the neighborhood majority.

It has long been known that decisions made by a majority of majorities can actually be supported

only by a minority, namely, they are not faithful. Despite this property,1called the referendum paradox

[2], two-stage procedures of this kind continue to be widely used. Political examples include the electors’

system of electing the president of the United States and many parliamentary procedures. Political

scientists continue to warn that “if a bare majority of members of a bare majority of (equal-sized)

parliaments voted ‘yes’ to a measure, that would mean only slightly more than one quarter of all members

voted ‘yes’—and thus a measure could pass with nearly three quarters of members opposed” [3]. Is this

eﬀect enhanced or weakened when there are many local voting bodies, they have the same size and can

be arbitrarily mixed? To answer this question, we study the majority of majorities on regular graphs.

To formalize this question, let us say that a procedure for approving proposals is α1-protecting and

α2-trusting (with 0 ≤α1≤α2≤1) if it rejects all proposals for which |H|/|V| ≤ α1and accepts

all proposals for which |H|/|V|> α2.In the intermediate cases where α1<|H|/|V| ≤ α2, such a

procedure may accept or reject the proposal taking into account other factors. In particular, this can

be determined by the graph expressing the connections between happy and sad agents. The classical

simple majority procedure is obviously both 1/2-protecting and 1/2-trusting. Expressed in these terms,

the question we explore is to determine, for d-regular graphs of order |V|=n, the greatest α1and the

smallest α2such that the “majority of majorities” policy is α1-protecting and α2-trusting.

Contributions: The main result of the paper, Theorem 14, concerns a triple (n, d, h),where nis an

odd order of a regular graph with loops, dis the vertex degree, and his the number of happy vertices

(supporting the proposal). The theorem establishes conditions that, for a given triple (n, d, h), determine

whether there is a graph whose vertices are labeled as happy or sad with parameters (n, d, h) on which

the majority of local (neighborhood) majorities accepts the proposal as well as whether there is such

a conﬁguration on which this is not the case. In addition, we study the properties of the relationship

between the ﬁnal two-stage majority decision and the parameters n, d, and h.

The rest of the paper is organized as follows. Section 2 presents the basic notation and formulation of

the problem, and provides a simple necessary condition for the acceptance of a proposal by a two-stage

majority on a regular graph with all loops. In Section 3, the main technical statements are proved.

1As mentioned in [1], a hierarchical method of voting was at the heart of Lenin’s Utopian concept of centralized

democracy implemented in the Soviet Union (the term Soviet itself means council) and its satellites for party institutions,

national bodies, and trade unions. “For party institutions (which were the most important) there could be as many as

seven levels.”

These enable to obtain necessary and suﬃcient conditions for the class of graphs with parameters n

and dto contain a graph that accepts (rejects) a proposal making hvertices happy. These conditions

are gathered in Theorem 14 presented in Subsection 3.3. In Sections 4 and 5 some properties of the

found dependencies are reported. In particular, explicit formulas are obtained for the exact integer

values of dthat allow the lowest support of accepted proposals and simultaneously allow the highest

support for rejected proposals. Section 6 presents an alternative formulation of the problem as majority

domination on regular graphs. Finally, Section 7 provides a summary and concluding remarks, as well

as a discussion of connections to the previous literature and to some applications.

2 Preliminaries

2.1 The problem

Let G= (V, E) be a graph with vertex set V=V(G) and edge set E=E(G); |V|=n. For any u∈V,

Nu={v∈V|(u, v)∈E}is the set of neighbors of u. We consider graphs Gwith no multiple edges, but

where every vertex v∈Vhas one loop (v, v)∈E(hereafter referred to as graphs with loops). Hence2

v∈Nvfor every v∈V. The degree of vertex vis dv=|Nv|.This implies that a loop is counted once3.

We consider a setting where the vertices of a given network Gmust conduct a vote and decide

collectively on whether to accept or reject a proposal that is oﬀered to them. Each vertex vhas its

own preference: it is happy (respectively, sad) with the proposal if it expects to gain (resp., lose) from

accepting it. The preference is expressed by a private opinion (or valuation)function f:V→ {1,−1}

such that f(v) = 1 if and only if vis happy with the proposal. Thus, an opinion function finduces

aconﬁguration in the form of a binary-vertex-labeled graph Gf= (V, E, f). The conﬁguration can

alternatively be described in terms of a partition of Vinduced by f, dividing it into two disjoint parts

V=H∪S(H∩S=∅), where Hand Sare called the set of happy vertices and the set of sad vertices,

respectively. Throughout, we denote |H|=hand |S|=s.

However, the choice made by each vertex vduring the voting process is not based merely on its

own valuation f(v). Rather, it relies on the valuations of v’s neighbors as well. For any W⊆V, let

f(W) = Pv∈Wf(v). In particular, f(V) is called the weight of f. We say that a vertex v∈Vof

a conﬁguration Gfis a proponent of the proposal if a majority of its neighbors (including itself) are

happy, namely, f(Nv)≥1 (or equivalently, |Nv∩H|>|Nv∩S|); otherwise, vis an opponent. Let

P⊆Vbe the set of proponents of Gf, and p=|P|.We say that Gfis an approving conﬁguration if

p > n/2, namely, a majority of its vertices are proponents; otherwise, it is a disapproving conﬁguration.

Let Gn|ddenote the class of d-regular graphs of order nwith loops4, i.e., graphs Gon nvertices, each

having a loop, such that dv=dfor every v∈V(G).Let Gn|d|hdenote the class of conﬁgurations Gfsuch

that G∈ Gn|dand it has hhappy vertices. The class Gn|d|his called uniformly approving (respectively,

uniformly disapproving) if it contains only approving (resp., only disapproving) conﬁgurations. Gn|d|his

mixed if it contains conﬁgurations of both types. A key question studied in this paper is the following.

Problem 1. Given odd n, d ∈Nsuch that d≤n, ﬁnd the values of hsuch that Gn|d|his uniformly

approving or uniformly disapproving.

2An equivalent formalism is to consider closed neighborhoods Nu∪ {u}for graphs without loops [4].

3For a discussion of this convention see [5, Subsection 5.3].

4Among the papers studying independent sets in regular graphs with loops we mention [6].

Denote by hmin(n, d) the minimum hthat ensures the existence of approving conﬁgurations for

given nand d. Formally, for h=hmin(n, d) there exists some approving conﬁguration in the class

Gn|d|h, but for every h < hmin(n, d), the class Gn|d|his uniformly disapproving. Similarly, h−

max(n, d) is

the maximum number hof happy vertices for which there exists a disapproving conﬁguration in the

class Gn|d|h,whence for every h∈ {h−

max(n, d) + 1, . . . , n},the class Gn|d|his uniformly approving. Now

Problem 1 can be rewritten as follows.

Problem 1′.Given odd n, d ∈Nsuch that d≤n, ﬁnd hmin(n, d) and h−

max(n, d).

We also identify numbers rthat can be thought of as a 2-way security gap, in the sense that

whenever the number of happy vertices deviates upwards (respectively, downwards) from n/2 by at

least r, the resulting conﬁguration class is guaranteed to be uniformly approving (resp., disapproving),

and characterize the classes Gn|dof regular graphs whose 2-way security gap is suﬃciently small.

Let us mention two technical features that distinguish this work from some of the previous ones.

First, we consider graphs with loops (sometimes called pseudographs), as this provides a uniform account

of the situation where the voter pays attention to their own opinion and not just to the opinions of

the other neighboring voters. Such a loop is counted once in the degree of the corresponding vertex.

An alternative commonly used in some of the literature is to consider local voting on the “closed

neighborhood” Nu∪ {u}of each vertex u. This is essentially equivalent, but seems somewhat artiﬁcial

and does not allow mixing voters who take and do not take into account their own opinion. Moreover,

in this case, the degree of a vertex is no longer equal to the number of opinions taken into account.

Considering loops is devoid of these shortcomings.

Second, we estimate the number of happy vertices that can be suﬃcient in some circumstances (or

is deﬁnitely suﬃcient) for a proposal to be approved, because this keeps reference to the one-quarter

support level mentioned above. Such a direct reference is lost if one estimates the diﬀerence between the

number of happy and sad vertices, as is common in the literature on domination in graphs. However, for

comparability, we translate our main results, Theorem 14 and Proposition 18, into the graph domination

framework in Corollaries 22 and 23 (Section 6).

2.2 Basic support inequalities

We assume that nis odd, which eliminates indeﬁnite situations of no majority, when the numbers of

proponents and opponents are equal. Recall the handshaking lemma, going back to Euler (1736). For

graphs without loops, this lemma says: The sum of vertex degrees of a graph is twice the number of the

edges (see, e.g., [7]).

In our case, since nis odd, the handshaking lemma implies that d(taking the loop into account)

is odd too, which implies that the numbers of happy and sad neighbors of any vertex cannot be equal.

More speciﬁcally, throughout we let

n= 2q−1, d = 2b−1, q, b ∈N.

Then a conﬁguration Gfin Gn|d|his an approving conﬁguration whenever its number of proponents is at

least q, and a vertex vis a proponent if and only if Nvcontains at least bhappy vertices. For notational

convenience, we view “edge endpoints” as distinct entities, formally deﬁned as pairs (v, e), where vis

a vertex and eis an edge incident to v. An endpoint (v, e) is happy (respectively, sad) whenever vis.

Therefore, in an approving conﬁguration Gf∈ Gn|d|h, the number of happy endpoints is at least qb.

On the other hand, each happy vertex contributes dhappy endpoints of Gf. Consequently, hhappy

vertices contribute hd happy endpoints in total. This number is suﬃcient for Gfto be an approving

conﬁguration only if hd ≥qb, which implies that hd ≥n+ 1

2·d+ 1

2. It follows that

hmin(n, d)≥(n+ 1)(d+ 1)

4d(1)

and, expressing this bound in terms of the proportion h/n,

hmin(n, d)

n≥1

41 + n−11 + d−1.(2)

We call (1) the global support inequality.

To obtain another condition, observe that for a conﬁguration Gfin Gn|d|hwith h=|H| ≤ d/2,

|Nv∩H| ≤ h≤d/2 holds for every v∈V(Gf),so there are no proponents in V(Gf),implying that Gf

is a disapproving conﬁguration. Therefore, h≥d+ 1

2, is also necessary for a conﬁguration in Gn|d|hto

be approving, implying that

hmin(n, d)≥d+ 1

2.(3)

We refer to this inequality as the local support inequality.

Combining the global and local support inequalities (1) and (3), we have the following.

Proposition 2. hmin(n, d)≥1

2(d+ 1) max n+ 1

2d; 1.

Conditions (1) and (3) complement each other. Let us illustrate this by considering networks of

order n= 31.For such networks, the corresponding boundary curves and the intersection of the support

domains in the coordinates dand h/n are shown in Fig. 1.

(a) (b)

Figure 1: Boundary curves of the global and local support inequalities (a) and the support domain (b)

for n= 31 in the coordinates dand h/n

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ThePowerofSmallCoalitionsunderTwo-TierMajorityonRegularGraphsPavelChebotarev∗DavidPeleg†July19,2023AbstractInthispaper,westudythefollowingproblem.ConsiderasettingwhereaproposalisofferedtotheverticesofagivennetworkG,andtheverticesmustconductavoteanddecidewhethertoaccepttheproposalorrejectit.Eachverte...

展开>> 收起<<

The Power of Small Coalitions under Two-Tier Majority on Regular Graphs Pavel ChebotarevDavid Peleg.pdf

共28页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

The Power of Small Coalitions under Two-Tier Majority on Regular Graphs Pavel ChebotarevDavid Peleg

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: