Utility Function

A utility function is a mathematical mapping from a set of possible outcomes or states of the world to real numbers. It formally encodes an agent's ordinal preferences (ranking of outcomes) into cardinal utility values (strength of preference). This allows for quantitative comparison and optimization, which is essential for algorithmic negotiation. For example, an agent might assign a utility of 10 to winning a contract at a low price and a utility of 2 to losing it.

The fundamental axiom of rational choice is that an agent seeks to maximize its expected utility. During negotiation, the agent evaluates potential agreements (e.g., price, delivery time, service level) by calculating their utility and selects the action that yields the highest value. This objective drives all strategic behavior, from bidding in an auction to making concessions in bargaining.

• Expected Utility Theory: Agents choose between uncertain outcomes by calculating the probability-weighted sum of utilities.
• Revealed Preference: An agent's chosen action reveals its utility function, a principle used in inverse reinforcement learning.

The curvature of a utility function encodes an agent's attitude toward risk. This is critical in negotiations involving uncertainty or lotteries.

• Risk-Averse: Concave utility function (e.g., U(x) = log(x)). The agent prefers a sure outcome over a gamble with the same expected value.
• Risk-Seeking: Convex utility function. The agent prefers the gamble.
• Risk-Neutral: Linear utility function (e.g., U(x) = x). The agent cares only about expected value.

In financial negotiations, a risk-averse buyer may accept a higher sure price to avoid the uncertainty of an auction.

Real-world negotiations involve multiple issues (price, quality, deadline). A multi-attribute utility function aggregates preferences across these dimensions into a single score. Common forms include:

• Additive: U(bundle) = w1 * U1(price) + w2 * U2(quality) + ... where weights (w1, w2) reflect issue importance.
• Multiplicative: Used when attributes have interactions.

This allows for trade-offs. An agent may concede on price (small utility loss) for a major improvement in delivery time (large utility gain), seeking Pareto-optimal outcomes.

An agent's utility function is typically private information (its type). This creates a strategic environment studied in mechanism design. The goal is to design protocols (like specific auctions) where truthfully revealing one's utility is the optimal strategy (strategy-proofness or incentive compatibility).

• Example: In a Vickrey auction, bidding one's true valuation is a dominant strategy because the winner pays the second-highest bid.
• The revelation principle states that any outcome achievable by a mechanism can be replicated by a direct mechanism where agents truthfully report their types.

Utility is not always static. It can evolve based on:

• Time Discounting: Future gains are worth less than immediate ones, modeled by a discount factor (δ). This is central to the Rubinstein bargaining model.
• Changing Context: An agent's utility for a resource may depend on what other resources it has already acquired (complementarity/substitutability).
• Learning and Adaptation: Agents may update their understanding of their own preferences or the value of goods based on new information.

This dynamism necessitates protocols that handle iterated bargaining and state-dependent offers.

The inverse engineering of game theory, where a protocol (or 'game') is designed so that the strategic, self-interested actions of rational agents lead to a socially desirable outcome. The designer specifies the rules, and agents—equipped with their private utility functions—choose strategies. Key goals include:

• Efficiency: Maximizing total social welfare (sum of utilities).
• Incentive Compatibility: Ensuring truth-telling is a dominant strategy.
• Revenue Maximization (for auctions). The Revelation Principle is a central theorem, stating any equilibrium outcome of any mechanism can be replicated by a direct mechanism where agents truthfully report their private types.

A state of resource allocation or agreement where it is impossible to make any one agent better off (increase their utility) without making at least one other agent worse off. It represents an efficiency frontier, not a single point. In negotiation:

• An outcome is Pareto superior to another if it makes at least one agent better off and no agent worse off.
• Rational agents should not agree to a deal that is not Pareto optimal, as a Pareto improvement would exist. The Nash Bargaining Solution selects a unique, 'fair' point from the set of Pareto optimal outcomes based on axiomatic principles.

The private walk-away point for an agent in a negotiation, representing the minimum price a seller will accept or the maximum price a buyer will pay. It is a critical parameter derived from an agent's utility function and outside options (their Best Alternative To a Negotiated Agreement - BATNA).

• In a purchase negotiation, a buyer's reservation price is the point where Utility(deal) = Utility(no deal).
• In auction theory, it is often equivalent to an agent's true private valuation. The negotiation zone or Zone of Possible Agreement (ZOPA) exists when the buyer's reservation price is higher than the seller's.

A protocol (e.g., an auction or matching algorithm) designed so that an agent's dominant strategy is to report its private information—such as its true valuation or preferences encoded in its utility function—honestly, regardless of what other agents do. This property is also called dominant-strategy incentive compatibility.

• The Vickrey Auction (second-price sealed-bid) is a classic example: bidders are incentivized to bid their true value.
• Strategy-proofness is a strong and desirable property that simplifies agent reasoning, as they need not model others' behavior. It is a key objective in mechanism design.

A framework for modeling multi-agent coordination problems where a global objective (utility) must be optimized subject to constraints, but decision variables and constraints are distributed among autonomous agents. Each agent controls its own variables and has a local utility function.

• The goal is for agents to collaboratively assign values to their variables to maximize the sum of all local utilities (the global utility).
• Agents communicate to find this optimal solution without centralizing all information.
• It formally models problems like distributed scheduling, sensor network coordination, and multi-agent task allocation.

A seminal solution concept in cooperative game theory for two-agent bargaining. Given a bargaining problem—defined by a set of feasible utility outcomes and a disagreement point (utilities if no deal is made)—the Nash solution selects a unique agreement based on four axioms: Pareto optimality, symmetry, scale invariance, and independence of irrelevant alternatives.

• Mathematically, it maximizes the product of the agents' utility gains: (U1 - d1) * (U2 - d2), where d is the disagreement point.
• It provides a normative prediction of a 'fair' outcome when agents have equal bargaining power and can make binding agreements, serving as a benchmark for evaluating negotiation protocols.