In this paper, we study the Facility Location Problem with Scarce Resources (FLPSR) under the assumption that agents' type follows a probability distribution on [0,1]. In the FLPSR, the goal is to identify the optimal locations for one or more capacitated facilities to maximize Social Welfare (SW), defined as the sum of the utilities of all agents. Since the total capacity of the facilities is insufficient to serve all agents, they compete in a First-Come-First-Served game to get accommodated. The main contribution of the paper ties Optimal Transport theory to the problem of selecting a truthful mechanism tailored to the agents' distributions. For the case of a single facility, we show that an optimal mechanism always exists. We examine three classes of probability distributions and characterize the optimal mechanism analytically or provide a routine to numerically compute it. We extend our results to the case in which we have two capacitated facilities to place. Initially, we assume that agents are independent and identically distributed, but our techniques generalize to scenarios where agents are not identically distributed. Finally, we validate our findings through several numerical experiments, including: (i) deriving optimal mechanisms for the class of beta distributions, (ii) assessing the Bayesian approximation ratio of these mechanisms for small numbers of agents, and (iii)assessing how quickly the expected mechanism SW converges to its limit.

Measuring distances in multidimensional settings poses a significant challenge encountered across various scientific and engineering disciplines. In this paper, we introduce a novel measure of divergence to quantify the discrepancy between two multidimensional distributions—one predicted by a machine learning model and the other expected. Our approach builds upon the class of Energy Distances and incorporates a whitening pre-processing step, resulting in a divergence that is strictly connected to the new multivariate Gini index. To validate the proposed divergence, we demonstrate its effectiveness as a loss function for training a neural network designed to predict the financial performance of small and medium enterprises.

In this paper, we explore the Mechanism Design aspects of the m -Capacitated Facility Location Problem ( m -CFLP) on a line, focusing on two frameworks. In the first framework, the number of facilities is arbitrary, all facilities share the same capacity, and the number of agents matches the total capacity of the facilities. In the second framework, we need to locate two facilities, each with a capacity equal to at least half the number of agents. For both frameworks, we propose truthful mechanisms with bounded approximation ratios in terms of Social Cost (SC) and Maximum Cost (MC). When m > 2 , our results stand in contrast to the impossibility results known for the classical m -Facility Location Problem, where capacity constraints are absent. Moreover, all the proposed mechanisms are optimal with respect to MC and either optimal or near-optimal with respect to the SC among anonymous mechanisms. We then establish lower bounds on the approximation ratios that any truthful and deterministic mechanism achieves with respect to SC and MC for both frameworks. Lastly, we run several numerical experiments to empirically evaluate the performances of our mechanisms with respect to the SC or the MC. Our empirical analysis shows that our proposed mechanisms outperform all previously proposed mechanisms applicable in this setting.

In this article, we explore the Mechanism Design aspects of the Maximum Vertex-Weighted \(b\) -matching (MVbM) problem on bipartite graphs \((A\cup T,E)\) . The set \(A\) comprises agents, while \(T\) represents tasks. The set \(E\) , which connects \(A\) and \(T\) , is the private information of either agents or tasks. In this framework, we investigate three mechanisms— \(\mathbb{M}_{BFS}\) , \(\mathbb{M}_{DFS}\) , and \(\mathbb{M}_{G}\) . We examine scenarios in which either agents or tasks are strategic and report their adjacent edges to one of the three mechanisms. In both cases, we assume that the strategic entities are bounded by their statements: They can hide edges, but they cannot report edges that do not exist. First, we consider the case in which agents can manipulate. In this framework, \(\mathbb{M}_{BFS}\) and \(\mathbb{M}_{DFS}\) are optimal but not truthful. By characterizing the Nash Equilibria induced by \(\mathbb{M}_{BFS}\) and \(\mathbb{M}_{DFS}\) , we reveal that both mechanisms have a Price of Anarchy ( \(PoA\) ) and Price of Stability ( \(PoS\) ) of \(2\) . These efficiency guarantees are tight; no deterministic mechanism can achieve a lower \(PoA\) or \(PoS\) . In contrast, the third mechanism, \(\mathbb{M}_{G}\) , is not optimal, but truthful and its approximation ratio is \(2\) . We demonstrate that this ratio is optimal; no deterministic and truthful mechanism can outperform it. We then shift our focus to scenarios where tasks can exhibit strategic behavior. In this case, \(\mathbb{M}_{BFS}\) , \(\mathbb{M}_{DFS}\) , and \(\mathbb{M}_{G}\) all maintain truthfulness, making \(\mathbb{M}_{BFS}\) and \(\mathbb{M}_{DFS}\) truthful and optimal mechanisms. In conclusion, we investigate the manipulability of \(\mathbb{M}_{BFS}\) and \(\mathbb{M}_{DFS}\) through experiments on randomly generated graphs. We observe that (i) \(\mathbb{M}_{BFS}\) is less prone to be manipulated by the first agent than \(\mathbb{M}_{DFS}\) , and (ii) \(\mathbb{M}_{BFS}\) is more manipulable on instances in which the total capacity of the agents is equal to the number of tasks. 1

