Utilitarian Welfare Optimization in the Generalized Vertex Coloring Games: An Implication to Venue Selection in Events Planning

The concept of the self-organized VCG was informally proposed in a behavioural study reported in Kearns et al. (2006), which was motivated by a self-organizing venue assignment problem among the faculty members. With the same aim of resolving conflicts (i.e. achieving some proper coloring), experiments were conducted against different network topologies and with variations to the extent of limits on information sharing among the agents. The conflict-resolving status and time were well monitored and compared across networks with distinguished features. In Chaudhuri et al. (2008), such social interactions within a network was first formulated as a game with binary payoffs, and theoretical results were derived through ingenious combinatorial arguments. It was shown that, even the agents would adopt completely greedy strategies and are allowed to act simultaneously, a proper coloring is attainable when available colors are two more in number than the maximum degree $\Delta$ of the graph, and the procedure ends in $O(\frac{\log n}{\delta})$ rounds with probability $1-\delta$. Almost at the same time, an independent work led by Panagopoulou and Spirakis (2008) studied a similar problem with a slightly different payoff scheme from a more game-theoretic perception. The authors showed that every Nash equilibrium of the corresponding VCG is feasible and locally optimal, and a characterization of the Nash equilibria was provided.

The two pioneering works attracted numerous attention to the field of decentralized coloring game. One branch of work focuses on customized results when the VCG is restricted to certain special graph structures (see, e.g., (Enemark, McCubbins, Paturi and Weller, 2011)). Another popular ramification is induced by the flexible game settings, both on game types ((Pelekis and Schauer, 2013; Carosi, Fioravanti, Gualà and Monaco, 2019)) and payoff features ((Kliemann, Sheykhdarabadi and Srivastav, 2015)) and employed strategies ((Hernández and Blum, 2012)). Of course, constant efforts have also been paid on improving the upper bounds for the convergence rate thus the complexity of the VCG (Bermond, Chaintreau, Ducoffe and Mazauric, 2019) or reduing the color supply (Fryganiotis, Papavassiliou and Pelekis, 2023). The idea of the VCG also shed light on many engineering problem-solvings; see, e.g. (Goonewardena, Akbari, Ajib and Elbiaze, 2014; Marden and Wierman, 2013; Touhiduzzaman, Hahn and Srivastava, 2018).

A Markov chain is a stochastic process that models a sequence of random events in which the probability of each event depends only on the state of the system at the previous event. It has been widely used in graph coloring, which is NP-hard, due to its advantage in handling large-scale search in a systematic and efficient manner. One of the earliest Markov chain algorithms for graph coloring was proposed by Kirkpatrick, Gelatt Jr and Vecchi (1983) where the transition probability depends on the difference in the number of conflicting edges between the two colorings. The algorithm proved to be effective on small to medium-sized graphs had difficulty with larger graphs. In recent years, there have been several other Markov chain algorithms proposed for graph coloring, such as the Genetic Algorithm (Fleurent and Ferland, 1996; Hindi and Yampolskiy, 2012; Marappan and Sethumadhavan, 2013), Ant Colony Optimization (Salari and Eshghi, 2005; Dowsland and Thompson, 2008), and Particle Swarm Optimization (Cui, Qin, Liu, Wang, Zhang and Cao, 2008; Marappan and Sethumadhavan, 2021). Promising results have been shown on a wide range of graph coloring problems.

Markov chains have also been applied for color samplings. Aiming to approximately counting the number of the k-colorings in a graph, Jerrum (1995) converted this counting problem to estimating the mixing time of a Markov Chain. Inspired by the term of Glauber Dynamic in statistical physics, he presented an approach to ramdomly sampling colorings with maximum degree $\Delta$ in $O(n\log n)$ time with at least $2\Delta+1$ colors provided. Vigoda (2000) later proved that it suffices for the number of colors to be only $\frac{11}{6}\Delta$ for the $O(n\log n)$ bound. Further results were developed for some graphs with special features (see, e.g., (Hayes and Vigoda, 2006; Hayes, Vera and Vigoda, 2007)). Recently, Vigoda’s result on general graphs was improved by Chen, Delcourt, Moitra, Perarnau and Postle (2019) who proved that the chains are rapidly mixing in $O(n\log n)$ time when there are at least $(\frac{11}{6}-\epsilon_{0})\Delta$ colors where $\epsilon_{0}$ is a small positive constant, using the linear programming approach.

