Stabilizing Welfare-Maximizing Decisions via Endogenous Transfers

1 Introduction

It is 2050, and the utopia of the Internet of Things has become a reality in transportation. Autonomous vehicles taxi commuters to work, transcontinental shipping is coordinated through autonomous platoons, and algorithms balance intrinsic tradeoffs between safety and efficiency. From a policy maker's perspective, centralized solutions are appealing: by collecting global information, algorithms can guide traffic flows toward socially optimal outcomes, reduce congestion, and avoid the inefficiencies that arise when agents act myopically (e.g., Braess's paradox [Christodoulou and Koutsoupias, 2005]). However, realizing this vision in practice is far from trivial. Computing socially optimal outcomes is often NP-hard, incentive-compatible preference elicitation is possible only under restrictive conditions, and centralized mechanisms are fragile to communication failures. As a result, purely centralized solutions struggle to deliver robust, reliable performance.

These limitations have motivated research on decentralized multi-agent systems, where self-interested agents act autonomously but coordinate through learning or negotiation [Kraus, 1997; Ephrati and Rosenschein, 1997]. For example, centralized training with decentralized execution (CTDE) allows agents to learn coordinated policies under shared information during training [Lowe et al., 2017; Amato, 2024]. However, once deployed, agents cannot adapt or negotiate on the fly. In many strategic environments, agents must alternate between competition and cooperation depending on context [Axelrod and Hamilton, 1981]. Coalition formation thus provides a natural middle ground: by forming voluntary coalitions, agents can improve outcomes relative to fully decentralized behavior without requiring full centralization. Still, coalition formation comes with challenges: computing optimal coalitions is NP-hard [Sandholm et al., 1999], iterative coalition deviations may fail to converge [Meir, 2017], and strategic behavior under common social choice rules remains computationally intractable [Xia et al., 2009].

In this paper, we propose endogenous transfers as a mechanism for stabilizing collective decision-making in multi-agent systems. Collective choices among self-interested agents can naturally be modeled as a social choice problem: agents vote over alternatives, and the outcome depends on the aggregation of their preferences. Rather than prescribing coalitions or enforcing outcomes, our approach allows agents to voluntarily redistribute utility through contracts that are contingent on the chosen alternative. These transfers reshape incentives and expand the space of stable outcomes, allowing coalitions to form and dissolve strategically [Jackson and Wilkie, 2005].

Our model is inspired by classical work on bribery and coalitional manipulation in voting, as well as cooperative game-theoretic analyses of social choice [Bachrach et al., 2011]. In traditional bribery or manipulation models, coalitions are often assumed to be exogenous and bribes are budget-constrained [Elkind et al., 2009; Faliszewski et al., 2009]. By contrast, in our framework, both coalitions and transfers are fully endogenous: agents decide how to vote and how to contract, anticipating the behavior of others while respecting individual rationality. This implies that agents can offer transfers contingent on a particular alternative winning, forming stable coalitions without any central enforcement.

The central question, then, is whether such voluntary transfers are sufficient to stabilize welfare-maximizing outcomes in the presence of strategic, coalitional behavior. We show that under consensus rules, stable outcomes always exist and can be constructed efficiently, and we characterize fundamental limits on stability under more general voting rules.

1.1 Our Contributions

We make the following contributions.

Amodel of endogenous transfers in social choice. We introduce a noncooperative model in which agents may form transfer agreements in a strategic pre-round, followed by strategic voting under a fixed social choice rule. Contracts are conditioned on alternatives winning and allow agents to share the utility generated by collective decisions. This framework separates contract formation from preference revelation, enabling the study of coalition stability without assuming centralized enforcement or exogenously given coalitions.

Strong Nash equilibrium under consensus rules. For consensus rules, which generalize cooperative bargaining scenarios in which agents can veto unfavorable outcomes, we show that individually rational strong Nash equilibria (IR-SNE) always exist. Moreover, every IR-SNE induces a welfare-maximizing outcome supported by a feasible transfer scheme. We provide a simple, computationally efficient algorithm for constructing such equilibria, establishing both existence and implementability.

Necessary conditions for deviations in general. We extend our analysis beyond consensus to arbitrary anonymous, monotonic, and resolute social choice rules. In this setting, we derive a tight necessary condition for the existence of IR coalitional deviations. While this does not resolve known NP-hardness of manipulation for fixed rules, it substantially restricts the space of profitable deviations and clarifies when stability cannot be restored via transfers.

A bridge between cooperative and noncooperative social choice. Our results admit a natural interpretation in terms of cooperative game theory. Although the underlying environment is noncooperative, the presence of transferable utility allows coalitions to redistribute surplus via contracts. As a result, strong Nash equilibrium coincides with a notion of core stability with respect to the set of outcomes implementable by the social choice rule. In particular, under consensus, IR-SNE implements core-stable, welfare-maximizing allocations despite the absence of centralized mechanism design.

