This paper presents two decentralized algorithms for robust task allocation: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, the consensus-based bundle algorithm (CBBA). These algorithms use a market-based decision strategy for decentralized task selection and a consensus routine for conflict resolution. CBAA and CBBA are proven to converge to conflict-free assignments and exhibit provable worst-case performance. They are robust to inconsistencies in situational awareness and variations in communication network topology. Numerical experiments show that CBAA and CBBA outperform existing auction-based task-allocation algorithms in terms of convergence properties and performance. The CBBA algorithm is shown to produce the same solution as some centralized sequential greedy procedures, guaranteeing 50% optimality. The paper also discusses the convergence properties of CBBA, showing that it converges to a conflict-free assignment within N_min * D iterations in a static network with diameter D. The CBBA algorithm is also shown to be robust to inconsistent information and asynchronous conflict resolution. The paper concludes that CBBA guarantees a minimum performance level without considering the actual scoring scheme.This paper presents two decentralized algorithms for robust task allocation: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, the consensus-based bundle algorithm (CBBA). These algorithms use a market-based decision strategy for decentralized task selection and a consensus routine for conflict resolution. CBAA and CBBA are proven to converge to conflict-free assignments and exhibit provable worst-case performance. They are robust to inconsistencies in situational awareness and variations in communication network topology. Numerical experiments show that CBAA and CBBA outperform existing auction-based task-allocation algorithms in terms of convergence properties and performance. The CBBA algorithm is shown to produce the same solution as some centralized sequential greedy procedures, guaranteeing 50% optimality. The paper also discusses the convergence properties of CBBA, showing that it converges to a conflict-free assignment within N_min * D iterations in a static network with diameter D. The CBBA algorithm is also shown to be robust to inconsistent information and asynchronous conflict resolution. The paper concludes that CBBA guarantees a minimum performance level without considering the actual scoring scheme.