Title page -- Contents -- Introduction -- Overview -- I Preliminaries and Background -- Distributed Constraint Optimization Problems -- Definitions and Notation -- Assumptions and Conventions -- Ownership and control -- Identification and communication patterns -- Privacy and Self-Interest -- Example Applications -- Distributed Meeting Scheduling -- Distributed Combinatorial Auctions -- Overlay Network Optimization -- Distributed Resource Allocation -- Takeoff and Landing Slot Allocation -- Background -- Backtrack Search in DCOP Algorithms -- Synchronous search algorithms -- Synchronous Branch and Bound (SynchBB) -- dAO-Opt: Simple AND/OR Search For DCOP -- dAOBB: AND/OR Branch and Bound for DCOP -- Asynchronous search algorithms -- Asynchronous search for DisCSP -- ADOPT -- Non-Commitment Branch and Bound -- Asynchronous Forward Bounding (AFB) -- Summary of distributed search methods -- Dynamic Programming (inference) in COP -- BTE -- Partial Centralization: Optimal Asynchronous Partial Overlay (OptAPO) -- Pseudotrees / Depth-First Search Trees -- DFS trees -- Distributed DFS generation: a simple algorithm -- Heuristics for finding good DFS trees -- Heuristics for generating low-depth DFS trees for search algorithms -- Heuristics for generating low-width DFS trees for dynamic programming -- II The DPOP Algorithm -- DPOP: A Dynamic Programming Optimization Protocol for DCOP -- DPOP: A Dynamic Programming Optimization Protocol for DCOP -- DPOP phase 1: DFS construction to generate a DFS tree -- DPOP phase 2: UTIL propagation -- DPOP phase 3: VALUE propagation -- DPOP: Algorithm Complexity -- Experimental evaluation -- A Bidirectional Propagation Extension of DPOP -- H-DPOP: compacting UTIL messages with consistency techniques -- Preliminaries -- CDDs: Constraint Decision Diagrams -- H-DPOP - Pruning the search space with hard constraints.

UTIL propagation using CDDs -- Building CDDs from constraints: -- Implementing the JOIN operator on CDD messages -- Implementing the PROJECT operator on CDD messages -- The isConsistent plug-in mechanism -- Comparing H-DPOP with search algorithms -- NCBB: Non Commitment Branch and Bound Search for DCOP -- NCBB with caching -- Comparing pruning in search and in H-DPOP -- Experimental Results -- DPOP vs H-DPOP: Message Size -- Optimal query placement in an overlay network -- Random Graph Coloring Problems -- NQueens problems using graph coloring -- Winner Determination in Combinatorial Auctions -- H-DPOP vs NCBB: Search Space Comparison -- H-DPOP vs NCBB: N-Queens -- H-DPOP vs NCBB: Combinatorial Auctions -- Related work -- Summary -- III Tradeoffs -- Tradeoffs between Memory/Message Size and Number of Messages -- DPOP: a quick recap -- DFS-based method to detect subproblems of high width -- DFS-based Label propagation to determine complex subgraphs -- MB-DPOP(k): Trading off Memory vs. Number of Messages -- MB-DPOP - Labeling Phase to determine the Cycle Cuts -- Heuristic labeling of nodes as CC -- MB-DPOP - UTIL Phase -- MB-DPOP - VALUE Phase -- MB-DPOP(k) - Complexity -- MB-DPOP: experimental evaluation -- Meeting scheduling -- Graph Coloring -- Distributed Sensor Networks -- Related Work -- Summary -- O-DPOP: Message size vs. Number of Messages -- O-DPOP Phase 2: ASK/GOOD Phase -- Propagating GOODs -- Value ordering and bound computation -- Valuation-Sufficiency -- Properties of the Algorithm -- Comparison with the UTIL phase of DPOP -- O-DPOP Phase 3: top-down VALUE assignment phase -- O-DPOP: soundness, termination, complexity -- Experimental Evaluation -- Comparison with search algorithms -- Summary -- Tradeoffs between Memory/Message Size and Solution Quality -- LS-DPOP: a local search - dynamic programming hybrid.