Finally, our framework offers a complementary perspective on classical impossibility results in mechanism design. Green and Laffont [1977] show that no mechanism can simultaneously achieve efficiency, budget balance, and strategyproofness in general quasi-linear domains [Nath and Sandholm, 2019]. Rather than contradicting this result, we refine the notion of strategic robustness. By allowing transferable utility and coalition-aware contracts, we replace unconditional truthfulness with a coalition-proof requirement: no group of agents can profitably deviate given feasible transfers among its members. In this sense, IR-SNE can be viewed as a refinement of strategyproofness that restores efficiency and budget balance within the space of coalitionally stable outcomes.

1.2 RelatedWork

The computational complexity of bribery in elections was first studied by Faliszewski et al. [2006], who asked whether a preferred candidate can be made the winner under a voting rule by modifying the preferences of a limited number of agents. Subsequent work analyzed bribery under many voting rules, including Borda [Brelsford et al., 2008], maximin [Faliszewski et al., 2011], Schulze [Parkes and Xia, 2012], k-approval [Lin, 2012], STV and ranked pairs [Xia, 2012], and Bucklin and fallback voting [Faliszewski et al., 2015]. Faliszewski [2008] introduced non-uniform bribery prices per agent under a fixed budget, while Faliszewski et al. [2007] and Elkind et al. [2009] studied models where the cost of a bribe depends on the swap distance between the original and modified rankings. For comprehensive overviews, see Baumeister and Rothe [2016] and Faliszewski and Rothe [2016].

Bribery is closely related to coalitional manipulation, which studies whether a preferred outcome can be achieved by coordinated misreports from a coalition of agents [Conitzer et al., 2007; Xia et al., 2009]. Unlike bribery, coalitional manipulation typically assumes the coalition is exogenously given; endogenously selecting coalitions and distributing gains is itself computationally intractable [Sandholm et al., 1999; Chalkiadakis et al., 2011]. Bachrach et al. [2009] introduced the cost of stability, and Bachrach et al. [2011] showed that bribery can be interpreted as utilityconstrained coalition recruitment, linking voting with cooperative game theory. Our model extends this perspective by explicitly separating preference reports from transfer contracts and by imposing individual rationality on every participating agent, leading to the notion of IR-SNE. This allows us to construct feasible, budget-balanced transfer schemes that stabilize outcomes under consensus and related rules, complementing Bachrach et al.'s existential and complexity results with a constructive, mechanism-aware analysis.

Related questions about side payments and commitments have been studied in game theory [Fershtman et al., 1991; Jackson and Wilkie, 2005; Monderer and Tennenholtz, 2009; Kalai and Kalai, 2013; Turrini, 2013; Grandi et al., 2019; Geffner et al., 2025] and in multi-agent RL [Sodomka et al., 2013; Yang et al., 2020; Haupt et al., 2024; Kolumbus et al., 2024]. A separate literature examines vote trading through competitive equilibrium models [Casella et al., 2012; Casella and Palfrey, 2021; Casella and Mac´e, 2021].

2 Preliminaries

Model. An instance I = ⟨N,A,u⟩ consists of a set of n agents N , a set of m alternatives A, and base utility functions u = (u1, . . . , un), where each ui ∶ A → R≥0. We denote the social welfare of an alternative a as SW(a) = ∑i∈N ui(a). A resolute social choice function f ∶ L(A)n → A selects a single alternative given votes of the agents. We assume f is anonymous, monotone, and resolute (AMR); it uses a fixed tie-breaking order.

In particular, we focus on the resolute consensus rule, where an alternative is chosen only if it is top-ranked by all agents; otherwise, a default alternative a∗ ∈ A is selected.

Consensus is both anonymous and monotonic.

Contracts. A contract is a collection of transfers c ∶ N × N × A → R, where ci→j(a) represents a promise from agent i to agent j conditional on alternative a. Contracts are proposed before voting and are enforced conditional on the realized winner. Each contract induces a net transfer scheme τ defined by τi(a) = ∑j≠i cj→i(a) - ∑j≠i ci→j(a), which satisfies budget balance: ∑i τi(a) = 0. We assume that the set of contracts is closed under netting, meaning that only the induced transfer scheme τ affects utilities and strategic behavior, except when the identity of transfer recipients is relevant for coalition formation. The null contract is denoted by ∅.

