People are processors: coalitional auctions for complex projects

Piotr Skowron, Krzysztof Rzadca, Anwitaman Datta

Here is a summary of the paper:

TL;DR

This paper explores the game theory and computational complexity behind hiring teams of subcontractors for complex projects. The authors compare centralized markets (where a client picks individual bidders) with decentralized markets (where agents form consortiums to bid) under both project-based and hourly compensation. They introduce new stability concepts like "weakly winning teams" to guarantee stable consortiums and map the computational bounds of finding these optimal teams.

What Problem Does This Paper Address?

Modern complex projects—like constructing a building or developing a massive IT system—require hiring multiple specialized subcontractors rather than a single monolithic company. But how should this market be organized?

The standard "hiring a team" problem assumes a centralized setting: individual experts submit their required salaries to a client, who then pieces together the cheapest capable team. This paper introduces a decentralized alternative where subcontractors coordinate among themselves to form consortiums and bid for the project as a unified group.

Furthermore, the authors examine two different compensation models: "project salary" (a flat rate for the job) and "hourly salary" (paid for time spent working). The core challenge is determining the rational strategies for these agents (e.g., who to team up with and what to charge) and defining what makes a winning team "stable" against groups of agents who might secretly collude to undercut them.

Methods

The authors model the bidding process as a non-cooperative strategic game. They assume access to an algorithmic "oracle" that can determine if a proposed team is feasible (i.e., has the skills to finish the project on time and under budget).

To evaluate stability, they use concepts from game theory, specifically the Strong Nash Equilibrium (SNE)—a state where no coalition of agents can deviate to strictly improve their payoffs. Because agents might be cautious about losing their spot entirely if a deviation fails, the authors introduce a stricter concept: the Rigorously Strong Nash Equilibrium (RSNE).

They define teams as being "explicitly endangered" (undercut by a completely different team) or "implicitly endangered" (undercut by a team that shares some members who are offered equal or better pay). Based on these endangerment types, they formalize "strongly winning" and "weakly winning" teams, reducing the problem of finding them to the algorithmic problem of finding the Cheapest Feasible Team (FCFT).

Datasets

Not discussed in the paper. This is a theoretical algorithmic game theory paper; no empirical datasets or benchmarks were used.

Key Insights and Ideas

  • Centralized vs. Decentralized Stability: In a centralized market with flat project salaries, a stable outcome (an SNE) always exists if a feasible team exists. However, in a decentralized market, a "strongly winning team" might not exist at all because agents can get trapped in an endless cycle of undercutting each other.
  • The "Weakly Winning" Compromise: Because strongly winning teams aren't guaranteed, the authors propose a "weakly winning team" concept. A team is weakly winning if any coalition that tries to undercut it is itself vulnerable to being undercut. The authors prove that a weakly winning team always exists as long as the project is feasible.
  • Hourly Pay is Chaotic: The hourly salary model is inherently less stable than the project salary model. In the hourly model, even in the centralized setting, a Strong Nash Equilibrium might not exist.
  • Mechanism Design Fixes: If a client uses a first-price auction (gradually decreasing the asking price) or dynamically adjusts the budget using a binary search, they can force the market to yield a strongly winning team.

Key Results

  • Centralized Model: Finding a Strong Nash Equilibrium (assuming salaries can be rational numbers) can be solved in $O(n^3 \log(nv) \cdot \text{FCFT})$ time, where $n$ is the number of agents, $v$ is the budget, and FCFT is the time it takes the oracle to find the cheapest feasible team.
  • Decentralized Model: Checking if a team is rigorously strongly winning takes $O(n^2 \cdot \text{FCFT})$ time. Finding a weakly winning team takes $O(n^5 \log(nv) \cdot \text{FCFT})$ time.
  • Scheduling Complexity: In a concrete scheduling scenario where agents are treated as processors with varying speeds (Appendix C), finding a feasible team is NP-hard even for just 2 agents. Furthermore, it is mathematically impossible to approximate both the schedule makespan and the budget within any constant factors $\alpha$ and $\beta$ (unless P=NP).

Limitations and Future Work

  • Discrete Salaries: The polynomial-time algorithms for finding Strong Nash Equilibria and weakly winning teams rely on the assumption that salaries can be rational numbers. Finding an efficient algorithm for strictly discrete (integer) salaries remains an open question.
  • Hourly Salary Intractability: The hourly salary model lacks guaranteed stable outcomes, making it difficult to apply these specific equilibrium concepts in practice without further constraints.
  • Future Directions: The authors suggest exploring "Coalitional Farsighted Conservative Stable Sets"—a concept where agents only deviate if they are sure that all subsequent chain reactions of undercutting will still leave them better off. They also propose using directed graph components to model the cycles of implicit and explicit endangerment to find new sets of stable solutions.

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 (a coalition) having required competences and resources. A team can be formed either by the client 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 employment contract. In these models, we investigate rational strategies of the agents (what salary should they ask? with whom should they team up?) under different organizations of the market. We propose concepts allowing to characterize the stability of the winning teams. We show that there may be no (rigorously) strongly winning coalition, but the weakly winning and the auction-winning coalitions are guaranteed to exist. In a general setting, with an oracle that decides whether a coalition is feasible, we show how to find the winning coalitions with a polynomial number of calls to the oracle. We also determine the complexity of the problem in a special case in which a project is a set of independent tasks. Each task must be processed by a single agent, but processing speeds differ between agents and tasks.
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},
}

Loading related content...

Figure