Search

Congestion games are attractive because they can model many concrete situations where some competing entities interact through the use of some shared resources, and also because they always admit pure Nash equilibria which correspond to the local minima of a potential function. We explore the problem of computing a state of minimum potential in this setting. Using the maximum number of resources that a player can use at a time, and the possible symmetry in the players' strategy spaces, we settle the complexity of the problem for instances having monotone (i.e., either non-decreasing or non-increasing) latency functions on their resources. The picture, delineating polynomial and NP-hard cases, is complemented with tight approximation algorithms.

In this work we study the problem of {\em Stochastic Budgeted Multi-round Submodular Maximization} (SBMSm), in which we would like to adaptively maximize the sum over multiple rounds of the value of a monotone and submodular objective function defined on a subset of items, subject to the fact that the values of this function depend on the realization of stochastic events and the number of items that we can select over all rounds is limited by a given budget. This problem extends, and generalizes to multiple round settings, well-studied problems such as (adaptive) influence maximization and stochastic probing. We first show that, if the number of items and stochastic events is somehow bounded, there is a polynomial time dynamic programming algorithm for SBMSm. Then, we provide a simple greedy approximation algorithm for SBMSm, that first non-adaptively allocates the budget to be spent at each round, and then greedily and adaptively maximizes the objective function by using the budget assigned at each round. Such algorithm guarantees a $(1-1/e-\epsilon)$-approximation to the optimal adaptive value. Finally, by introducing a metric called {\em budget-adaptivity gap}, we measure how much an optimal policy for SBMSm, that is adaptive in both the budget allocation and item selection, is better than an optimal partially adaptive policy that, as in our greedy algorithm, determined the budget allocation in advance. We show a tight bound of $e/(e-1)$ on the budget-adaptivity gap, and this result implies that our greedy algorithm guarantees the best approximation among all partially adaptive policies.

To what extent does the structure of the players' strategy space influence the efficiency of decentralized solutions in congestion games? In this work, we investigate whether better performance are possible when restricting to load balancing games in which players can only choose among single resources. We consider three different solutions concepts, namely, approximate pure Nash equilibria, approximate one-round walks generated by selfish players aiming at minimizing their personal cost and approximate one-round walks generated by cooperative players aiming at minimizing the marginal increase in the sum of the players' personal costs. The last two concepts can be interpreted as solutions of greedy online algorithms for the related resource selection problem. We show that, under fairly general latency functions on the resources, better bounds cannot be achieved if players are either weighted or asymmetric. On the positive side, we prove that, under mild assumptions on the latency functions, improvements on the performance of approximate pure Nash equilibria are possible for load balancing games with weighted and symmetric players in the case of identical resources. We also design lower bounds on the performance of one-round walks in load balancing games with unweighted players and identical resources., Comment: To cite this paper, consider the preliminary version appeared in the proceedings of ESA 2017: "Vittorio Bil\`o, Cosimo Vinci: On the Impact of Singleton Strategies in Congestion Games. The 25th Annual European Symposium on Algorithms (ESA), 17:1-17:14 (2017)"

We investigate traffic routing both from the perspective of theory as well as real world data. First, we introduce a new type of games: $\theta$-free flow games. Here, commuters only consider, in their strategy sets, paths whose free-flow costs (informally their lengths) are within a small multiplicative $(1+\theta)$ constant of the optimal free-flow cost path connecting their source and destination, where $\theta\geq0$. We provide an exhaustive analysis of tight bounds on PoA($\theta$) for arbitrary classes of cost functions, both in the case of general congestion/routing games as well as in the special case of path-disjoint networks. Second, by using a large mobility dataset in Singapore, we inspect minute-by-minute decision-making of thousands of commuters, and find that $\theta=1$ is a good estimate of agents' route (pre)selection mechanism. In contrast, in Pigou networks, the ratio of the free-flow costs of the routes, and thus $\theta$, is \textit{infinite}; so, although such worst case networks are mathematically simple, they correspond to artificial routing scenarios with little resemblance to real world conditions, opening the possibility of proving much stronger Price of Anarchy guarantees by explicitly studying their dependency on $\theta$. For example, in the case of the standard Bureau of Public Roads (BPR) cost model, where$c_e(x)= a_e x^4+b_e$, and for quartic cost functions in general, the standard PoA bound for $\theta=\infty$ is $2.1505$, and this is tight both for general networks as well as path-disjoint and even parallel-edge networks. In comparison, for $\theta=1$, the PoA in the case of general networks is only $1.6994$, whereas for path-disjoint/parallel-edge networks is even smaller ($1.3652$), showing that both the route geometries as captured by the parameter $\theta$ as well as the network topology have significant effects on PoA., Comment: Extended version of the conference paper presented in WINE 2020: The 16th Conference on Web and Internet Economics

