Deviate or Not: Learning Coalition Structures
with Multiple-bit Observations in Games

Coalitions and collusive behavior are common in the real world. In auction systems, bidders may form coalitions to coordinate bids and exploit mechanisms for better odds of winning [1]. On ridesharing platforms like Uber and Lyft, some drivers might disconnect simultaneously to create an artificial shortage, triggering a price surge they can later benefit from [2, 3, 4]. While illegal collusion, like price fixing, is regulated by agencies such as the SEC in the United States, it remains challenging to eliminate, as seen in scandals like the LIBOR Scandal [5]. As AI systems become more advanced and widely used in domains like stock trading and autonomous driving, regulating these AI agents presents a growing challenge as seen by regulators and researchers [6, 7].

In response to such concerns, the problem of coalition structure learning (CSL) [8] has recently gained attention. In CSL, a platform aims to figure out which agents are in a coalition by designing a small number of games for the agents to play and make observations on the outcomes of these games. Notably, more than one coalition may exist simultaneously. In practice, the platform could represent a regulator, like an auction or ridesharing platform, aiming to detect collusion or design better mechanisms.

However, the existing study on CSL relies on a strong assumption that the platform can only observe whether a specified strategy profile is a Nash equilibrium (NE) in each round. With this single-bit observation oracle and other assumptions, optimal algorithms require $\Theta(n\log n)$ rounds of games to learn the coalition structure, where $n$ is the number of agents. Such an observation oracle is too restrictive for two reasons. First, for real-world systems with a large number of agents, $\Theta(n\log n)$ rounds is still prohibitively large. Second, it may be possible for the platform to know which agents would deviate from the specified strategy profile. For example, a ridesharing platform could observe which drivers disconnect from the platform given a pricing scheme.

In this paper, we aim to address this limitation and consider a multiple-bit observation oracle: the platform can observe an $n$-dimensional binary vector in each round, where the $i$-th bit indicates whether or not agent $i$ would like to deviate from the specified strategy profile. This oracle allows the platform to gain $n$ bits of information in each round, which is significantly more informative than the single-bit observation oracle, allowing the platform to learn the coalition structure with much fewer rounds. However, from a technical perspective, switching from the single-bit observation oracle to the multiple-bit observation oracle fundamentally changes the problem. With the single-bit observation, the platform can choose the game to use to get the next bit of observation, which means it is easy to ensure that each bit of observation brings in information. However, with multi-bit observation, the platform will get $n$-bit information in a batch, and it is often inevitable that these $n$-bits contain repetitive or highly correlated information. Therefore, the key challenge in algorithm design is how to design the games so that the $n$ bits of observation are more de-correlated and contain more information.

Consider a set $N=\{1,2,\dots,n\}$ of $n$ strategic agents. A coalition $S\subseteq N$ is a nonempty subset of the agents, in which the agents can coordinate with each other in games. We assume there is a coalition structure $\mathcal{S}^{*}=\{{S_{1}}^{*},{S_{2}}^{*},\dots,{S_{m}}^{*}\}$ among these agents, which is a set partition of $N$, and each agent in $N$ belongs to exactly one of these mutually disjoint coalitions. We use $[i]_{\mathcal{S}^{*}}$ to denote the coalition containing agent $i$ under $\mathcal{S}^{*}$. $\mathcal{S}^{*}$ is not public information, but agents in each coalition know the other agents in the same coalition. In the Coalition Structure Learning (CSL) problem, our goal is to actively design a sequence of games for the agents to play, such that observations in these games can be used to learn the underlying coalition structure $\mathcal{S}^{*}$. Specifically, we interact with the agents in a sequence of rounds. Each round, we design a game $\mathcal{G}$ along with a strategy profile $\Sigma=(\sigma_{1},\sigma_{2},\dots,\sigma_{n})$ in $\mathcal{G}$ for the agents, and we make an observation $\mathcal{O}(\mathcal{G},\Sigma)$ about the strategy profile $\Sigma$ in $\mathcal{G}$. The task is to learn the underlying coalition structure $\mathcal{S}^{*}$.

We show in this section an algorithm that solves Multiple-bit CSL with normal-form games in $\log_{2}n+2$ rounds. Note that the number of rounds matches the lower bound in Theorem 2.1 up to $O(\log\log n)$. The main idea of the algorithm is to use binary search to find another agent in the same coalition for each agent simultaneously. We start by defining game-strategy pairs and a special pair that we call the directed prisoner’s dilemma, which we use in the algorithm.

Given the construction of directed prisoner’s dilemma, we have the following observation.

