The dynamic topology, resource constraints, and data heterogeneity inherent in the Internet of Vehicles (IoV) present fundamental challenges to the effective deployment of federated learning (FL) applications. Traditional FL strategies often suffer from suboptimal model performance and excessive communication overhead under such conditions. Existing solutions primarily focus on static resource allocation and overlook the compounded effects of high mobility, diverse device capabilities, and time-varying data quality. Moreover, current incentive mechanisms lack adaptability to dynamic resource-benefit trade-offs, making it challenging to sustain efficient participation from vehicle clients. To address these issues, we propose NBCI-FL, an incentive framework that redefines vehicular collaboration as a multi-objective coalition game. It introduces a mobility-aware coalition-formation mechanism based on heterogeneous coalition games, along with a three-dimensional evaluation-based client-selection mechanism to construct efficient and stable learning clusters. Furthermore, we propose a two-stage Nash bargaining game that dynamically balances the fairness of data contributions with the optimization of resource utilization efficiency. Theoretical analysis proves the existence and effectiveness of the Nash bargaining equilibrium under vehicular dynamic conditions. Extensive simulations on real-world datasets demonstrate that our proposed NBCI-FL substantially outperforms state-of-the-art traditional FL baselines by maintaining high global model accuracy, improving communication efficiency, enhancing network stability, and ensuring fair and rational utility allocation among all participants.

Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms.

We study the mechanism design problem of facility location on a metric space in the learning-augmented framework, where mechanisms have access to an imperfect prediction of optimal facility locations. Our goal is to design strategyproof (SP) mechanisms to elicit agent preferences on the facility locations truthfully and, leveraging the given imperfect prediction, determine the facility location that approximately minimizes the maximum cost among all agents. In particular, we seek SP mechanisms whose approximation guarantees depend on the prediction errors — achieve improved guarantees when the prediction is accurate (known as the consistency), while still ensuring robust worst-case performance when the prediction is arbitrarily inaccurate (known as the robustness). When the metric space is the real line, we characterize all deterministic SP mechanisms with consistency strictly less than 2 and bounded robustness: such mechanisms must be the MinMaxP mechanism, which returns the prediction location if it lies between the two extreme agent locations and, otherwise, returns the closest agent location to the prediction. We further show that, for any prediction error η ≥ 0, while MinMaxP is (1 + min(1, η))-approximation, no deterministic SP mechanism can achieve a better approximation. In two-dimensional spaces with the l_p metric, we analyze the approximation guarantees of a deterministic mechanism that runs MinMaxP independently on each coordinate, as well as a randomized mechanism that selects between two deterministic ones with specific probabilities. Finally, we discuss the group strategyproofness of the considered mechanisms.

Large Language Models (LLMs) have demonstrated amazing capabilities in language generation, comprehension, and knowledge reasoning. However, relying on a single model can result in biased and unstable outcomes in many tasks. Multi-model collaboration has been introduced to enhance reasoning abilities on various tasks, but obtaining the correct answer from multiple candidate responses remains a challenge. To address this issue, we propose multi-model brainstorming based on prompt. It incorporates different models into a group for brainstorming, to reach a consensus answer after multiple rounds of reasoning elaboration and re-inference. Our experiments on diverse datasets demonstrate that the brainstorming can substantially improve the effectiveness in logical reasoning. Further, we observe that two small-parameter models can achieve accuracy comparable to a larger-parameter model through brainstorming, presenting a novel approach for the distributed deployment of LLMs.

We study a variation of facility location problems (FLPs) that aims to improve the accessibility of agents to the facility within the context of mechanism design without money. In such a variation, agents have preferences on the ideal locations of the facility on a real line, and the facility’s location is fixed in advance where (re)locating the facility is not possible due to various constraints (e.g., limited space and construction costs). To improve the accessibility of agents to facilities, existing mechanism design literature in FLPs has proposed to structurally modify the real line (e.g., by adding a new interval) or provide shuttle services between two points when structural modifications are not possible. In this paper, we focus on the latter approach and propose to construct an accessibility range to extend the accessibility of the facility. In the range, agents can receive accommodations (e.g., school buses, campus shuttles, or pickup services) to help reach the facility. Therefore, the cost of each agent is the distance from their ideal location to the facility (possibility) through the range. We focus on designing strategyproof mechanisms that elicit true ideal locations from the agents and construct accessibility ranges (intervals) to approximately minimize the social cost or the maximum cost of agents. For both social and maximum costs, we design group strategyproof mechanisms and strong group strategyproof mechanisms with (asymptotically) tight bounds on the approximation ratios.

A k -submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k -submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O ( n 2 k ) . We show that Greedy+Singleton has an approximation ratio of 0.273 for monotone functions , which improves the previous analysis of 0.158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k -submodular functions, and prove an approximation ratio of 0.219.