The Metropolis-Hastings algorithm is a versatile algorithm for solving complex optimization problems that was first introduced in a seminal paper by Metropolis et al. (1953) and further modified by Hastings (1970) who included a correction factor to ensure detailed balance. It relies on constructing a Markov chain that has the desired target distribution as its stationary distribution, from which it generates a sequence of samples. The algorithm has since been adapted for engineering applications emerging in various fields, including but not limited to signal processing (Luengo and Martino, 2013; Vu, Vo and Evans, 2014; Marnissi, Chouzenoux, Benazza-Benyahia and Pesquet, 2020), self-reconfiguration systems (Pickem, Egerstedt and Shamma, 2015), task allocation (Hamza, Toonsi and Shamma, 2021; Moayedikia, Ghaderi and Yeoh, 2020), etc.

A snapshot of the algorithm is as follows: In a finite-state space $S$, denote the target distribution by $\pi(X)$ where $X$ is the variable ot interest. As an initialization one constructs a starting state $x_{0}$ and an irreducible proposal transition matrix $Q(x^{\prime}|x)$ to generate a new state $x^{\prime}$ from $x$. The transition probability is then multiplied by an acceptance rate

and the updated transition probability, namely the target transition probability, is

Note that the target transition probability satisfies the local balanced equation

thus the target distribution o$\pi(X)$ is exactly a stationary distribution of the Markov process induced by $P$. The uniqueness of the stationary distribution is given by irreducibility of the chain.

Let us first introduce the notations and terminologies that are used throughout this paper. Notations of the graph structure and the color collection follow from Section 1, and the maximum degree of the graph $G$ is denoted by $\delta(G)$. We require $m\geq\mathcal{X}(G)$ where $\mathcal{X}(G)$ is the chromatic number of G; i.e. the least number of colors that enables a proper coloring. It is denoted by $V_{j}\rightarrow V_{i}$ if the information of $V_{j}$ can be shared to $V_{i}$, and $V_{i}$’s family is defined as the set $\mathcal{F}_{i}:=\{V_{j}:V_{j}\rightarrow V_{i}\}$. Let $c^{k}\in C$ (k = 1, 2, …, $|C|$) be the coloring realizations. By adding a subscript $i\in\{1,2,\dots,n\}$ we specify the particular color assigned to $V_{i}$; e.g. $c^{k}_{i}$ specifies the assignment under the coloring $c^{k}$. When there is a change in coloring, say from $c^{k}$ to $c^{l}$, let $\Delta u_{i}(c^{k}\rightarrow c^{l}):=u_{i}(c^{l})-u_{i}(c^{k})$ and $\Delta\Phi(c^{k}\rightarrow c^{l}):=\Phi(c^{l})-\Phi(c^{k})$ denote the difference in $V_{i}$’s utility and the welfare respectively under the two colorings. To emphasize on the color choice of a particular agent, we sometimes specify $u_{i}(c)$ as $u_{i}(c_{i},c_{-i})$.

We say an agent is active in round $t$ if he wishes to update his color choice. Starting from any coloring $c(0)\in C$, the game continues in discrete rounds. Let $c_{i}(t)$ denote the color assigned to $V_{i}$ in round $t$ and $\mathcal{A}(t)$ denote the active set containing all active agents in round $t$. In each round, every active agent, driven by either (Feature 1) or (Feature 2), would attempt to update his color from certain available color set (or stategy set) $\mathcal{C}_{i}$ under some policy, while the inactive ones keep their colors unchanged. This induces a discrete-time Markov Chain on the coloring space $C$ with its transition matrix determined by the policy. A formal definition of the Generalized Vertex Coloring Game (G-VCG) is given as follows:

In the following sections, there will be discussions and experiments of G-VCGs on both asynchronous and synchronous conditions. A discrete game is said to be asynchronous if at most one agent is active in each round, while synchrony allows multiple active agents to update in the same round. In this paper, two particular types of synchrony, namely independent synchrony and complete synchrony, will be discussed.

In this part of the section, we make several essential assumptions, most of which are to be assumed thoughout the paper unless mentioned otherwise.

Focusing on maximizing the total utility of the network with little regard to the utility distribution, we now make an additional assumption that the welfare function is utilitarian or weighted utilitarian where the weights are priori information to the agents. In later sections we will see that such welfare formulas would enable individual agents to evaluate their contributions to the total welfare by selecting a new color, even without refering to the entire network.