Strategic Voting. Given base utilities u and transfers τ, agents' realized utilities are quasi-linear: if alternative a is chosen, agent i receives Ui(a) = ui(a) + τi(a). These utilities induce a truthful preference ordering R∗ i (u + τ) ∈ L(A) defined by a ≻∗i b ⇐⇒ Ui(a) > Ui(b), with ties broken according to a fixed ordering over A. A vote Ri is truthful if Ri = R∗ i (u + τ). Agents submit votes Ri ∈ L(A), yielding a vote profile P = (R1, . . . , Rn). For a subset of agents S ⊆ N , we denote by P ∗ S (u + τ) the truthful vote profile of agents in S under utilities u + τ. We write P ∗ = P ∗N (u) for the fully truthful profile under the null contract.

Coalitional Deviation. Our definition of coalitional deviation builds on concepts from unweighted coalitional manipulation [Xia et al., 2009] and bribery [Faliszewski et al., 2009], both of which assume truthful behavior by non-deviating agents. These definitions require refinement when stability is evaluated over states (P, τ, S) or along sequences of deviations, as in iterative voting [Meir, 2017]. In particular, only agents in the deviating coalition are allowed to modify outgoing transfers or vote strategically. Agents outside the coalition may experience changes in their incoming transfers due to the coalition's modifications but do not actively adjust their own outgoing contracts.

Definition 1 (Coalitional Deviation). Given base utilities u, a coalitional deviation from a state (P, τ,S) is any state (P ′ , τ ′ ,S′ ) constructed as follows. A coalition of agents S′ ⊆ N proposes modifications to outgoing contracts (c′i→j (a))i∈S′ ,j∈N,a∈A relative to the existing contract scheme c, inducing a new transfer scheme τ ′ , and submits new votes PS′ . Agents outside the coalition, i ∉ S′ , are assumed to vote truthfully with respect to their updated utilities u + τ ′ , denoted P ∗ -S′(u + τ ′ ). The resulting vote profile is P ′ = (PS′ ,P ∗ -S′ (u + τ ′ )), yielding outcome f (P ′ ).

Under Definition 1, an agent i belongs to the deviating coalition S′ if and only if they either vote strategically with respect to u + τ ′ , or actively modify their outgoing contracts. This notion is maximal: agents may join a coalition in favor of an alternative even if they are not individually pivotal. Nonparticipating agents vote truthfully with respect to the updated utilities u+τ ′ , modeling the independence of coalitions: each coalition chooses its deviation assuming all other agents respond truthfully to their adjusted utilities. This contrasts with an alternative, sticky notion, where non-participating agents neither update their votes nor their contracts. In Appendix A, we show that equilibrium may fail to exist under this sticky variant, even in trivial settings.

Definition 2 (Individually Rational Deviation). Let (P, τ, S) be a state and (P ′ , τ ′ , S′ ) a coalitional deviation. The deviation (P ′ , τ ′ ,S′ ) is individually rational (IR) if

with strict inequality for at least one i ∈ S′ . We call (P ′ , τ ′ , S′ ) IR-feasible from (P, τ, S).

Definition 3 (Strong Nash Equilibrium). A state (P, τ, S) is a strong Nash equilibrium (SNE) if no coalition S′ has an IR deviation. It is an IR-SNE if it is additionally IR-feasible from the truthful state (P ∗ ,∅,∅).

Example 1. Consider alternatives A = {1, 2}, agents N = {1, . . . , 5}, f as the consensus rule with default a∗ = 2, and utilities u = (ui(a))i∈N,a∈A defined as:

The truthful vote is R∗ 5 = (1 ≻ 2) and R∗ i = (2 ≻ 1), i ∈ N ∖ {5}, so that f returns 2 by default. A feasible transfer scheme is

In u + τ , all agents i ∈ N vote with Ri = (1 ≻ 2), with P = (Ri)i∈N so that f(P) = 1. The set of participating agents S = N. All agents in S weakly prefer alternative 1 in u + τ to 2 in u, so the state (P, τ, S) is IR-feasible from the truthful state (P ∗ ,∅,∅). It can be shown that there is no (P ′ , τ ′ ,S′ ) so that agents in S′ weakly prefer ui(f(P ′ )) + τ ′ i (f(P ′ )) to ui(f(P)) + τi(f(P)), so (P, τ, S) is an IR-SNE.

3 Main Results

We focus on the consensus rule f , where an alternative a ∈ A is chosen if and only if all agents rank a first in their reported preferences; otherwise, a default a∗ ∈ A is selected. This setting is motivated both practically and technically. Practically, consensus generalizes cooperative bargaining scenarios, in which multiple agents must determine how to split a surplus across a Pareto frontier: what benefits one agent necessarily limits another. In these settings, the default a∗ represents a disagreement value that agents receive if negotiations fail [Thomson, 1994]. Consensus thus provides a concise description of real-world multi-agent planning problems in which any agent can veto a plan, forcing all agents to receive a∗ [Kraus, 1997].

