Combinatorial optimization problems in the real world are ubiquitous. Practical applications include planning, scheduling, distributed control, resource allocation, etc. These problems often involve multiple agents and can be formulated as a Multi-agent Constraint Optimization Problem (MCOP). A major challenge in such systems is the agent coordination, such that a global optimal outcome is achieved. This thesis is devoted to two major issues that arise in MCOP: efficient optimization algorithms and manipulations from self-interested agents. We introduce a new randomized local search optimization algorithm called Random Subset Optimization (RSO). The RSO algorithm is tested on various applications and demonstrated to converge faster than other local search techniques while achieving competitive performance. For self-interested agents, we define a new form of incentive compatibility called size-limited incentive compatibility and show that RSO algorithm can be used to prevent agents' manipulations.