As mentioned in Section 1, our main concern is whether the optimal solutions of ($\mathsf{WO2}$) coincide with the ones of ($\mathsf{WO1}$). It is straitforward that if $c^{*}_{WO2}$ is a proper coloring, then $c^{*}_{WO1}=c^{*}_{WO2}$; otherwise $c^{*}_{WO1}$ would be a better solution for ($\mathsf{WO2}$). Yet, whether $c^{*}_{WO2}$ is proper highly depends on the abundance of colors provided. We make another assumption on the relationship between the caridinality of the color set and the maximum degree of the graph.

Assumption 2 guarantees $c^{*}_{WO2}$ to be proper because each vertex $V_{i}$ always has a color that is distinguished from the neighborhood; i.e.

To show that Assumption 2 is the weakest to ensure the properness of $C^{*}_{WO2}$ in whatever graph structures, we would like to give a counterexample when cases with $|M|=\delta$ thus $|M|\geq\delta$ may fail.

Moreover, special attention should be given to the step when the active agents modify their color choices. If not well regulated, the game would easily become vulnerable and two typical jeopardies include:

1. (i)

   Small search space: Due to (Feature 1), every agent would incline to top-preferred colors and is loath to adopt other ones. This would severely reduce the search space of the process thus the optimal coloring is often attainable.

2. (ii)

   Deadlock: Due to (Feature 3) and (Feature 1), an agent is not aware that sacrifice would bring “win-win” outcomes for both himself and the neighbors later. This would result in deadlocks in network, especially when the preference systems differ across the neighbors, when imprudent agents pursues temporary self-seeking colors while impairing the neighborhood’s progress.

In reality, one common approach to avoid these emotional behaviors is to involve in randomness (e.g. by lottery). We make an analogical assumption here yet still respect agents’ acceptance or rejection on the new color.

When making a decision, the latest information that an active agent can refer to is the current situations of the family members (which are obtained in the last round); i.e. the active agent $V_{i}$ assumes $c_{-i}(t+1)=c_{-i}(t)$ when deciding whether to accept the offer. The completely greedy policy is defined as follows:

Here is a brief summary on the game procedure:

1. (i)

   Before round 0, an initial coloring $c(0)$ is assigned to the network $G$. Each agent $V_{i}$ calculates his utility by evaluating $c_{i}(0)$ and detect clashes in his family.

2. (ii)

   In round $t\geq 0$, each element of $\mathcal{A}(t)$ pursues a new color by randomly sampling a color $j\in M$. The inactive agents remain their colors in the previous rounds; i.e. $c_{l}(t+1)=c_{l}(t)$ for $V_{l}\notin\mathcal{A}(t)$.

3. (iii)

   Each $V_{k}\in\mathcal{A}(t)$ decides whether to accept $j$ under certain acceptance policy. If $j$ is accepted, $c_{k}(t+1)=j$; otherwise $c_{k}(t+1)=c_{k}(t)$. The round t is finished and the game steps to round $t+1$.

We examine in this subsection whether the convergence of an IP-VCG to its optimal coloring under CGP which is often driven by (Feature 1). As mentioned, it suffices to answer this question: can a proper coloring be achieved in a game with binary utilities (3) under CGP? It is obvious that an active agent with zero utility would accept any color unused by his neighbor to avoid clashes, and those agents with utility one, though can still be active, would never accept any new color because they have already attained their best personal utilities. Under our Assumption 2, it is straightforward that asynchronous IP-VCGs will converge to an optimal coloring in finite rounds since there are always extra colors different from all neighbors’ for each agent to select, and the probability of such a selection is positive. In general, analysis on an arbitrary synchronous G-VCG could be quixotic for tremendous randomness and the optimality may not be guaranteed. However, we observe that the extreme setting of complete synchrony brings peculiar properties which are worth an extra attention. As such, in the rest of the section, we concentrate our arguments on the completely synchronous cases.

We would like to point out that a similar problem was discussed in the seminal work Chaudhuri et al. (2008) which also concerned about the binary utility VCG. The main difference of their setting is that, unlike in Assumption 3 where we assume $\mathcal{C}_{i}=M$, they restricted the available color set for each agent to be the colors currently unused by his neighbors; i.e. $\mathcal{C}_{i}(t)=M\backslash\{c_{j}(t):V_{j}\in\mathcal{N}(V_{i})\}$. Though could be more efficient, their setting suffers from a severely reduced search space because state transfers are often only allowed in one direction, which impairs possible generalizations. Besides, their setting requires a stronger assumption than our Assumption 2 that the number of colors must be at least two more than the maximum degree. Notice that the counterexample they gave on a failure of convergence when $m=\delta(G)+1$, however, can be solved in our setting for better color availability. We place their example here for the sake of completeness and better understanding.