Technically, consensus is appealing because it allows for concise necessary and sufficient conditions for SNE, and its structure provides intuition that extends to other anonymous, monotonic, and resolute (AMR) rules. To see why, consider a state (P, τ,S) in a transferable-utility social choice game. A potential SNE can fail in exactly two ways: any coalitional deviation (P ′ , τ ′ ,S′ ) starting from (P, τ,S) with f(P) = b either (i) changes the outcome, with f(P ′ ) ≠ b, or (ii) preserves the outcome, with f(P ′ ) = b but redistributes utilities in a way that strictly benefits the coalition.

Under consensus, the first type of deviation is tightly constrained: by Lemma 2, there is no IR-feasible state in which the default alternative a∗ becomes the winner, a consequence of the full coverage requirement (Definition 4) that all agents rank a non-default alternative first. The second type of deviation preserves the outcome but reallocates transfers; Lemma 3 characterizes when such redistributions are compatible with IR. Together, these lemmas pin down the structure of IRSNE under consensus and illustrate general principles for AMR rules: welfare maximization is necessary for equilibrium (Proposition 1); outcome-changing deviations require sufficiently large reallocations of utility (Proposition 4); and outcome-preserving deviations impose stricter constraints on feasible transfers than those characterized in Lemma 3.

We now turn to the technical groundwork that allows us to formalize these ideas, starting with the role of truthful states and the observability of agent participation.

3.1 Truthful Considerations and Observable Participation

Many of our proofs focus on the contract-adjusted utilities τ, rather than the underlying individual transfers (ci→j(a))i,j∈N,a∈A. We assume throughout that net transfers along transitive chains cancel out, so that an agent's utility depends only on the net transfer τi(a) when evaluating overall stability. This allows us to reason in terms of τ rather than tracking the full contract matrix c.

We emphasize, however, that this simplification is a sleight of hand: if the underlying contracts c are ignored entirely, so that agents only care how much they donate without regard to whom, this can break equilibrium, as shown in Appendix A. Lemma 1 is a direct corollary of this simplification: it lets us deduce whether i ∈ S from changes in τ, but this reasoning is valid only because τ captures the net effect of transitive contracts c.

Lemma 1 (Observable Participation). Given base utilities u, consider states (P, τ,S) and (P ′ , τ ′ ,S′ ). If there exists an alternative a ∈ A such that either (1) τi(a) ≤ 0 and τ ′ i (a) < τi(a), or (2) τi(a) ≥ 0 and τ ′ i (a) < 0, then i ∈ S′ .

Proof. In both cases, agent i experiences a strictly negative change in payoff under a ∈ A. Since non-participating agents of S′ cannot actively modify contracts, and net transfers cancel along chains by assumption, such changes can only result from i's own strategic actions, implying i ∈ S′ .

We can therefore identify coalition members based on changes in net transfers. This reasoning allows us to analyze potential deviations in general AMR rules: if the chosen alternative f(P) is not a social welfare maximizer, some coalition of agents can strictly increase their total utility by jointly reallocating transfers toward a welfare-maximizing alternative. Thus, non-welfare-maximizing states cannot be SNE.

Proposition 1 (Non-Welfare-Maximizing States Are Not SNE). Given base utilities u and an AMR rule f, consider a state (P, τ, S). If f(P) ∉ argmaxa∈A SW(a), then (P, τ, S) is not an SNE.

Proof Sketch. If f(P) is not a social welfare maximizer, the grand coalition can jointly reallocate transfers toward an alternative b ∈ argmaxa∈ASW(a) such that b fully covers f(P). This deviation weakly increases total utility for the chosen alternative for all agents, showing that (P, τ,S) cannot be stable. The full proof is provided in Appendix B.2.

Consensus strengthens the connection between social welfare maximization and equilibrium stability through the notion of full coverage. While Proposition 1 shows that nonwelfare-maximizing outcomes cannot be stable under any AMR rule, consensus imposes a stricter condition: for a nondefault alternative b to win, every agent must rank b first, meaning b must fully cover the truthful winner f(P ∗ ) in posttransfer utilities. This ensures that no coalition can profitably deviate, making social welfare maximization a necessary condition for IR-SNE under consensus.

Definition 4 (Fully Covered). Given utilities u and a transfer scheme τ, an alternative b ∈ A is said to be fully covered by u+ τ if

Proposition 2 (Truthful State Is SNE Under Consensus). Given base utilities u and a resolute consensus rule f, consider the truthful state (P ∗ ,∅,∅). If f(P ∗ ) ∈ argmaxa∈ASW(a), then (P ∗ ,∅,∅) is an SNE.

Proof Sketch. By IR and the definition of consensus, any alternative in a potential deviation must fully cover the truthful winner f(P ∗ ). Since f(P ∗ ) is a social welfare maximizer, only other welfare-maximizing alternatives can meet this requirement. Any redistribution that changes participating agents' utilities would violate IR, so no IR-feasible deviation exists. Hence, (P ∗ ,∅,∅) is an SNE. The full proof is provided in Appendix B.2.

3.2 IR-SNE for Consensus

Building on the discussion of truthful states and full coverage in Sec. 3.1, we turn to the construction and characterization of IR-SNE under the consensus rule f. In such equilibria, the selected alternative f(P) must maximize social welfare and induce full coverage in post-transfer utilities u+τ , which tightly restricts IR-feasible deviations.

Within this framework, Lemma 2 establishes that no IRfeasible deviation can make the default alternative a∗ a winner, while Lemma 3 characterizes when utilities associated with a welfare-maximizing alternative can be redistributed without violating IR. Together, these results pin down the constraints governing IR-SNE under consensus.

Lemma 2. Given base utilities u and consensus rule f, consider a state (P, τ,S) that is IR-feasible from the truthful state (P ∗ ,∅,∅). Suppose that f(P ∗ ) = a∗ ∉ argmaxa∈ASW(a), that f(P) = b ∈ argmaxa∈ASW(a), and that b has full coverage under u + τ. Then there is no state (P ′ , τ ′ ,S′ ) with f(P ′ ) = a∗ that is IR-feasible from (P, τ, S).

Proof Sketch. The argument proceeds by contradiction. Suppose that starting from a state (P, τ, S) in which the welfaremaximizing alternative b is implemented with full coverage, there exists an IR-feasible deviation to a state (P ′ , τ ′ , S′ ) that implements a∗ . IR requires that all agents in S′ weakly prefer a∗ under u + τ ′ to b under u + τ, with at least one agent strictly better off. Because b has full coverage, any such strict improvement for some agent must be financed by reducing the utility of other agents at a∗ . The key step is to show that this redistribution cannot be supported without violating IR.

Lemma 1 implies that any agent whose utility at a∗ is reduced below their base utility must be actively participating in the deviation, i.e., must belong to S′ . Hence, any agents outside S′ cannot supply the utility needed to fund a strict improvement for members of S′ . This forces the total utility at a∗ under u+τ ′ to exceed the total utility of b for agents in S′ , contradicting full coverage, which guarantees that b weakly dominates a∗ in total utility. Thus, no IR-feasible transition from (P, τ, S) back to an a∗ -implementing state exists. The full proof is presented in Appendix B.1.

As discussed above, a state (P, τ, S) can be destabilized in two ways. An outcome-changing deviation alters reports so that f(P ′ ) ≠ f(P). An outcome-preserving deviation leaves the selected alternative unchanged but allows a coalition to reallocate transfers so as to increase its members' welfare while maintaining IR and full coverage. Lemma 3 characterizes exactly when such outcome-preserving deviations are feasible.

The key insight is that any profitable redistribution must reduce the utility of some receiver agent i with τi(b) > 0, where b = f(P). Whether this reduction is feasible depends on the slack in Ui(b) relative to i's next-best alternatives. If Ui(b) strictly exceeds all other utilities, slack is realized. Otherwise, slack is only potential and must be unlocked by adjusting transfers at tied next-best alternatives. By Lemma 1, any agent whose utility falls below their base utility must participate in the deviation. As a result, slack can be extracted from i only if transfers at i's next-best alternatives can be relaxed without forcing additional agents into the coalition. Lemma 3 identifies three mutually exclusive scenarios in which this is possible, depending on whether slack is realized, supported by loose donors, or blocked by binding donors.

Definition 5 (Next-best alternative). Given base utilities u, consider a state (P, τ,S) with f(P) = b so that b has full coverage under u + τ . For every i ∈ N, let

denote the set of next-best alternatives to b.

Definition 6 (Binding NBA alternatives). Given base utilities u, consider a state (P, τ,S) with f(P) = b so that b has full coverage under u + τ. Fix a receiver i, with τi(b) > 0, and τi(x) > 0 for all x ∈ NBAi such that Ui(b) = Ui(x). For any x ∈ NBAi, let

We denote by

the set of binding NBA alternatives where all donors are tight.

Lemma 3. Given base utilities u and consensus rule f, consider a state (P, τ,S) that is IR-feasible from the truthful state (P ∗ ,∅,∅). Suppose that f(P ∗ ) = a∗ ∉ argmaxa∈ASW(a), that f(P) = b ∈ argmaxa∈ASW(a), and that b has full coverage under u + τ. There exists an IR-feasible coalitional deviation (P ′ , τ ′ ,S′ ) with f(P ′ ) ∈ argmaxa∈ASW(a) if and only if ∃i ∈ N with τi(b) > 0 so that at least one of the following hold:

• P1. (Strict slack at b.) Ui(b) > maxa∈A∖{b} Ui(a);
• P2. (Loose donors at every NBA.) ∀x ∈ NBAi, both τi(x) > 0 and ∃j ∈ N so that τj(x) < 0 and Uj(x) < Uj(b);
• P3. (Potential slack blocked only by binding donors.) Both:
• ∀x ∈ NBAi, τi(x) > 0;
• ∃j ∈ N so that ∀x ∈ Bi, τj(x) < 0 and Uj(x) = Uj(b).

Proof Sketch. The proof proceeds in two directions.

Sufficiency. The three cases correspond to progressively weaker ways of extracting transferable slack from a receiver at b, while preserving IR and full coverage constraints throughout the deviation. Fix a state (P, τ, S) with f(P) = b and full coverage. Suppose ∃i with τi(b) > 0 satisfying one of (P1)-(P3). In each case, we construct a small redistribution of transfers that lowers Ui(b) by some ϵ > 0 and reallocates this slack to other agents, while preserving both IR for the deviating coalition and full coverage of b.

Under (P1), agent i has realized slack: Ui(b) strictly exceeds all other alternatives. A donor at b can therefore withdraw transfers from i without changing i's ranking, and capture the slack while maintaining IR.

Under (P2), slack is only potential: Ui(b) ties with each next-best alternative. However, at every such alternative x ∈ NBAi there exists a donor jx, τjx (x) < 0, whose slack is not tight, with Ujx (x) < Ujx (b). These donors can each withdraw a small amount of utility from i at their respective alternatives without violating IR or full coverage of b, collectively freeing slack at b that can be redistributed.

Under (P3), some NBAs are binding: all donors at those alternatives are tight. Slack can still be extracted if there exists a single agent who is tight across all binding alternatives. This agent can absorb the necessary adjustment across those alternatives and receive the released slack at b.

In all cases, the deviating coalition excludes i, so the reduction in i's utility does not violate IR, and the modified transfers preserve full coverage of b. Hence an IR-feasible deviation with f(P ′ ) = b exists.

Necessity. Conversely, suppose there exists an IR-feasible deviation (P ′ , τ ′ ,S′ ) with f(P ′ ) ∈ argmaxa∈ASW(a). Since b has full coverage, any strict gain for agents in S′ must be financed by reducing the utility of some non-participating receiver k with τk > 0. By Lemma 1, this reduction must preserve full coverage for k at all alternatives.

If k has realized slack at b, then (P1) holds. Otherwise, slack must come from k's next-best alternatives. If at every such alternative there is a loose donor, then (P2) holds.

If some alternatives are binding, feasibility requires a single agent who can absorb the required adjustments across all binding alternatives, yielding (P3). If none of these conditions holds, no IR-preserving redistribution can reduce Uk(b), contradicting existence of the deviation.

Thus, conditions (P1)-(P3) are exhaustive and characterize exactly when an IR-feasible deviation preserving a welfaremaximizing outcome exists. The full proof is provided in Appendix B.2.

Our results combine to yield a complete characterization of IR-SNE. The key conclusion is that the truthful state is an IR-SNE if and only if the truthful winner is a socialwelfare maximizer. Intuitively, Lemma 2 rules out deviations that revert the outcome to a non-welfare-maximizing alternative once a welfare-maximizing outcome with full coverage is reached. Lemma 3 then characterizes when coalitions can profitably reallocate transfers while preserving the same welfare-maximizing outcome. Condition 3 of the theorem below encodes the slack constraints identified in Lemma 3, ensuring that no such welfare-preserving deviation can exist.

Moreover, no IR-feasible deviation can select an outcome outside argmaxa∈A SW(a). Any such deviation would necessarily violate full coverage. In particular, Lemma 5 in Appendix B.1 implies that full coverage pins down utilities across all welfare-maximizing alternatives, ruling out IRfeasible deviations to non-welfare-maximizing outcomes.

Theorem 1 (Characterization of IR-Strong Nash Equilibria). Fix base utilities u and consensus rule f . A state (P, τ, S) is an IR-SNE if and only if all of the following hold:

1. (IR-feasibility.) (P, τ,S) is IR-feasible from the truthful state (P ∗ , ∅, ∅) (or (P, τ, S) = (P ∗ , ∅, ∅)).
2. (Efficiency and coverage.) f(P) ∈ argmaxa∈ASW(a) and f(P) has full coverage under u + τ .
3. (No profitable welfare-preserving deviation.) For every i ∈ N so that τi(f(P)) > 0, none of the conditions of Lemma 3 are satisfied.

