Detecting service provider alliances on the choreography enactment pricing game

Johanne Cohen, Daniel Cordeiro, Loubna EchabbiarXiv 2016 · arXiv

Introduction

In the evolving landscape of cloud computing and Service-Oriented Architecture (SOA), system management is shifting from traditional orchestration to decentralized choreography. While orchestration relies on a central "conductor" to manage service interactions, choreography facilitates peer-to-peer interactions among independent providers. This shift enhances scalability and robustness but introduces significant economic challenges. Without a central authority to regulate pricing, service providers may form alliances—essentially cartels—to control market shares or limit competition.

This paper addresses the stability of these alliances by modeling the scenario as a cooperative game. The authors investigate the conditions under which providers remain within an alliance and propose a method for distributing collaborative "savings" to ensure no participant has an incentive to defect.

The Choreography Enactment Pricing Game

The authors define the Choreography Enactment Pricing Game as a cooperative game with transferable utility. In this model, multiple organizations (service providers) collaborate to execute complex applications. The central question is how to distribute the total profit or cost savings among these organizations in a way that maintains the group's integrity.

The Bargaining Set vs. The Core

In game theory, the "Core" represents a set of profit distributions where no sub-group can do better by leaving the alliance. However, in many practical scenarios, the Core is empty, meaning no perfectly stable distribution exists. To overcome this, the authors utilize the Bargaining Set. This concept defines stability through a system of "objections" and "counter-objections": a distribution of profits is considered stable if every threat by a player to leave the group can be met with a credible counter-offer from the remaining members.

Methodology and Assumptions

The research relies on the Monotonicity Assumption, which posits that adding more resources (such as virtual machines) to a task will never increase the total cost. This assumption holds true for common operational objectives, including minimizing energy consumption or reducing average job completion times.

Algorithm 1: Coalition Detection

The centerpiece of the study is a novel, polynomial-time algorithm designed to detect stable coalitions. The algorithm processes the cost functions of various organizations to determine if a stable alliance is mathematically feasible. If stability is possible, the algorithm outputs a specific "imputation"—a payment vector that dictates exactly how much each organization should be paid to prevent them from breaking away.

Key Insights

The "Free Rider" Rule

A critical finding of the paper is the "Free Rider" rule: if an organization’s participation in a coalition does not contribute to the total savings of the group, that organization must receive a payoff of zero in any stable arrangement. This ensures that profit distribution is tied strictly to value creation.

Uniqueness and Fairness

While many cooperative games suffer from having either infinite stable points or none at all, the authors demonstrate that for this specific pricing game, a stable distribution of profits—if it exists—is often unique. This provides a clear, unambiguous roadmap for service providers to reach an agreement. Furthermore, the proposed algorithm bridges the gap between "fairness" (distribution based on contribution) and "stability" (distribution that prevents defection).

Computational Efficiency

Detecting stable coalitions in general cooperative games is typically NP-hard, making it impractical for large-scale systems. By leveraging the specific properties of service scheduling and the monotonicity property, the authors reduced this complexity to polynomial time. This makes the detection of alliances and the calculation of stable payments viable for real-world, decentralized cloud environments.

Results and Mathematical Proofs

The validity of the model is established through formal mathematical proofs rather than empirical datasets. Key results include:

  • Theorem 6: Provides the definitive formula for calculating the payment ($x_j$) for each organization within an alliance.
  • Corollary 7: Establishes the lower bound for stability, proving that an alliance remains stable only if the total price users are willing to pay meets or exceeds the optimal cost achievable by the alliance.
  • Complexity Verification: The authors proved that if the underlying scheduling problem can be solved in polynomial time, the associated pricing game can also be resolved in polynomial time.

Limitations and Future Directions

Despite its contributions, the model has limitations. It currently struggles with non-monotone costs, such as makespan (the total duration from start to finish), where adding resources does not always lead to a predictable decrease in cost. Additionally, the model provides a static "snapshot" of a game, whereas real-world service environments are dynamic, with jobs and providers constantly entering and exiting the system.

Future research may explore "truthful mechanisms" in algorithmic mechanism design, creating systems where providers are naturally incentivized to report their true operational costs rather than inflating them to secure a larger share of the alliance's profits.

Summary updated

Abstract

We present the choreography enactment pricing game, a cooperative game-theoretic model for the study of scheduling of jobs using competitor service providers. A choreography (a peer-to-peer service composition model) needs a set of services to fulfill its jobs requirements. Users must choose, for each requirement, which service providers will be used to enact the choreography at lowest cost. Due to the lack of centralization, vendors can form alliances to control the market. We show a novel algorithm capable of detecting alliances among service providers, based on our study of the bargaining set of this game.
BibTeX
@misc{cohen2016detecting,
  author = {Johanne Cohen and Daniel Cordeiro and Loubna Echabbi},
  title = {{Detecting service provider alliances on the choreography enactment pricing game}},
  year = {2016},
  eprint = {1606.07111},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1606.07111},
}
Figure