Before stepping further, we first introduce a special type of Markov Chain, namely Absorbing Markov Chain (AMC), which will be our main tool of proving the convergence.

In the context of a 0-1 VCG, which is a simplification of IP-VCGs, one may use a list with binary digits to represent the utility of players after each round. Such utility lists have a length of $n$ with each element representing the utility of a vertex, and there are $2^{n}$ possible outcomes. Additionally, since it is impossible for all but one players to have utility equal to 1, the total number of possible cases is reduced by $n$. Let $S$ denote the utility space consisting of these $2^{n}-n$ utility lists on which a Markov Chain $(X_{t})_{t\in\mathbb{N}}$ can be run. The transition probability reflects the likelihood of a change in utility. The following Lemma 1 states that $(X_{t})_{t\in\mathbb{N}}$ is an AMC.

A classical property of an AMC is that it will be absorbed eventually, which means the convergence to a proper coloring in our case.

Given an optimal convergence of IP-VCGs, we are interested in the time to convergence with complexity measurements. In their setting of $\mathcal{C}_{i}(t)=M\backslash\{c_{j}(t):V_{j}\in\mathcal{N}(V_{i})\}$, Chaudhuri et al. (2008) proposed and proved that the game ends in $O(\log\frac{n}{\epsilon})$ rounds with probability at least $1-\epsilon$ when $m\geq\delta+2$. They took advantage of an important property that any zero-utility agent could earn a utility rise in two consecutive rounds with a probability above some positive constant. It supprisingly proves that this property extends to the completely synchronous 0-1 IP-VCGs thus to all IP-VCGs under CGP. This is given as Theorem 3 below and the proof is an anlogue to Lemma 3 in Chaudhuri et al. (2008) with subtle adjustments.

The constant lower bound, though relatively small, is useful because it provides some deterministic information in a stochastic self-organizing game scenario. More importantly in our discussions, the constant probability for a utility rise in two consecutive rounds sheds light on the behavior of the Markov Chain as defined in Theorem 1, besides the upshot of being absorbed. The following lemma demonstrates respective bounds on the expectation and variance of the number of rounds to convergence.

We are now ready to state the main theorem in this section, in which we show the stochastic boundedness of $T$, the time (i.e. number of steps) to convergence.

It is acknowledged that, despite the mentioned limitations, we still gain parts of our insights from the work led by Marden and Shamma (2012). Specifically, this detour section introduces some preliminary terminologies and results from Young (1993) that will be invoked in the proofs of our later results. We first give the definition of a regular perturbed Markov process (RPMP).

Another important concept we would like to review here is the construction of a resistance tree with some associated stochastic potential.

The above terminologies will play key roles in our later proofs, via a powerful theorem lemma from Young (1993).

We start from the easiest setting where agents become active and update their colors one by one. A Markov chain $(Y_{t})_{t\in\mathbb{N}}$ is established on the coloring space $C$ with each coloring as a state. The elements of the transition matrix correspond to the probability of a direct transition between the two states. Our aim is to adjust the transition probabilities of the chain (i.e. the acceptance probability of an active agent) so that stochastically stable states only contain $c^{*}_{WO2}$’s.

We would like to explain on some possible concerns regarding the policy before stepping towards the details in the MH-policy. In the policy, one may question that (Info-Type2) seems useless for individual decision-making. Indeed, without a loss of generality, we would restrict our consideration only on (Info-Type1) (i.e. assume (Info-Type2) is not inaccessible) for the sake of simplicity in the rest of this section, which equalizes the neighborhood $\mathcal{N}(V_{i})$ with the family $\mathcal{F}_{i}$. However, we are to show in Section 6 on why (Info-Type2) is important for some special purposes of the G-VCGs and how it can be tractably integrated in our formulations.

The proposed MH-policy is now presented. In order to maximize the objective value in $\mathsf{WO2}$, as in the Metropolis-Hasting algorithm, we wish the acceptance probability for each active agent given the selected color $c_{new}$ to be

to satisfy the local blanced equation for the stationary distribution $\pi$, where

is a Boltzmann distribution (McQuarrie, 2000) and $\tau$ is some temperature parameter. Here we omit the terms of the proposal probability because all proposal probabilities equal in a randomized selection. Notice that, as one decreases the temperature $\tau$, the target distribution only puts weights on the state(s) where the social welfare $\Phi(\cdot)$ is maximized.

