Deals Among Rational Agents

Reference: Rosenschein, J.S. & Genesereth, M.R. (1985). Proceedings IJCAI-85, Los Angeles, CA, pp. 91–99. Source file: rosenschein-genesereth-deals-among-rational-agents.pdf. URL

Summary

Rosenschein and Genesereth present a game-theoretic framework for interactions between intelligent agents with potentially disparate goals. They drop the “benevolent agent” assumption that pervaded early DAI and ask instead: what can purely rational, self-interested agents achieve through communication? The answer is given via payoff matrices, rational offer groups, and binding deals — coalitions of joint moves that no rational agent should unilaterally reject.

They prove that communication, modelled as exchanging offer groups, lets rational agents coordinate on jointly optimal outcomes that are unreachable without communication. The results are illustrated on Prisoner’s Dilemma, multiple-best-plan, and similar bargaining games, showing that binding promises transform defection-prone situations into cooperation. The paper is an early formal bridge between game theory, distributed AI, and agent communication.

Key Ideas

Rejects the benevolent-agent assumption; models agents as utility-maximisers with private goals.
Rational move = a move no agent should ever be persuaded to abandon given common knowledge of rationality.
Offer group = set of joint moves an agent is willing to commit to; deal = intersection of accepted offer groups.
Theorems: existence of non-null rational offer groups; lower bounds on guaranteed payoffs; a Group Rationality Theorem showing communication can dominate no-communication outcomes.
Shows rational cooperation in the Prisoner’s Dilemma once binding deals are available.

Connections

Conceptual Contribution

Claim: Communication among rational, non-benevolent agents can be given a precise game-theoretic semantics in which binding offers transform achievable payoff sets.
Mechanism: Payoff matrices + rationality assumptions (minimal/separate/unique move rationality) + rational offer groups whose intersections define enforceable deals.
Concepts introduced/used: Rational Offer Groups, Binding Deal, Benevolent Agent Assumption, Individual Rationality, Group Rationality.
Stance: foundational/formal (game-theoretic).
Relates to: Shoham’s Agent-Oriented Programming cites this work as one of the key precursors for modelling agent societies without assuming shared goals; AGENT-0’s “commit” primitive is the programming-language analogue of the binding deals formalised here. The paper also foreshadows Negotiation protocols, auction-based coordination, and modern Mechanism Design for MAS.

Tags

#game-theory #negotiation #rational-agents #foundational #dai #communication

Backlinks

Summary

Shoham introduces Agent-Oriented Programming (AOP) as a specialization of object-oriented programming in which the state of each module — now called an agent — is a mental state composed of beliefs, capabilities, decisions/choices, commitments, and obligations. Interpretation of these components is formally grounded in an extension of standard epistemic logics that adds temporality, obligation, decision, and capability operators.

Agents communicate via speech-act-inspired primitives (inform, request, offer, promise, decline, etc.), constrained by rules such as honesty and consistency. The paper defines a class of agent interpreters and presents AGENT-0, a concrete implemented language whose semantics is tied to the mental-state logic. Shoham also discusses “agentification” — converting arbitrary devices into AOP-programmable agents — and situates AOP against BDI architectures, speech act theory, and McCarthy’s Elephant2000.

Conceptual Contribution

Claim: Programming can be fruitfully specialised to an “agent” paradigm in which module state is a formally specified mental state and inter-module communication is a speech act constrained by rational/ethical rules.

Mechanism: Shoham extends standard modal-epistemic logic with temporal, obligation, decision and capability operators, defines the mental-state components of an agent (belief, capability, commitment, choice, obligation), then specifies a generic agent interpreter cycle (update mental state, execute commitments, handle incoming messages) and instantiates it in AGENT-0, whose programs are condition-action rules over mental state and whose messages are typed INFORM/REQUEST/UNREQUEST primitives.

Concepts introduced/used: Agent-Oriented Programming, Mental State, Commitment, AGENT-0, Speech Act Theory, Agentification, BDI, Honesty Constraint

Stance: foundational

Relates to: Establishes the mentalistic ACL stance later criticised by Agent Communication Languages - Rethinking the Principles and surveyed by Intelligent Agents Theory and Practice; AGENT-0’s speech-act primitives anticipate KQML as an Agent Communication Language and FIPA-ACL; the mental-state architecture is reused in An Interaction-oriented Agent Framework for Open Environments.

Nash Equilibrium

A strategy profile from which no player can gain by unilaterally deviating. In multi-agent systems with communication failures, the set of Nash equilibria reached by best-response dynamics can include arbitrarily poor outcomes — the core negative result of the Gopalakrishnan et al. resilience analysis.