Theorem 1 yields three transparent and easy-to-check conditions for verifying whether a state (P, τ,S) constitutes an IR-SNE. In particular, it separates the problem of equilibrium existence into feasibility, outcome selection, and the absence of profitable welfare-preserving deviations. This structure naturally suggests a constructive approach.

Algorithm 1 exploits this characterization to explicitly construct an IR-SNE by iteratively building transfers that secure full coverage for a welfare-maximizing alternative while eliminating all exploitable slack. The following proposition establishes correctness and efficiency of this construction.

Proposition 3. Given base utilities u and consensus rule f with default a∗ ∈ A, consider the truthful state (P ∗ ,∅,∅) with f(P ∗ ) = a∗ ∉ argmaxa∈ASW(a). Let Dt = {i ∈ N ∶ ui(t) > Ui(t + 1)}. Algorithm 1 yields a contract scheme τ so that (P, τ,S) is an IR-SNE, where f(P) ∈ arg maxa∈A SW (a) and

Algorithm 1: IR-SNE Construction for Consensus

Require: Utilities (ui(a))i∈N,a∈A, consensus rule f with f(P ∗ ) = a∗ ∉ argmaxa∈A SW(a)

Ensure: Transfer scheme τ with (P, τ, S) is an IR-SNE

• 1: Initialize τi(a) ← 0 for all i ∈ N, a ∈ A
• 2: Order alternatives by social welfare: 1 ⪰ 2 ⪰ ⋯ ⪰ m
• 3: for all i ∈ N do
• 4: τi(a∗ ) ← 0; Ui(a∗ ) ←ui(a∗ )
• 5: end for
• 6: for all i ∈ N, t = a∗ + 1, a∗ + 2 . . . ,m do
• 7: Ui(t) ← SW(t) SW(a∗ ) ui(a∗ ); τi(t) ← Ui(t) - ui(t)
• 8: end for
• 9: for t = a∗ - 1, a∗ - 2, . . . , 1 do
• 10: Let Rt = {i ∈ N ∶ ui(t) < Ui(t + 1)}; Dt = {i ∈ N ∶ ui(t) > Ui(t + 1)}
• 11: for all i ∈ Rt do
• 12: τi(t) ← Ui(t + 1) - ui(t)
• 13: end for
• 14: Distribute total deficit -∑i∈Rt τi(t) among agents in Dt so that for all i ∈ Dt, ui(t) + τi(t) ≥ Ui(t + 1)
• 15: for all i ∈ N do
• 16: Ui(t) ←ui(t) + τi(t)
• 17: end for
• 18: end for

is the set of agents that actively participate in the algorithm via donations or strategic voting. It runs in O(nm) time.

Proof Sketch. Algorithm 1 constructs the transfer scheme τ in a stepwise manner to ensure that the welfare-maximizing alternative b becomes the equilibrium outcome, while the default alternative a∗ receives no transfers.

Intuitively, lines 3-5 assign τi(a∗ ) = 0 for all i ∈ N, so that a∗ cannot benefit from additional contributions. Lines 6-8 ensure that a∗ weakly dominates every alternative with lower social welfare in u + τ, so they do not pose a risk of deviation and can be ignored for equilibrium considerations. Since a∗ is not a social welfare maximizer, lines 9-18 then iterate through alternatives t ∈ {a∗ - 1, . . . , 1}, partitioning agents into receivers Rt (who have smaller utility on t than on t + 1) and donors Dt (who have strictly greater utility). Receivers are granted transfers to make up their deficit, while donors contribute to satisfy budget balance and maintain full coverage of t.

By construction, any agent i with τi(b) > 0 does not satisfy any of the slack conditions (P1)-(P3) from Lemma 3. Combined with Lemma 2, which rules out IR-feasible deviations to a∗ , and Lemma 5, which rules out deviations to non-welfare-maximizing alternatives, we conclude that no IR-feasible deviation exists.

A full verification of conditions (P1)-(P3) for all agents is provided in Appendix B.1.

3.3 Stability Criteria for General AMRRules

Extending the characterization of IR-SNE beyond the consensus rule is challenging. For many AMR rules, such as Maximin and Ranked Pairs, even deciding whether a fixed coalition can manipulate an outcome is NP-hard [Xia et al., 2009]. Related hardness results extend to several bribery variants when the number of alternatives is unbounded [Faliszewski, 2008; Faliszewski et al., 2009]. Rather than attempting a full characterization under a fixed voting rule, we instead identify a necessary condition for coalitional stability that is independent of the particular AMR rule and can be checked efficiently.

Proposition 1 implies that any IR-SNE outcome must select a SW-maximizing alternative. This leaves a natural question: even among welfare maximizers, when can a coalition reallocate transfers to induce a profitable deviation? To address this question, we introduce a notion that captures how much negative transfer can be reassigned without violating individual rationality.

