Voting Protocol

These are the formal rules that determine when a vote is valid and when the protocol concludes.

• Quorum: A minimum threshold of participating agents required for the vote to be legally binding (e.g., >50% of eligible agents).
• Termination Conditions: Defined endpoints such as a fixed deadline, a unanimous agreement, or the achievement of a supermajority (e.g., 2/3 in favor).
• Purpose: Prevents indecision and ensures the outcome has sufficient legitimacy and participation from the agent population.

A deterministic subroutine invoked when the voting rule produces a tie between two or more alternatives.

• Common Mechanisms:
  • Lexicographic Order: A pre-defined priority order of alternatives.
  • Chair's Decisive Vote: A designated authority agent breaks the tie.
  • Random Selection: A verifiably random draw (e.g., using a cryptographic beacon).
• Criticality: A poorly specified tie-breaker can become a single point of failure or manipulation in an otherwise robust protocol.

This is a desired property, not a separate component, but it must be engineered into the rule and format. A protocol is strategy-proof if an agent's optimal strategy is always to reveal its true preferences, regardless of how others vote.

• Gibbard-Satterthwaite Theorem: Proves that for non-dictatorial rules with 3+ alternatives, no ranked-choice rule is universally strategy-proof.
• Practical Engineering: While perfect strategy-proofness is often impossible, protocols can be designed to minimize the impact and benefit of strategic voting (e.g., using approval voting or scoring rules).

The procedural guarantee that the execution of the protocol can be independently verified. In digital multi-agent systems, this is often cryptographic.

• Elements Include:
  • Ballot Secrecy with Public Verifiability: Votes are anonymous, but anyone can verify the tally was computed correctly from the published, encrypted ballots.
  • Immutable Log: An append-only record of participation timestamps and the final aggregated result.
• Purpose: Ensures the integrity of the outcome, building trust among participating autonomous agents that the announced result is correct.

A framework for modeling multi-agent coordination where a global objective must be optimized subject to constraints distributed among agents. Agents communicate to find variable assignments that maximize social welfare. This is a more general and computationally explicit form of collective decision-making compared to voting.

• Variables and Domains: Each agent controls some variables with possible values.
• Constraints and Utilities: Define costs or rewards for specific combinations of variable assignments.
• Algorithms: Include DPOP and Max-Sum for finding optimal or near-optimal solutions with limited communication.

A negotiation process where agents form cooperative groups (coalitions) to achieve goals unattainable alone. This involves negotiation over coalition structure and payoff distribution, often analyzed using cooperative game theory concepts like the core or the Shapley value.

• Stability: A coalition is stable if no subgroup has an incentive to break away (e.g., in the bargaining set).
• Characteristic Function: Defines the value (utility) a coalition can generate.
• Overlap with Voting: Voting can be used within a coalition to make internal decisions after it forms.

The 'inverse engineering' of negotiation protocols. Instead of analyzing agent behavior in a given game, mechanism design creates the rules of interaction (mechanisms) so that self-interested agents' strategic choices lead to a desired social outcome (e.g., efficiency, revenue, truthfulness).

• Revelation Principle: A key theorem stating any mechanism's outcome can be replicated by a direct revelation mechanism where agents simply report their private types.
• Strategy-Proofness: A mechanism is strategy-proof if truth-telling is a dominant strategy for all agents (e.g., the Vickrey auction).
• Voting rules like Borda count or plurality are specific, pre-defined mechanisms for preference aggregation.

A structured interaction framework, often bilateral, governing the exchange of offers and counteroffers to reach a mutually acceptable agreement. Based heavily on game theory models.

• Rubinstein Bargaining Model: The canonical model of alternating offers with time discounting.
• Nash Bargaining Solution: A cooperative solution predicting the outcome of a negotiation where agents can achieve mutual gains.
• Monotonic Concession Protocol: A simple protocol where agents must make concessions in each round.
• Reservation Price: The private walk-away point for each agent, a critical concept in bargaining distinct from a vote.