A k-submodular function is a generalization of submodular functions that takes k disjoint subsets as input and outputs a real value. It captures many problems in combinatorial optimization and machine leaning such as influence maximization, sensor placement, feature selection, etc. In this paper, we consider the monotone k-submodular maximization problem under a knapsack constraint, and explore the performance guarantee of a greedy-based algorithm: enumerating all size-2 solutions and extending every singleton solution greedily; the best outcome is returned. We provide a novel analysis framework and prove that this algorithm achieves an approximation ratio of at least 0.328. This is the best-known result of combinatorial algorithms on k-submodular knapsack maximization. In addition, within the framework, we can further improve the approximation ratio to a value approaching 1/3 with any desirable accuracy, by enumerating sufficiently large base solutions. The results can even be extended to non-monotone k-submodular functions.

We study the problem faced by a decision maker who wants to locate a set of facilities on a real line and allocate agents/items to the facilities. The items have given locations on the line, and can only be assigned to one of their closest facilities. The facilities are controlled by managers, who have additive utility over the items. An optimal solution that maximizes the (utilitarian or egalitarian) social welfare of the facilities may present a very unbalanced allocation of the items to the facilities and hence be perceived as unfair. In this paper, we are interested in fair allocation among facility managers and consider the well-studied proportionality and envy-freeness fairness notions and their relaxations. We assess the availability, existence, approximability, and the quality (price of fairness) of fair solutions, where the quality measures the system efficiency loss under a fair allocation compared to the one that maximizes the social welfare. Further, we show that one can find a Pareto-optimal solution in polynomial time.

We incorporate group fairness into the algorithmic centroid clustering problem, where $k$ centers are to be located to serve $n$ agents distributed in a metric space. We refine the notion of proportional fairness proposed in [Chen et al., ICML 2019] as {\em core fairness}. A $k$-clustering is in the core if no coalition containing at least $n/k$ agents can strictly decrease their total distance by deviating to a new center together. Our solution concept is motivated by the situation where agents are able to coordinate and utilities are transferable. A string of existence, hardness and approximability results is provided. Particularly, we propose two dimensions to relax core requirements: one is on the degree of distance improvement, and the other is on the size of deviating coalition. For both relaxations and their combination, we study the extent to which relaxed core fairness can be satisfied in metric spaces including line, tree and general metric space, and design approximation algorithms accordingly. We also conduct experiments on synthetic and real-world data to examine the performance of our algorithms.

The study of approximate mechanism design for facility location has been in the center of research at the intersection of artificial intelligence and economics for the last decade, largely due to its practical importance in various domains, such as social planning and clustering. At a high level, the goal is to select a number of locations on which to build a set of facilities, aiming to optimize some social objective based on the preferences of strategic agents, who might have incentives to misreport their private information. This paper presents a comprehensive survey of the significant progress that has been made since the introduction of the problem, highlighting all the different variants and methodologies, as well as the most interesting directions for future research.

Public projects can succeed or fail for many reasons such as the feasibility of the original goal and coordination among contributors. One major reason for failure is that insufficient work leaves the project partially completed. For certain types of projects anything short of full completion is a failure (e.g., feature request on software projects in GitHub). Therefore, project success relies heavily on individuals allocating sufficient effort. When there are multiple public projects, each contributor needs to make decisions to best allocate his/her limited effort (e.g., time) to projects while considering the effort allocation decisions of other strategic contributors and his/her parameterized utilities based on values and costs for the projects. In this paper, we introduce a game-theoretic effort allocation model of contributors to public projects for modeling effort allocation of strategic contributors. We study the related Nash equilibrium (NE) computational problems and provide NP-hardness results for the existence of NE and polynomial-time algorithms for finding NE in restricted settings. Finally, we investigate the inefficiency of NE measured by the price of anarchy and price of stability.

We study single-candidate voting embedded in a metric space, where both voters and candidates are points in the space, and the distances between voters and candidates specify the voters' preferences over candidates. In the voting, each voter is asked to submit her favorite candidate. Given the collection of favorite candidates, a mechanism for eliminating the least popular candidate finds a committee containing all candidates but the one to be eliminated. Each committee is associated with a social value that is the sum of the costs (utilities) it imposes (provides) to the voters. We design mechanisms for finding a committee to optimize the social value. We measure the quality of a mechanism by its distortion, defined as the worst-case ratio between the social value of the committee found by the mechanism and the optimal one. We establish new upper and lower bounds on the distortion of mechanisms in this single-candidate voting, for both general metrics and well-motivated special cases.

This paper studies the facility location games with payments, where facilities are strategic players. In the game, customers and facilities are located at publicly known locations on a line segment. Each selfish facility has an opening-cost as her private information, and she may strategically report it. Upon receiving the reports, the government uses a mechanism to select some facilities to open and pay to them. The cost/utility of each customer depends on the distance to the nearest opened facility. Under a given budget B, which constrains the total payment, we derive upper and lower bounds on the approximation ratios of truthful budget feasible mechanisms for four utilitarian and egalitarian objectives, and study the case when augmented budget is allowed.