People are Processors: Coalitional Auctions for Complex Projects

Piotr Skowron, Krzysztof Rzadca, Anwitaman Datta

Abstract

To successfully complete a complex project, be it a construction of an airport or of a backbone IT system, agents (companies or individuals) must form a team having required competences 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—in that case many feasible teams compete for the contract. We investigate rational strategies of the agents (what salary should they ask? with whom should they team up?). We propose concepts to characterize the stability of the winning teams and study their computational complexity.

Introduction

Modern complex projects—ranging from large-scale infrastructure to massive IT systems—rarely rely on a single monolithic entity. Instead, they require the coordination of multiple specialized subcontractors. The fundamental challenge lies in how these markets should be organized to ensure both efficiency and stability.

Traditionally, this is viewed as a centralized problem: individual experts submit salary bids to a client, who then selects the cheapest combination of agents capable of completing the task. However, this paper explores a decentralized alternative where subcontractors coordinate among themselves to form consortiums, bidding for the project as a unified group. This shift introduces complex game-theoretic dynamics regarding how agents should price their services and who they should partner with to avoid being undercut by rival coalitions.

Modeling Stability in Team Formation

The authors model the bidding process as a non-cooperative strategic game. A central assumption is the existence of an algorithmic "oracle" capable of determining if a proposed team is feasible—meaning they possess the necessary skills to finish the project within the specified budget and timeframe.

To evaluate the stability of these teams, the paper utilizes the Strong Nash Equilibrium (SNE), a state where no coalition of agents can deviate to improve their collective payoffs. However, because agents in a decentralized market might be cautious about losing their position entirely if a deviation fails, the authors introduce more nuanced concepts:

  • Explicitly Endangered Teams: Those that can be undercut by a completely different, cheaper team.
  • Implicitly Endangered Teams: Those undercut by a team sharing some members who are offered equal or better pay.
  • Strongly vs. Weakly Winning Teams: A "strongly winning" team is one that cannot be undercut. Because these do not always exist, the authors propose the "weakly winning team"—a team where any coalition attempting to undercut it is itself vulnerable to being undercut.

Computational Complexity and Results

The core contribution of the research is mapping the computational bounds for finding and checking these stable configurations. The complexity often hinges on the time required for the oracle to find the Cheapest Feasible Team (FCFT).

Table 1: Summary of existence and computational complexity for various solution concepts in centralized and decentralized settings.

As shown in the table above, the centralized model is generally more stable and computationally easier to manage. In a centralized market with flat project salaries, a Strong Nash Equilibrium always exists if the project is feasible. In contrast, decentralized markets are more volatile; a strongly winning team might not exist due to endless cycles of undercutting. However, the authors prove that a weakly winning team is guaranteed to exist as long as the project is feasible, providing a reliable fallback for mechanism designers.

The Impact of Compensation Models

The research highlights a stark difference between "project salary" (flat rate) and "hourly salary" (time-based) models. The hourly model is significantly more chaotic. Even in a centralized setting, an SNE might not exist under hourly compensation.

Furthermore, when agents are treated as processors with varying speeds, the scheduling complexity becomes a major hurdle. The authors demonstrate that finding a feasible team in concrete scheduling scenarios is NP-hard even with only two agents. They also show that it is mathematically impossible to approximate both the schedule makespan and the budget within constant factors unless P=NP.

Conclusion and Future Directions

While the paper provides a robust framework for understanding coalitional auctions, several questions remain. The current polynomial-time algorithms assume salaries can be rational numbers; finding efficient algorithms for strictly discrete (integer) salaries is still an open problem.

Future work may involve "Coalitional Farsighted Conservative Stable Sets," where agents only deviate if they are certain that subsequent chain reactions of undercutting will not leave them worse off. Additionally, the authors suggest using directed graph components to model cycles of endangerment, potentially revealing new classes of stable solutions for complex, decentralized labor markets.

Summary updated

Abstract

To successfully complete a complex project, be it a construction of an airport or of a backbone IT system, agents (companies or individuals) must form a team having required competences 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---in that case many feasible teams compete for the contract. We investigate rational strategies of the agents (what salary should they ask? with whom should they team up?). We propose concepts to characterize the stability of the winning teams and study their computational complexity.
BibTeX
@inproceedings{skowron2017people,
  author = {Piotr Skowron and Krzysztof Rzadca and Anwitaman Datta},
  title = {{People are Processors: Coalitional Auctions for Complex Projects}},
  booktitle = {IEEE Intell. Syst},
  year = {2017},
  url = {https://openreview.net/forum?id=Slov4FrwRn2},
}
Figure