In Federated Learning, a Central Node (CN) coordinates a group of agents to collectively train a shared neural network.However, due to the inherent information asymmetry, some agents may behave as free riders and exploit the system by reaping rewards or by passively benefiting from the common model without contributing to the training process.Proof-of-Training (PoT) effectively allows the CN to verify that an agent has completed training honestly and correctly.However, this method incurs high costs, including proof generation by the agent, communication expenses, and proof verification by the CN.Conducting Proof-of-Training in each FL round is impractical due to these expenses.To enhance verification efficiency, a feasible strategy is to conduct probabilistic verification, where only a subset of agents is sampled for verification in each FL round.This paper aims to design a new incentive mechanism to motivate the agents behave honestly and potentially mitigate free riders.Our model hinges on two parameters: (i) the reward allocated to the local trainers, namely 𝑅, and (ii) a probability vector, denoted as ì 𝑝, indicating the likelihood of subjecting each agent to PoT scrutiny.We show that it is possible to characterize a set of parameters 𝑅 and ì 𝑝 that minimizes the total CN cost and makes the routine Individually Rational and Incentive Compatible, so that every agent will actively train their local model.Finally, we validate our model through extensive experiments.Our findings show that our characterization of the best reward and validation scheme is correct as they minimize the cost of the training routine without compromising the convergence speed.All our experiments are conducted on various datasets, demonstrating the wide applicability of our results.

This paper investigates the Mechanism Design aspects of the $m$-Capacitated Facility Location Problem where the total facility capacity is lower than the number of agents. Following \cite{aziz2020capacity}, the Social Welfare of the facility location is determined through a First-Come-First-Served (FCFS) game where agents compete after the facility positions are established. When the number of facilities is $m>1$, the Nash Equilibrium (NE) of the FCFS game is not unique, thus the utility of the agents and the notion of truthfulness are not well-defined. To address these issues, we consider absolutely truthful mechanisms, i.e. mechanisms able to prevent agents from misreporting regardless of the strategies played during the FCFS game. We pair this more stringent truthfulness requirement with the notion of Equilibrium Stable (ES) mechanism, i.e. mechanisms whose Social Welfare does not depend on the NE of the FCFS game. We show that the class of percentile mechanisms is absolutely truthful and characterize under which conditions they are ES. We then show that the approximation ratio of each ES percentile mechanism is bounded and determine its value. Notably, when all the facilities have the same capacity and the number of agents is large enough, it is possible to achieve an approximation ratio smaller than $1+\frac{1}{2m-1}$. We enhance our findings by empirically evaluating the mechanisms’ performances when agents’ true positions follows a distribution.

In this paper, we study the Maximum Vertex-weighted b-Matching (MVbM) problem on bipartite graphs in a new game-theoretical environment. In contrast to other game-theoretical settings, we consider the case in which the value of the tasks is public and common to every agent so that the private information of every agent consists of edges connecting them to the set of tasks. In this framework, we study three mechanisms. Two of these mechanisms, namely MBFS and MDFS, are optimal but not truthful, while the third one, MAP, is truthful but sub-optimal. Albeit these mechanisms are induced by known algorithms, we show MBFS and MDFS are the best possible mechanisms in terms of Price of Anarchy and Price of Stability, while MAP is the best truthful mechanism in terms of approximated ratio. Furthermore, we characterize the Nash Equilibria of MBFS and MDFS and retrieve sets of conditions under which MBFS acts as a truthful mechanism, which highlights the differences between MBFS and MDFS. Finally, we extend our results to the case in which agents’ capacity is part of their private information.

Due to the large number of submissions that more and more conferences experience, finding an automatized way to well distribute the submitted papers among reviewers has become necessary. We model the peer-reviewing matching problem as a bilevel programming (BP) formulation. Our model consists of a lower-level problem describing the reviewers’ perspective and an upper-level problem describing the editors’. Every reviewer is interested in minimizing their overall effort, while the editors are interested in finding an allocation that maximizes the quality of the reviews and follows the reviewers’ preferences the most. To the best of our knowledge, the proposed model is the first one that formulates the peer-reviewing matching problem by considering two objective functions, one to describe the reviewers’ viewpoint and the other to describe the editors’ viewpoint. We demonstrate that both the upper-level and lower-level problems are feasible and that our BP model admits a solution under mild assumptions. After studying the properties of the solutions, we propose a heuristic to solve our model and compare its performance with the relevant state-of-the-art methods. Extensive numerical results show that our approach can find fairer solutions with competitive quality and less effort from the reviewers.(Our code website: https://github.com/Galaxy-ZRX/Bilevel-Review.)

This paper presents a novel method to compute the exact Kantorovich-Wasserstein distance between a pair of $d$-dimensional histograms having $n$ bins each. We prove that this problem is equivalent to an uncapacitated minimum cost flow problem on a $(d+1)$-partite graph with $(d+1)n$ nodes and $dn^{\frac{d+1}{d}}$ arcs, whenever the cost is separable along the principal $d$-dimensional directions. We show numerically the benefits of our approach by computing the Kantorovich-Wasserstein distance of order 2 among two sets of instances: gray scale images and $d$-dimensional biomedical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms.