Voting Protocol

The voting rule is the mathematical function that maps a profile of individual agent preferences to a collective outcome. It is the algorithmic core of the protocol.

• Examples: Plurality, Borda Count, Approval Voting, Single Transferable Vote (STV).
• Key Property: Different rules incentivize different voting strategies and produce different social choice properties, such as Condorcet consistency or resistance to strategic manipulation.

This component defines the structure in which agents must express their preferences over the set of alternatives.

• Common Formats:
  • Rank-Ordered List: Agents submit a complete or partial ranking (e.g., A > B > C).
  • Approval Set: Agents select all alternatives they find acceptable.
  • Utility Scores: Agents assign numerical scores to each alternative.
• Engineering Trade-off: The format balances expressiveness against complexity and privacy. A rank-order is simple but less nuanced than cardinal utility scores.

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 broader class of distributed algorithms enabling a group of agents to agree on a single data value or course of action, of which voting is a specific type. Key distinctions include:

• Byzantine Fault Tolerance: Protocols designed to reach agreement even if some agents are malicious or faulty.
• Proof-of-Stake/Work: Consensus mechanisms from blockchain that use economic stake or computational work instead of simple vote counts.
• Finality: The property that once a decision is made, it cannot be reversed, which is a stricter guarantee than many basic voting protocols provide.

A market-driven protocol where agents compete to acquire resources or tasks by submitting bids according to predefined rules. Unlike voting's preference aggregation, auctions focus on price discovery and allocation to the highest bidder. Common types include:

• English Auction: Open, ascending price.
• Vickrey Auction: Sealed-bid, second-price (truth-telling is a dominant strategy).
• Dutch Auction: Descending price until a bid is made.
• Combinatorial Auction: Allows bids on bundles of items, solving the complex Winner Determination Problem.

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.