Lemma 3.1 shows that we can use directed prisoner’s dilemmas to determine whether two agents are in the same coalition under $\mathcal{S}^{*}$. However, querying a single directed prisoner’s dilemma is not efficient as we only get $1$ bit of information. To utilize the information from the observation oracle more efficiently, we will need to consider the product of multiple directed prisoner’s dilemmas.

A graphical interpretation of Lemma 3.2 is as follows. When we query the game-strategy pair $\prod_{x=1}^{k}\mathcal{P}(i_{x},j_{x})$, consider a directed graph where each vertex represents an agent and each edge $(j_{x},i_{x})$, $x\in\{1,2,\dots,k\}$ represents $\mathcal{P}(i_{x},j_{x})$. The observation tells us for each vertex if any of its outgoing neighbors in this constructed graph is in the same coalition. With Lemma 3.2, we are ready for our Algorithm 1 for Multiple-bit CSL with normal-form games.

Intuitively, given an agent $j$, if we want to find another agent $i\ (i<j)$ in the same coalition with $j$, we can query a game-strategy pair $\prod_{k\in T_{j}}\mathcal{P}(k,j)$ where $T_{j}=\{1,2,\ldots,j-1\}$ initially. According to Lemma 3.2, we will know whether there is such an agent in $T_{j}$ from the $j$-th bit of the observation. If there is such an agent, we can then bisect the set $T_{j}$ and apply binary search to find this agent. Moreover, this binary search can be done simultaneously for different agents. For example, given two agents $j$ and $j^{\prime}$, we can construct the game-strategy pairs $\prod_{k\in T_{j}}\mathcal{P}(k,j)\times\prod_{k\in T_{j^{\prime}}}\mathcal{P}(k,j^{\prime})$ and apply binary search at the same time on $T_{j}$ and $T_{j^{\prime}}$ using the $j$-th and $j^{\prime}$-th bits of the observation. This is because the $j$-th bit in the observation vector only depends on whether there exists another agent in $T_{j}$ in the same coalition with agent $j$, and the same argument applies to agent $j^{\prime}$.

Algorithm 1 leverages this intuition and works in two stages. In the first stage (Lines 1 to 7), we try to find for each agent $j$ the smallest index of the agents in $[j]_{\mathcal{S}^{*}}$. To do this, we first query $\prod_{i\in N,j\in N,i<j}\mathcal{P}(i,j)$ (Line 1). In this game, agent $j$ has the incentive to deviate only when another agent $i$ with a smaller index than $j$ is in the same coalition with $j$. Therefore, using the $j$-th bit from the observation, we can determine whether agent $j$ is the agent with the smallest index in $[j]_{\mathcal{S}^{*}}$ (Line 2). For agents who are not, we then use binary search to locate the smallest indexed agents in their coalitions simultaneously (Lines 3 to 6). In the second stage (Lines 8 to 11), it merges each coalition in $\mathcal{S}^{*}$ together according to the result of the first stage.

We provide an example of Algorithm 1 in Fig. 2.

We consider in this section the case of Multiple-bit CSL with auctions. The auction format we consider is theoretically well-studied second-price auctions with personalized reserves [30], which is widely used in practice. We first formally define this format.

Our algorithm for the Multiple-bit CSL problem with auctions works in $(1+\log_{2}n)(1+c)+1$ rounds, where $c$ is size of the largest coalition in $\mathcal{S}^{*}$. To introduce the algorithm, we first define the game-strategy pairs that we will use in the algorithm, the auction game gadgets, where we will specify the valuation and reserve prices of every agents in each partition bucket.

Note that in the above auction game gadgets, we do not require each agent to know all the other agents’ valuations so that the valuation of each agent is still private across strategic agents. Only agents in the same coalition know each other’s true valuation.

The auction gadgets are important building blocks for our algorithm that works in $(1+\log_{2}n)(1+c)+1$ rounds. To help demonstrate how they can be used to solve Multiple-bit CSL, we present a simpler algorithm that works in $n-1$ rounds using the auction gadgets below.

To provide some intuitions, consider an agent $i\in N$. If we want to find another agent in the same coalition as $i$, we can query the auction gadget $\mathcal{A}(\{i\},N\setminus\{i\},\varnothing)$. According to Lemma 4.1, if the observation $\mathbf{O}$ has $O_{j}=\mathrm{True}$ for some $j\in N\setminus\{i\}$, then $i$ and $j$ are in the same coalition under $\mathcal{S}^{*}$. Otherwise, $i$ is in a coalition by itself. Then, suppose we have found an agent $j$ in $i$’s coalition, and we would like to find a different agent in that coalition. We can query the auction gadget $\mathcal{A}(\{i\},N\setminus\{i,j\},\{j\})$. By moving agent $j$ to the set $Z$, we ensure that $j$ does not have the incentive to deviate, and either another agent in the same coalition as $i$ will have $O_{k}=\mathrm{True}$ for some $k\in N\setminus\{i,j\}$, or we can conclude that $i$ and $j$ are in a coalition by themselves. We can then repeat this process until we have found all the agents in the same coalition as $i$. After that, we can move $i$ to the set $Z$ and proceed with the next agent in $N$. In this way, we can recover the coalition structure $\mathcal{S}^{*}$. Moreover, since each time we query an auction gadget, we move one agent to set $Z$, and the algorithm terminates when $|Z|=n-1$, it uses $n-1$ queries in total.

We defer the proof to Appendix C. Other than the auction gadgets, we will also use another game-strategy pair in the algorithm. We prove the following lemma about the observations obtained by querying this game-strategy pair.

Then, we are ready to present our algorithm that works in $(1+\log_{2}n)(1+c)+1$ rounds for Multiple-bit CSL with auctions. The algorithm is shown in Algorithm 3.

The algorithm starts by querying the game-strategy pair $((N,\mathbf{v}=\mathbf{1},\mathbf{r}=\mathbf{0}),\Sigma=\mathbf{0})$ (Line 1). Using the obtained observation, by Lemma 4.2, the algorithm identifies exactly one agent in each coalition, groups them into set $T_{x}$ and the rest of the agents into set $T_{y}$ (Lines 2). Essentially, set $T_{x}$ contains a set of agents who are definitely not in the same coalition with each other. Furthermore, for each agent $i$ in $T_{y}$, there is exactly one “teammate” of $i$ in $T_{x}$. We denote the index of this agent as $\alpha(i)$.

An important idea behind Algorithm 3 is bitwise search, i.e., to determine each binary bit of $\alpha(i)$ separately. To do this, for each $b\in\{0,1,\dots,\lfloor\log_{2}n\rfloor\}$, the algorithm picks the set of agents in $T_{x}$ such that the $b$-th lowest binary bits of their index are $1$ as $X$ (Line 4), and tries to tell which agents in $T_{y}$ are in the same coalition as some agent in $X$ by querying auction gadgets. Intuitively, if we let $Y=T_{y},Z=N\setminus(X\cup Y)$ and query $\mathcal{A}(X,Y,Z)$, by Lemma 4.1, for each coalition that contains an agent in $X$, one of its members in $Y$ will decide to deviate. Thus, we can move these agents to $Z$ like how we did in Algorithm 2, until no agents in $Y$ decide to deviate. The remaining agents in $Y$ are then the agents that are not in the same coalition as any agent in $X$. The algorithm leverages this idea to determine each binary bit of $\alpha(i)$ separately, and stores the results in $O^{(b)}_{i}$ (Lines 5 to 12). Note that for each $b$, the algorithm uses at most $1+c$ queries, where $c$ is the size of the largest coalition in $\mathcal{S}^{*}$. We illustrate the execution of the bitwise search with an example in Fig. 3.

Finally, the algorithm recovers $\alpha(i)$ for each agent $i$ in $T_{y}$ by summing up the values of the binary bits in $O^{(b)}_{i}$ (Line 15), and merges $i$ with $\alpha(i)$ accordingly (Line 16).

In this paper, we study the Coalition Structure Learning (CSL) problem under the multiple-bit observation oracle. We consider various settings of the type of games that the algorithm may design, including normal-form games, congestion games, graphical games, and auctions. In each of the settings, we present an algorithm that learns the coalition structure with a sublinear number of rounds. We also complement our algorithmic results with lower bounds on the number of rounds required to learn the coalition structure, demonstrating their optimality in most of the settings. Compared to the existing work, our results significantly reduce the number of rounds required to learn the coalition structure, and greatly improve the potential applicability of the CSL problem in real-world systems. Regarding CSL, there are various different settings for future work that are not covered by this paper. It would be interesting to consider the CSL problem (i) when the underlying coalition structure is dynamic, (ii) when the agents are aware of the algorithm and respond strategically, (iii) when the algorithm can only observe a subset of the agents in each round, and (iv) when the observations are noisy or the agents are boundedly rational.

This work was supported in part by NSF grant IIS-2046640 (CAREER) and NSF IIS-2200410.