LS-DPOP - local search/inference hybrid -- Detecting areas where local search is required -- Local search in independent clusters -- One local search step -- Large neighborhood exploration - analysis and complexity -- Iterative LS-DPOP for anytime -- Experimental evaluation -- Related Work -- Summary -- A-DPOP: approximations with minibuckets -- UTIL propagation phase -- Limiting the size of UTIL messages with approximations -- VALUE propagation -- A-DPOP complexity -- Tradeoff solution quality vs computational effort and memory -- AnyPOP - an anytime algorithm for large optimization problems -- Dominant values -- Propagation dynamics -- Dynamically delta-dominant values -- Iterative A-DPOP for anytime behaviour -- Experimental evaluation -- Summary -- PC-DPOP: Tradeoffs between Memory/Message Size and Centralization -- PC-DPOP(k) - partial centralization hybrid -- PC-DPOP - UTIL Phase -- PC-DPOP - Centralization -- Subproblem reconstruction -- Solving centralized subproblems -- PC-DPOP - VALUE Phase -- PC-DPOP - Complexity -- Experimental evaluation -- Graph Coloring -- Distributed Sensor Networks -- Meeting scheduling -- Related Work -- A Note on Privacy -- Summary -- IV Dynamics -- Dynamic Problem Solving with Self Stabilizing Algorithms -- Self-stabilizing AND/OR search -- Self-stabilizing Dynamic Programming: S-DPOP -- S-DPOP optimizations for fault-containment -- Fault-containment in the DFS construction -- Fault-containment in the UTIL/VALUE protocols -- S-DPOP Protocol Extensions -- Super-stabilization -- Fast response time upon low-impact faults -- Solution stability in dynamically evolving optimization problems -- Commitment deadlines specified for individual variables -- Solution Stability as Minimal Cost of Change via Stability Constraints -- Algorithm RS-DPOP -- UTIL propagation -- VALUE propagation.

Real time guarantees in dynamically evolving environments -- V Self-Interest -- Distributed VCG Mechanisms for Systems with Self-Interested Users -- Background on Mechanism Design and Distributed Implementation -- Social Choice Problems -- Modeling Social Choice as Constraint Optimization -- A Centralized COP Model as a MultiGraph -- A Decentralized COP (DCOP) Model Using Replicated Variables -- Cooperative Case: Efficient Social Choice via DPOP -- Building the DCOP -- Constructing the DFS traversal -- Handling the Public Hard Constraints. -- Handling replica variables -- Complexity Analysis of DPOP Applied to Social Choice -- Handling Self-interest: A Faithful Algorithm for Social Choice -- The VCG Mechanism Applied to Social Choice Problems -- Faithful Distributed Implementation -- The Partition Principle applied to Efficient Social Choice -- Simple M-DPOP -- M-DPOP: Reusing Computation While Retaining Faithfulness -- Phase One of M-DPOP for a Marginal Problem: Constructing DFS-i -- Phase Two of M-DPOP for a Marginal Problem: UTIL-i propagations -- Experimental Evaluation: Distributed Meeting Scheduling -- Summary of M-DPOP -- Achieving Faithfulness with other DCOP Algorithms -- Adapting ADOPT for Faithful, Efficient Social Choice -- Adaptation of ADOPT to the DCOP model with replicated variables -- Reusability of computation in ADOPT -- Adapting OptAPO for Faithful, Efficient Social Choice -- Budget Balance -- Related Work -- The VCG Mechanism Applied to Social Choice Problems -- Incentive Compatible VCG Payment Redistribution -- R-M-DPOP: Retaining Optimality While Seeking to Return VCG Payments -- An example of possible, indirect influence -- Detecting Areas of Indirect, Possible Influence -- A concrete numerical example of LABEL propagation -- BB-M-DPOP: Exact Budget-Balance Without Optimality Guarantees -- Experimental evaluation.

R-M-DPOP: Partial redistribution while maintaining optimality -- BB-M-DPOP: Complete redistribution in exchange for loss of optimality -- Discussions and Future Work -- Distributed implementations: incentive issues -- Alternate Scheme: Retaining Optimality While Returning Micropayments -- Tuning the redistribution schemes -- Summary -- Conclusions -- Contributions -- Concluding Remarks -- Appendix -- Performance Evaluation for DCOP algorithms -- Performance Issues with Asynchronous Search -- FRODO simulation platform -- Other applications of DCOP techniques -- Distributed Control -- Distributed Coordination of Robot Teams -- Relationships with author's own previous work -- Bibliography -- List of Figures -- List of Tables.