Definition 7 (Reallocatable Amount). Given a state (P, τ, S) and an alternative ˆa ∈ A, the reallocatable amount to agent j ∈ N from a set of donors S ⊆ N over ˆa is

Intuitively, the reallocatable amount measures how much utility can be redirected toward a target agent from agents who are indifferent between the current outcome and a candidate alternative, together with the agent's own negative transfers. The following proposition uses this notion to characterize when an IR-feasible deviation exists under some AMR rule. Crucially, the voting rule is allowed to be chosen adversarially, isolating a purely economic constraint on stability.

Proposition 4 (IR-Stability via Indifferent Donors). Fix base utilities u and consider a state (P, τ,S) that is IRfeasible from the truthful state (P ∗ ,∅,∅). Suppose that f(P ∗ ) = a∗ ∉ argmaxa∈ASW(a), that f(P) = b ∈ argmaxa∈A SW(a), and that b has full coverage under u+τ .

Then there exists an AMR rule f and an IR-feasible state (P ′ , τ ′ ,S′ ) with f(P ′ ) = ˆa ∈ A ∖ {b} if and only if there exists j ∈ N such that

Proof Sketch. The key idea is that any IR-feasible deviation toward an alternative ˆa requires contributions from agents who are indifferent between ˆa and the current winner b. The reallocatable amount RA(j,Sj(ˆa), ˆa) measures the maximum utility that can be redirected to a beneficiary j using these indifferent donors and j's own negative transfers. If this amount exceeds the difference Uj(b)-Uj(ˆa), a suitably chosen AMR rule can make ˆa the winner, providing sufficiency. Conversely, if no agent satisfies this inequality, any attempt to fund a gain at ˆa would require contributions from agents who strictly prefer b, violating IR; this establishes necessity. Thus, the reallocatable-amount condition captures precisely when a coalition can profitably induce an alternative outcome under some AMR rule. The full proof is in Appendix B.2.

Proposition 4 demonstrates that full coverage alone is insufficient for IR-SNE. In addition to ensuring Ui(f(P)) ≥

Ui(f(P ∗ )) for all agents, stability also requires that no agent can be subsidized via reallocations from indifferent donors to overturn the outcome. As an immediate corollary, Lemma 2 follows by setting ˆa = a∗ , since the reallocatable-amount condition fails for all agents.

When the AMR rule f is fixed, passing the reallocatableamount test is no longer sufficient to guarantee an IR-feasible deviation, reflecting the classical computational hardness of manipulation and bribery problems. For example, swap bribery remains NP-complete for k-approval with k ≥ 3 [Elkind et al., 2009]. Nevertheless, the reallocatable-amount inequality serves as a polynomial-time filter for candidate deviations, ruling out many alternatives that cannot be sustained under any AMR rule.

4 Discussion

In this paper, we introduced an endogenous bribery mechanism that allows agents to coordinate plans in the presence of coalitional strategic behavior, along with a solution concept that is computationally simple and guaranteed to exist under the consensus rule. At the same time, our results expose several limitations and open problems that must be addressed before such mechanisms can be deployed in practice.

First, multi-agent planning is inherently combinatorial, since each agent may need to take different actions, leading to an exponential number of plans. As a result, computing IRSNE may be intractable in realistic settings. This challenge motivates future work on simplifying the representation of the problem, exploiting structure in preferences, and developing approximation algorithms that can scale to larger instances.

Second, the welfare consequences of introducing an exchange market warrant further investigation. Although the proposed mechanism explicitly accounts for coalitional strategic behavior, the resulting equilibria may reduce overall efficiency or fairness compared to outcomes where agents act independently or within small cliques of agents [Kearns, 2008]. These concerns are particularly salient when agents have unequal pricing power and when fairness is a key design consideration. Promising directions for future research include extending the framework to online settings, where agents or alternatives arrive and depart over time, as well as exploring auction-based mechanisms for contract formation.

Finally, our analysis adopts Pareto dominance as the basis for individual rationality, implicitly assuming that agents are willing to participate in any coalition that weakly benefits them. This abstraction overlooks the possibility that agents may object to outcomes in which others receive disproportionately large gains, particularly when they have strategic leverage through credible non-participation. For example, consider two agents with default payoffs (0, 0) and two feasible outcomes: (A) = (1, 1000) and (B) = (2, 100). Although both outcomes are Pareto optimal, agent 1 may refuse to participate unless agent 2 agrees to outcome (B), illustrating how leverage and commitment power can shape equilibrium selection. Modeling such behavior is closely related to the problem of optimal commitment, which is computationally hard and remains an important direction for future work [Littman and Stone, 2001; Conitzer and Sandholm, 2006].