Abstract
To successfully complete a complex project, agents (companies or individuals) must form a team with the required competencies and resources. A team can be formed either by the project issuer based on individual agents' offers (centralized formation) or by the agents themselves (decentralized formation) bidding for a project as a consortium. The authors investigate rational strategies for agents, propose concepts to characterize the stability of winning teams and study computational complexity of finding these concepts of stability.
Introduction
In large-scale engineering and infrastructure, no single entity typically possesses all the skills required for completion. Instead, a client must hire a team of specialized agents. Traditionally, this has been viewed as a centralized problem: agents submit individual bids, and the client selects the cheapest feasible group.
However, real-world subcontractors often coordinate to form consortia before bidding. This creates a decentralized market where agents must balance cooperation—to form a viable team—and competition—to secure profit without being undercut. This paper addresses the gap in understanding how these teams form, their stability (i.e., resistance to deviations), and the computational efficiency of finding such stable states.
Theoretical Framework and Methods
The authors model project bidding as a strategic game. A "team" is defined by its members, their requested salaries, and the total cost to the client. Two distinct payment structures are analyzed:
- Project Salary: A fixed fee for the job regardless of time spent.
- Hourly Salary: Payment based on the duration of tasks assigned.
To maintain generality across various domains (from commodity auctions to complex scheduling), the authors use an abstract oracle (a "black box" function) to determine team feasibility. While the paper is theoretical and does not use empirical datasets, it employs formal proofs and constructed examples to demonstrate the existence (or lack thereof) of equilibria.
Stability Concepts
The paper introduces several stability concepts to characterize equilibrium states:
- Strong Nash Equilibrium (SNE): A state where no group of agents can deviate together to improve everyone's payoff.
- Rigorously Strong Nash Equilibrium (RSNE): A stricter version for "cautious" agents who avoid any risk of losing their contract.
- Weakly Winning Teams: A concept for decentralized markets where a perfectly stable team might not exist due to constant undercutting.
Key Insights and Results
The research reveals a significant "Stability Gap" in decentralized markets. A "Strongly Winning Team" may not exist even if the project is feasible, as agents can enter a cycle of shifting alliances to undercut competitors. Conversely, in the centralized "Project Salary" model, an SNE always exists if the project is feasible, typically corresponding to the cheapest possible team.
The choice of payment model also impacts stability. The "Hourly Salary" model is inherently more chaotic; an SNE might not exist in hourly models even when guaranteed in project-based ones.
Computational Complexity
A major contribution of this work is the comprehensive mapping of computational costs for different solution concepts across centralized and decentralized perspectives.
As shown in the table above, checking if a team is "Rigorously Strongly Winning" takes $O(n^2 \cdot FCFT)$ time, where $FCFT$ is the cost of finding the cheapest feasible team. While finding an SNE in the centralized model can be solved in polynomial time (if salaries are rational), the underlying problem of finding a feasible team in realistic scheduling environments is proven to be NP-hard and W[1]-hard.
Conclusion and Future Work
The study highlights the complexities of team formation in competitive bidding environments. While centralized models offer more predictable stability, decentralized consortia face challenges with existence and undercutting. Future work may address the open question of efficient algorithms for discrete (integer) salaries in decentralized settings and explore heuristics for NP-hard scheduling constraints where exact solutions are computationally prohibitive.
Summary updated