Distributed Constraint Optimization (DCOP)

Each agent exclusively controls its own set of variables and knows only its local constraints. No single entity has a global view of the problem. Agents must communicate to resolve interdependencies.

• Local Constraint Knowledge: An agent only knows the cost functions involving its own variables.
• Privacy Preservation: Internal utility functions remain hidden; only value assignments are shared.
• Autonomous Decision: Each agent ultimately decides its own variable's value based on received messages.

The problem is modeled as a constraint graph where nodes represent agents (or their variables) and edges represent shared constraints. The graph's structure directly impacts algorithmic complexity.

• Sparse Graphs: Fewer inter-agent dependencies allow faster convergence.
• Dense Graphs: Many overlapping constraints require more coordination overhead.
• Cyclic Structures: Loops in the graph necessitate more sophisticated inference to avoid oscillation.

Agents coordinate by exchanging structured messages containing cost information. Algorithms like Max-Sum and ADOPT define specific message protocols to propagate utility assessments through the constraint graph.

• Max-Sum: Operates on a factor graph, passing messages that summarize marginal utilities for each possible value.
• ADOPT: Uses a depth-first search tree with threshold-based backtracking to guarantee optimality.
• DPOP: Employs dynamic programming over a pseudo-tree, aggregating utilities from leaves to root.

All local constraints aggregate into a single global objective function—typically the sum of all individual cost functions. The goal is to find the variable assignment that minimizes (or maximizes) this aggregate.

• Additive Costs: The most common aggregation, where total cost = sum of all local constraint costs.
• Pareto Optimality: Ensures no agent can improve its outcome without worsening another's.
• Social Welfare: Maximizing the sum of all agent utilities is a standard optimization target.

Agents do not wait for a central clock tick. They process incoming messages and update their variable assignments independently, enabling robust operation in dynamic environments.

• No Global Synchronization: Eliminates single-point bottlenecks and reduces idle time.
• Concurrent Computation: Multiple agents solve sub-problems simultaneously.
• Resilience to Latency: Algorithms tolerate variable message delays without deadlock.

For complex, densely constrained problems, finding the exact optimal solution can be computationally prohibitive. DCOP algorithms often provide anytime behavior with guaranteed error bounds.

• Anytime Algorithms: Return a feasible solution quickly and improve it if given more time.
• Approximation Ratio: A formal guarantee that the solution cost is within a factor k of the optimal.
• Bounded Optimality: Trades off absolute optimality for practical, real-time decision-making.

A stable state in a non-cooperative game where no individual agent can improve its outcome by unilaterally changing its strategy. In spectrum sharing, this models the convergence point of competitive channel selection.

• Each radio's strategy is a best response to others
• Used to predict steady-state behavior in DCOP formulations
• Does not guarantee global optimality, only local stability

A machine learning paradigm where multiple autonomous agents learn optimal policies through trial-and-error interaction within a shared environment. MARL provides a learning-based alternative to explicit DCOP solvers.

• Agents observe local state and receive rewards
• Centralized training with decentralized execution is common
• Handles non-stationarity where each agent's policy shift changes the environment for others

A sealed-bid combinatorial auction mechanism that incentivizes truthful bidding by charging each winner the marginal harm their presence imposes on other bidders. Applied to efficient spectrum license allocation.

• Bidders reveal true valuations as a dominant strategy
• Computes optimal assignment maximizing social welfare
• Payment rule ensures strategy-proofness, aligning individual incentives with global efficiency

A resource allocation algorithm that balances total network throughput against individual user service levels. It maximizes the sum of logarithmic utilities, ensuring no user is starved.

• Compromise between max-throughput and max-min fairness
• Used in LTE/5G scheduling and DCOP utility functions
• Prevents greedy allocation that would exclude edge users

A deep learning model representing wireless networks as graphs where nodes are transceivers and edges capture interference relationships. GNNs learn to predict complex interference patterns for optimized resource allocation.

• Naturally captures topological constraints of DCOP
• Permutation-invariant to node ordering
• Can approximate DCOP solutions with orders-of-magnitude speedup over exact solvers

A set of predefined, non-cooperative rules and behavioral protocols enabling cognitive radios to autonomously manage access without explicit real-time negotiation. This is a lightweight alternative to full DCOP coordination.

• Rules like polite channel switching and transmit power control
• Reduces protocol overhead in dense deployments
• May converge to suboptimal but stable allocations compared to full optimization