In load balancing problems there is a set of clients, each wishing to select a resource from a set of permissible ones, in order to execute a certain task. Each resource has a latency function, which depends on its workload, and a client's cost is the completion time of her chosen resource. Two fundamental variants of load balancing problems are {\em selfish load balancing} (aka. {\em load balancing games}), where clients are non-cooperative selfish players aimed at minimizing their own cost solely, and {\em online load balancing}, where clients appear online and have to be irrevocably assigned to a resource without any knowledge about future requests. We revisit both selfish and online load balancing under the objective of minimizing the {\em Nash Social Welfare}, i.e., the geometric mean of the clients' costs. To the best of our knowledge, despite being a celebrated welfare estimator in many social contexts, the Nash Social Welfare has not been considered so far as a benchmarking quality measure in load balancing problems. We provide tight bounds on the price of anarchy of pure Nash equilibria and on the competitive ratio of the greedy algorithm under very general latency functions, including polynomial ones. For this particular class, we also prove that the greedy strategy is optimal as it matches the performance of any possible online algorithm.

In the adaptive influence maximization problem, we are given a social network and a budget $k$, and we iteratively select $k$ nodes, called seeds, in order to maximize the expected number of nodes that are reached by an influence cascade that they generate according to a stochastic model for influence diffusion. Differently from the non-adaptive influence maximization problem, where all the seeds must be selected beforehand, here nodes are selected sequentially one by one, and the decision on the $i$th seed is based on the observed cascade produced by the first $i-1$ seeds. We focus on the myopic feedback model, in which we can only observe which neighbors of previously selected seeds have been influenced and on the independent cascade model, where each edge is associated with an independent probability of diffusing influence. Previous works showed that the adaptivity gap is at most $4$, which implies that the non-adaptive greedy algorithm guarantees an approximation factor of $\frac{1}{4}\left(1-\frac{1}{e}\right)$ for the adaptive problem. In this paper, we improve the bounds on both the adaptivity gap and on the approximation factor. We directly analyze the approximation factor of the non-adaptive greedy algorithm, without passing through the adaptivity gap, and show that it is at least $\frac{1}{2}\left(1-\frac{1}{e}\right)$. Therefore, the adaptivity gap is at most $\frac{2e}{e-1}\approx 3.164$. To prove these bounds, we introduce a new approach to relate the greedy non-adaptive algorithm to the adaptive optimum. The new approach does not rely on multi-linear extensions or random walks on optimal decision trees, which are commonly used techniques in the field. We believe that it is of independent interest and may be used to analyze other adaptive optimization problems., Comment: arXiv admin note: text overlap with arXiv:2006.15374

In the influence maximization (IM) problem, we are given a social network and a budget $k$, and we look for a set of $k$ nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. In this paper, we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the $i$th seed can be based on the observed cascade produced by the first $i-1$ seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by $\lceil n^{1/3}\rceil $, where $n$ is the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from $\frac{2e}{e-1}\approx 3.16$ to $\frac{2e^2}{e^2-1}\approx 2.31$. Finally, we study $\alpha$-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most $\alpha$, and show that the adaptivity gap is upper-bounded by $\sqrt{\alpha}+O(1)$. Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most $\frac{3e^3}{e^3-1}\approx 3.16$. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest., Comment: 18 pages

We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su--Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time., Comment: Accepted journal version