The welfare difference in the acceptance ratio (4) cannot be directly reflected from individual’s utility difference as a modification on an agent’s choice would likely affect his neighbors’ utilities as well. Yet, we notice that, a clever way for an active agent $V_{i}$ to keep aware of the total difference in the entire network is to monitor the imminent local utility difference across his family $\mathcal{F}_{i}$ before he accepts or rejects. This is because an agent choice can affect the utility of nobody other than his neighbors $V_{j}\in\mathcal{N}(V_{i})$, and we have unified $\mathcal{F}_{i}$ and $\mathcal{N}(V_{i})$ to be equivalent. Formally, when $V_{i}$ is the unique active agent in the game, it holds that

where $c^{k}=(c_{i}(t),c_{-i}(t))$ and $c^{l}=(c_{new},c_{-i}(t))$, and the term on the righth-and side is defined as

Using the terminology in a foundational work Monderer and Shapley (1996), there exists a potential relationship between $\Phi(\cdot)$ and $U_{\mathcal{F}_{i}\cup\{V_{i}\}}(\cdot)$. The procedure of realizing the MH-policy is summarized in the pseudo-code Algorithm 1 in the asynchronous version.

Before moving on to prove the optimality of Algorithm 1, we would like to demonstrate why the MH-policy can be appealing to agents; in other words, it respects the human nature of (Feature 1) and (Feature 3). This is because when updating under the MH-policy:

1. (i)

   An active agent $V_{i}$ will accept $c_{new}$ whenever his own utility $u_{i}(c_{new},c_{-i}(t))$ increases: if $u_{i}(c_{i}(t),c_{-i}(t))=0$ and $u_{i}(c_{new},c_{-i}(t))>0$ then $u_{i}(c_{new},c_{-i}(t))-u_{i}(c_{i}(t),c_{-i}(t))<\Delta U_{\mathcal{F}_{i}\cup\{V_{i}\}}(c^{k}\rightarrow c^{l})$ since $V_{i}$’s zero-utility neighbors may also have the clash resolved; else, if $u_{i}(c_{i}(t),c_{-i}(t))>0$ and $u_{i}(c_{new},c_{-i}(t))>u_{i}(c_{i}(t),c_{-i}(t))$, then $u_{i}(c_{new},c_{-i}(t))-u_{i}(c_{i}(t),c_{-i}(t))=\Delta U_{\mathcal{F}_{i}\cup\{V_{i}\}}(c^{k}\rightarrow c^{l})$ as the neighbors’ utilities are unaffected. In both cases, $e^{\Delta U_{\mathcal{F}_{i}\cup\{V_{i}\}}(c^{k}\rightarrow c^{l})}>1$.

2. (ii)

   An active agent $V_{i}$ is not obliged to give up on his old color whenever his own utility $u_{i}(c_{new},c_{-i}(t))$ decreases: if $u_{i}(c_{i}(t),c_{-i}(t))>0$ and $u_{i}(c_{new},c_{-i}(t))=0$ then $u_{i}(c_{new},c_{-i}(t))-u_{i}(c_{i}(t),c_{-i}(t))>\Delta U_{\mathcal{F}_{i}\cup\{V_{i}\}}(c^{k}\rightarrow c^{l})$ since $c_{new}$ induces color clashes between $V_{i}$ and some neighbors whose utility would immediately drop to zero; else, if $u_{i}(c_{i}(t),c_{-i}(t))>0$ and $u_{i}(c_{new},c_{-i}(t))>0$, then $u_{i}(c_{new},c_{-i}(t))-u_{i}(c_{i}(t),c_{-i}(t))=\Delta U_{\mathcal{F}_{i}\cup\{V_{i}\}}(c^{k}\rightarrow c^{l})$ as the neighbors’ utilities are unaffected. In both cases, $e^{\Delta U_{\mathcal{F}_{i}\cup\{V_{i}\}}(c^{k}\rightarrow c^{l})}<1$.

3. (iii)

   The more $V_{i}$’s utility would drop, the more likely he would keep his old color. The arguments are the same as (ii) along with the fact that the worst utility is zero.

We now step to prove that the MH-policy indeed leads to $c_{WO2}^{*}$. To do so we first state that the Markov Chain induced by the MH-policy is in fact an RPMP.

We are now able to invoke properties of RPMP to investigate on the support of the stationary distribution $\pi(\cdot)$, i.e. the set of stochastically stable states, which only contains states leading to the global optimal welfare rather than a local optimum. Besides, it turns out that we can establish relationship between the resistances and the final welfares. Equipped with these tools, we substantiate that the MH-policy indeed leads the game to $c^{*}_{WO2}$.