Search

This paper investigates the potential benefits of cooperation in scenarios where finitely many agents compete for shared resources, leading to congestion and thereby reduced rewards. By appropriate coordination the members of the cooperating group (a.k.a., coalition) can minimize the congestion losses due to inmates, while efficiently facing the competition from outsiders (coalitions indulge in a non-cooperative congestion game). The quest in this paper is to identify the stable partition of coalitions that are not challenged by a new coalition. In contrast to the traditional cooperative games, the worth of a coalition in our game also depends upon the arrangement of the opponents. Every arrangement leads to a partition and a corresponding congestion game; the resultant Nash equilibria (NEs) dictate the `worth'. The analysis is further complicated due to the presence of multiple NEs for each such game., Comment: 8 pages, 2 figures, Accepted in CDC 2024

Coalition Logic is a central logic in logical research on strategic reasoning. In a recent paper, Li and Ju argued that generally, models of Coalition Logic, concurrent game models, have three too strong assumptions: seriality, independence of agents, and determinism. They presented a Minimal Coalition Logic based on general concurrent game models, which do not have the three assumptions. However, when constructing coalition logics about strategic reasoning in special kinds of situations, we may want to keep some of the assumptions. Thus, studying coalition logics with some of these assumptions makes good sense. In this paper, we show the completeness of these coalition logics by a uniform approach.

\noindent A perfect dominating set in a graph $G=(V,E)$ is a subset $S \subseteq V$ such that each vertex in $V \setminus S$ has exactly one neighbor in $S$. A perfect coalition in $G$ consists of two disjoint sets of vertices $V_i$ and $V_j$ such that i) neither $V_i$ nor $V_j$ is a dominating set, ii) each vertex in $V(G) \setminus V_i$ has at most one neighbor in $V_i$ and each vertex in $V(G) \setminus V_j$ has at most one neighbor in $V_j$, and iii) $V_i \cup V_j$ is a perfect dominating set. A perfect coalition partition (abbreviated $prc$-partition) in a graph $G$ is a vertex partition $\pi= \lbrace V_1,V_2,\dots ,V_k \rbrace$ such that for each set $V_i$ of $\pi$ either $V_i$ is a singleton dominating set, or there exists a set $V_j \in \pi$ that forms a perfect coalition with $V_i$. In this paper, we initiate the study of perfect coalition partitions in graphs. We obtain a bound on the number of perfect coalitions involving each member of a perfect coalition partition, in terms of maximum degree. The perfect coalition of some special graphs are investigated. The graph $G$ with $\delta(G)=1$, the triangle-free graphs $G$ with prefect coalition number of order of $G$ and the trees $T$ with prefect coalition number in $\{n,n-1,n-2\}$ where $n=|V(T)|$ are characterized., Comment: 18 pages

Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions.

The Global Business Coalition for Education (GBC-Education) was founded to bring the business community together to end the global education crisis. GBC-Education seeks to increase investments in education from the private sector. In 2019, GBC-Education began developing a suite of resources and services to support partners in its network in making more-strategic investments in education that are aligned with their goals for corporate social responsibility and their environmental, social, and governance strategy. This report describes part of GBC-Education's work with four member companies: Schneider Electric, HP Inc., SAP, and Ancestry.

We propose Tyche, a family of protocols for performing practically (as well as asymptotically) efficient multiparty lotteries, resistant against aborts and majority coalitions. Our protocols are based on a commit-and-reveal approach, requiring only a collision-resistant hash function. All our protocols use a blockchain as a public bulletin board and for buy-in collection and payout settlement. Importantly though, they do not rely on it or any other third party for providing randomness. Also, participants are not required to post any collateral beyond their buy-in. Any honest participant can eventually settle the lottery, and dishonest behavior never reduces the winning probability of any honest participant. Further, we adapt all three protocols into anonymous lotteries, where (under certain conditions) the winner is unlinkable to any particular participant. We show that our protocols are secure, fair, and some preserve the participants' privacy. Finally, we evaluate the performance of our protocols, particularly in terms of transaction fees, by implementing them on the Sui blockchain. There we see that per user transaction fees are reasonably low and our protocols could potentially support millions of participants.

Horizontal collaboration between operators can save traffic operation costs, a concept that has been particularly validated in the logistics field. Due to the increasing transportation demand and the introduction of charging times for electric vehicles, there is growing pressure on airport ground support services. This study introduces the concept of coalition to airport ground support services. Unlike most studies on horizontal collaboration, the scheduling for airport ground support services needs to particularly consider punctuality issues. In this study, we separately establish electric vehicle scheduling models for operator-separate and operator-cooperated modes and design an algorithm based on the concept of the Adaptive Large Neighborhood Search algorithm, aiming to obtain the electric vehicle scheduling plan with minimum cost and delay time. Furthermore, the study proposes a cost allocation method that considers the degree of sharing among operators to ensure the feasibility of coalition. Finally, we conducted numerical experiments based on actual airport operation data. The experiments verified the effectiveness of the algorithm and the cost allocation method. Compared to solvers, our algorithm can obtain feasible solutions in a shorter time while ensuring that the objective function gap is within 2%. Additionally, the improved cost allocation method is fairer compared to the traditional Shapley method. Numerical experiments also show that coalition can save 15-25% of airport operating costs and 26-39% of delay time, with savings varying based on the sharing parameters. Through quantitative analysis such as sensitivity analysis, the study provides insights into the variation patterns of overall and individual shared utilities and offers suggestions and decision-making mechanisms for the configuration and operation of airport ground operators.

Coalition formation over graphs is a well studied class of games whose players are vertices and feasible coalitions must be connected subgraphs. In this setting, the existence and computation of equilibria, under various notions of stability, has attracted a lot of attention. However, the natural process by which players, starting from any feasible state, strive to reach an equilibrium after a series of unilateral improving deviations, has been less studied. We investigate the convergence of dynamics towards individually stable outcomes under the following perspective: what are the most general classes of preferences and graph topologies guaranteeing convergence? To this aim, on the one hand, we cover a hierarchy of preferences, ranging from the most general to a subcase of additively separable preferences, including individually rational and monotone cases. On the other hand, given that convergence may fail in graphs admitting a cycle even in our most restrictive preference class, we analyze acyclic graph topologies such as trees, paths, and stars.

The increasing number of Low Earth Orbit (LEO) satellites, driven by lower manufacturing and launch costs, is proving invaluable for Earth observation missions and low-latency internet connectivity. However, as the number of satellites increases, the number of communication links to maintain also rises, making the management of this vast network increasingly challenging and highlighting the need for clustering satellites into efficient groups as a promising solution. This paper formulates the clustering of LEO satellites as a coalition structure generation (CSG) problem and leverages quantum annealing to solve it. We represent the satellite network as a graph and obtain the optimal partitions using a hybrid quantum-classical algorithm called GCS-Q. The algorithm follows a top-down approach by iteratively splitting the graph at each step using a quadratic unconstrained binary optimization (QUBO) formulation. To evaluate our approach, we utilize real-world three-line element set (TLE/3LE) data for Starlink satellites from Celestrak. Our experiments, conducted using the D-Wave Advantage annealer and the state-of-the-art solver Gurobi, demonstrate that the quantum annealer significantly outperforms classical methods in terms of runtime while maintaining the solution quality. The performance achieved with quantum annealers surpasses the capabilities of classical computers, highlighting the transformative potential of quantum computing in optimizing the management of large-scale satellite networks., Comment: 6 pages, 4 figures

The transition to 100% renewable energy requires new techniques for managing energy networks, such as dividing them into sensible subsets of prosumers called micro-grids. Doing so in an optimal manner is a difficult optimization problem, as it can be abstracted to the Coalition Structure Generation problem in Induced Subgraph Games, a NP-complete problem which requires dividing an undirected, complete, weighted graph into subgraphs in a way that maximizes the sum of their internal weights. Recently, Venkatesh et al. (arXiv:2212.11372) published a Quantum Annealing (QA)-based iterative algorithm called GCS-Q, which they claim to be the best currently existing solver for the problem in terms of runtime complexity. As this algorithm makes the application of QA to the problem seem promising, but is a greedy one, this work proposes several less greedy QA-based approaches and investigates whether any of them can outperform GCS-Q in terms of solution quality. While we find that this is not the case yet on D-Wave hardware, most of them do when using the classical QBSolv software as a solver. Especially an algorithm we call 4-split iterative R-QUBO shows potential here, finding all optima in our dataset while scaling favorably with the problem size in terms of runtime. Thus, it appears to be interesting for future research on quantum approaches to the problem, assuming QA hardware will become more noise-resilient over time., Comment: 7 pages, 4 figures (8 if counting subfigures). To be published in the proceedings of the 2024 IEEE International Conference on Quantum Computing and Engineering (QCE)

The inherent "black box" nature of deep neural networks (DNNs) compromises their transparency and reliability. Recently, explainable AI (XAI) has garnered increasing attention from researchers. Several perturbation-based interpretations have emerged. However, these methods often fail to adequately consider feature dependencies. To solve this problem, we introduce a perturbation-based interpretation guided by feature coalitions, which leverages deep information of network to extract correlated features. Then, we proposed a carefully-designed consistency loss to guide network interpretation. Both quantitative and qualitative experiments are conducted to validate the effectiveness of our proposed method. Code is available at github.com/Teriri1999/Perturebation-on-Feature-Coalition., Comment: 4 pages, 4 figures, 2 tables