Imperial College London


Faculty of EngineeringDepartment of Computing

Lecturer in Department of Computing



d.paccagnan Website




Electrical EngineeringSouth Kensington Campus





Publication Type

22 results found

Paccagnan D, Chandan R, Ferguson BL, Marden JRet al., 2021, Optimal Taxes in Atomic Congestion Games, ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION, Vol: 9, ISSN: 2167-8375

Journal article

Paccagnan D, Chandan R, Marden JR, 2020, Utility design for distributed resource Allocation - Part I: characterizing and optimizing the exact price of anarchy, IEEE Transactions on Automatic Control, Vol: 65, Pages: 4616-4631, ISSN: 0018-9286

Game theory has emerged as a fruitful paradigm for the design of networked multiagent systems. A fundamental component of this approach is the design of agents' utility functions so that their self-interested maximization results in a desirable collective behavior. In this work we focus on a well-studied class of distributed resource allocation problems where each agent is requested to select a subset of resources with the goal of optimizing a given system-level objective. Our core contribution is the development of a novel framework to tightly characterize the worst case performance of any resulting Nash equilibrium (price of anarchy) as a function of the chosen agents' utility functions. Leveraging this result, we identify how to design such utilities so as to optimize the price of anarchy through a tractable linear program. This provides us with a priori performance certificates applicable to any existing learning algorithm capable of driving the system to an equilibrium. Part II of this work specializes these results to submodular and supermodular objectives, discusses the complexity of computing Nash equilibria, and provides multiple illustrations of the theoretical findings.

Journal article

Chandan R, Paccagnan D, Marden JR, 2020, When smoothness is not enough: toward exact quantification and optimization of the price-of-anarchy, 2019 IEEE 58th Conference on Decision and Control (CDC), Publisher: IEEE, Pages: 1-6

Today's multiagent systems have grown too complex to rely on centralized controllers, prompting increasing interest in the design of distributed algorithms. In this respect, game theory has emerged as a valuable tool to complement more traditional techniques. The fundamental idea behind this approach is the assignment of agents' local cost functions, such that their selfish minimization attains, or is provably close to, the global objective. Any algorithm capable of computing an equilibrium of the corresponding game inherits an approximation ratio that is, in the worst case, equal to its price-of-anarchy. Therefore, a successful application of the game design approach hinges on the possibility to quantify and optimize the equilibrium performance.Toward this end, we introduce the notion of generalized smoothness, and show that the resulting efficiency bounds are significantly tighter compared to those obtained using the traditional smoothness approach. Leveraging this newly-introduced notion, we quantify the equilibrium performance for the class of local resource allocation games. Finally, we show how the agents' local decision rules can be designed in order to optimize the efficiency of the corresponding equilibria, by means of a tractable linear program.

Conference paper

Paccagnan D, Campi MC, 2019, The scenario approach meets uncertain game theory and variational inequalities, 2019 IEEE 58th Conference on Decision and Control (CDC), Publisher: IEEE, Pages: 1-6

Variational inequalities are modeling tools used to capture a variety of decision-making problems arising in mathematical optimization, operations research, game theory. The scenario approach is a set of techniques developed to tackle stochastic optimization problems, take decisions based on historical data, and quantify their risk. The overarching goal of this manuscript is to bridge these two areas of research, and thus broaden the class of problems amenable to be studied under the lens of the scenario approach. First and foremost, we provide out-of-samples feasibility guarantees for the solution of variational and quasi variational inequality problems. Second, we apply these results to two classes of uncertain games. In the first class, the uncertainty enters in the constraint sets, while in the second class the uncertainty enters in the cost functions. Finally, we exemplify the quality and relevance of our bounds through numerical simulations on a demand-response model.

Conference paper

Chandan R, Paccagnan D, Marden JR, 2019, Optimal price of anarchy in cost-sharing games, 2019 American Control Conference (ACC), Publisher: IEEE, Pages: 2277-2282

The design of distributed algorithms is central to the study of multiagent systems control. In this paper, we consider a class of combinatorial cost-minimization problems and propose a framework for designing distributed algorithms with a priori performance guarantees that are near-optimal. We approach this problem from a game-theoretic perspective, assigning agents cost functions such that the equilibrium efficiency (price of anarchy) is optimized. Once agents' cost functions have been specified, any algorithm capable of computing a Nash equilibrium of the system inherits a performance guarantee matching the price of anarchy. Towards this goal, we formulate the problem of computing the price of anarchy as a tractable linear program. We then present a framework for designing agents' local cost functions in order to optimize for the worst-case equilibrium efficiency. Finally, we investigate the implications of our findings when this framework is applied to systems with convex, nondecreasing costs.

Conference paper

Paccagnan D, Marden JR, 2019, The importance of system-level information in multiagent systems design: cardinality and covering problems, IEEE Transactions on Automatic Control, Vol: 64, Pages: 3253-3267, ISSN: 0018-9286

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behavior. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this paper, we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behavior over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori.

Journal article

Chandan R, Paccagnan D, Ferguson BL, Marden JRet al., 2019, Computing optimal taxes in atomic congestion games, 14th Workshop on the Economics of Networks, Systems and Computation, Publisher: ACM Press, Pages: 1-1

When the performance of a system is dictated by the behaviour of its users, self-interested choices can result in sub-optimal system operation, as is the case in road traffic networks. The inefficiency resulting from such selfish behaviour is commonly measured by the ratio between the emergent worst-case system cost and the minimum system cost, termed price-of-anarchy. As the degree of inefficiency can be significant even for relatively simple systems (e.g., affine congestion games), researchers have proposed a variety of approaches to align the emergent selfish behaviour with the desired system objective. A well-studied and promising method is that of altering users' perceived costs by means of taxes.

Conference paper

Paccagnan D, Gentile B, Parise F, Kamgarpour M, Lygeros Jet al., 2019, Nash and Wardrop equilibria in aggregative games with coupling constraints, IEEE Transactions on Automatic Control, Vol: 64, Pages: 1373-1388, ISSN: 0018-9286

We consider the framework of aggregative games, in which the cost function of each agent depends on his own strategy and on the average population strategy. As first contribution, we investigate the relations between the concepts of Nash and Wardrop equilibria. By exploiting a characterization of the two equilibria as solutions of variational inequalities, we bound their distance with a decreasing function of the population size. As second contribution, we propose two decentralized algorithms that converge to such equilibria and are capable of coping with constraints coupling the strategies of different agents. Finally, we study the applications of charging of electric vehicles and of route choice on a road network.

Journal article

Paccagnan D, Parise F, Lygeros J, 2018, On the efficiency of nash equilibria in aggregative charging games, IEEE Control Systems Letters, Vol: 2, Pages: 629-634, ISSN: 2475-1456

Several works have recently suggested to model the problem of coordinating the charging needs of a fleet of electric vehicles as a game, and have proposed distributed algorithms to coordinate the vehicles towards a Nash equilibrium of such game. However, Nash equilibria have been shown to posses desirable system-level properties only in simplified cases. In this letter, we use the concept of price of anarchy (PoA) to analyze the inefficiency of Nash equilibria when compared to the social optimum solution. More precisely, we show that: 1) for linear price functions depending on all the charging instants, the PoA converges to one as the population of vehicles grows; 2) for price functions that depend only on the instantaneous demand, the PoA converges to one if the price function takes the form of a positive pure monomial; and 3) for general classes of price functions, the asymptotic PoA can be bounded. For finite populations, we additionally provide a bound on the PoA as a function of the number vehicles in the system. We support the theoretical findings by means of numerical simulations.

Journal article

Gentile B, Paccagnan D, Ogunsola B, Lygeros Jet al., 2018, A novel concept of equilibrium over a network, 2017 IEEE 56th Annual Conference on Decision and Control (CDC), Publisher: IEEE, Pages: 3829-3834

We define and analyze a novel concept of equilibrium over a network, which we refer to as location equilibrium. Its applications include area coverage for taxi drivers, human migration and task assignment for a server network. In particular, we show that a specific instance of the location equilibrium problem is equivalent to the Wardrop equilibrium problem on a specific network. Further, we show that finding a location equilibrium is equivalent to solving a variational inequality with an operator which is in general not monotone. Based on the relation to the Wardrop equilibrium, we propose the use of the extragradient algorithm and show its convergence to a specific location equilibrium. The findings are applied to a numerical study of area coverage for taxi drivers in Hong Kong.

Conference paper

Paccagnan D, Marden JR, 2018, The risks and rewards of conditioning noncooperative designs to additional information, 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Publisher: IEEE, Pages: 958-965

A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behaviour. The information available to the agents, gathered either through communication or sensing, defines the structure of the admissible control laws and naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information can be used to produce a significant performance enhancement. This paper studies, within a class of resource allocation problems, the case when such information is uncertain or inaccessible and pinpoints a fundamental risk-reward tradeoff faced by the system designer.

Conference paper

Burger G, Paccagnan D, Gentile B, Lygeros Jet al., 2017, Guarantees of convergence to a dynamic user equilibrium for a single arc network, 20th World Congress of the International-Federation-of-Automatic-Control (IFAC), Publisher: ELSEVIER, Pages: 9674-9679, ISSN: 2405-8963

While steady state traffic equilibrium problems have been successfully studied, the analysis complicates when the dynamics of the vehicles is taken into account. The literature on the topic presents a variety of models, but usually the algorithms suggested do not possess convergence guarantees. We propose a simple game where all the vehicles travel along the same arc and choose the starting time of their trip. Based on the first Wardrop principle, we formulate the traffic user equilibrium as a variational inequality. Since monotonicity of the corresponding operator guarantees convergence of gradient-based algorithms, we provide theoretical guarantees for short time horizons, and analyze it numerically for longer ones. We conclude with simulations showing that convergence can be achieved also in more general setups, for example with multiple origins or destinations.

Conference paper

Paccagnan D, Kamgarpour M, Lygeros J, 2017, On aggregative and mean field games with applications to electricity markets, 2016 European Control Conference (ECC), Publisher: IEEE, Pages: 196-201

We study the existence and uniqueness of Nash equilibria for a certain class of aggregative games with finite and possibly large number of players. Sufficient conditions for these are obtained using the theory of variational inequalities together with the specific structure of the objective functions. We further present an algorithm that converges to the Nash equilibrium in a decentralized fashion with provable guarantees. The theoretical results are applied to the problem of managing the charging of a large fleet of plug-in electric vehicles and the results are compared with the existing work.

Conference paper

Paccagnan D, Gentile B, Parise F, Kamgarpour M, Lygeros Jet al., 2016, Distributed computation of generalized Nash equilibria in quadratic aggregative games with affine coupling constraints, 2016 IEEE 55th Conference on Decision and Control (CDC), Publisher: IEEE, Pages: 6123-6128

We analyse deterministic aggregative games, with large but finite number of players, that are subject to both local and coupling constraints. Firstly, we derive sufficient conditions for the existence of a generalized Nash equilibrium, by using the theory of variational inequalities together with the specific structure of the objective functions and constraints. Secondly, we present a coordination scheme, belonging to the class of asymmetric projection algorithms, and we prove that it converges R-linearly to a generalized Nash equilibrium. To this end, we extend the available results on asymmetric projection algorithms to our setting. Finally, we show that the proposed scheme can be implemented in a decentralized fashion and it is suitable for the analysis of large populations. Our theoretical results are applied to the problem of charging a fleet of plug-in electric vehicles, in the presence of capacity constraints coupling the individual demands.

Conference paper

Paccagnan D, Kamgarpour M, Lygeros J, 2016, On the range of feasible power trajectories for a population of thermostatically controlled loads, 2015 54th IEEE Conference on Decision and Control (CDC), Publisher: IEEE, Pages: 5883-5888

We study the potential of a population of thermostatically controlled loads to track desired power signals with provable guarantees. Based on connecting the temperature state of an individual device with its internal energy, we derive necessary conditions that a given power signal needs to satisfy in order for the aggregation of devices to track it using non-disruptive probabilistic switching control. Our derivation takes into account hybrid individual dynamics, an accurate continuous-time Markov chain model for the population dynamics and bounds on switching rates of individual devices. We illustrate the approach with case studies.

Conference paper

Jorgensen MJ, Paccagnan D, Poulsen NK, Larsen MBet al., 2014, IMU calibration and validation in a factory, remote on land and at sea, 2014 IEEE/ION Position, Location and Navigation Symposium - PLANS 2014, Publisher: IEEE, Pages: 1384-1391

This paper treats the IMU calibration and validation problem in three settings: Factory production line with the aid of a precision multi-axis turntable, in-the-field on land and at sea, both without specialist test equipment. The treatment is limited to the IMU calibration parameters of key relevance for gyro-compassing grade optical gyroscopes and force-rebalanced pendulous accelerometers: Scale factor, bias and sensor axes misalignments. Focus is on low-dynamic marine applications e.g., subsea construction and survey. Two different methods of calibration are investigated: Kalman smoothing using an Aided Inertial Navigation System (AINS) framework, augmenting the error state Kalman filter (ESKF) to include the full set of IMU calibration parameters and a least squares approach, where the calibration parameters are determined by minimizing the magnitude of the INS error differential equation output. A method of evaluating calibrations is introduced and discussed. The two calibration methods are evaluated for factory use and results compared to a legacy proprietary method as well as in-field calibration/verification on land and at sea. The calibration methods shows similar navigation performance as the proprietary method. This validates both methods for factory calibration. Furthermore it is shown that the AINS method can calibrate in-field on land and at sea without the use of a precision multi-axis turntable.

Conference paper

Gentile B, Paccagnan D, Ogunsula B, Lygeros Jet al., The Nash Equilibrium with Inertia in Population Games

In the traditional game-theoretic set up, where agents select actions andexperience corresponding utilities, an equilibrium is a configuration where noagent can improve their utility by unilaterally switching to a differentaction. In this work, we introduce the novel notion of inertial Nashequilibrium to account for the fact that, in many practical situations, actionchanges do not come for free. Specifically, we consider a population game andintroduce the coefficients $c_{ij}$ describing the cost an agent incurs byswitching from action $i$ to action $j$. We define an inertial Nash equilibriumas a distribution over the action space where no agent benefits in moving to adifferent action, while taking into account the cost of this change. First, weshow that the set of inertial Nash equilibria contains all the Nash equilibria,but is in general not convex. Second, we argue that classical algorithms forcomputing Nash equilibria cannot be used in the presence of switching costs. Wethen propose a natural better-response dynamics and prove its convergence to aninertial Nash equilibrium. We apply our results to predict the drivers'distribution of an on-demand ride-hailing platform.

Journal article

Ramaswamy V, Paccagnan D, Marden JR, Multiagent Maximum Coverage Problems: The Trade-off Between Anarchy and Stability

The price of anarchy and price of stability are three well-studiedperformance metrics that seek to characterize the inefficiency of equilibria indistributed systems. The distinction between these two performance metricscenters on the equilibria that they focus on: the price of anarchycharacterizes the quality of the worst-performing equilibria, while the priceof stability characterizes the quality of the best-performing equilibria. Whilemuch of the literature focuses on these metrics from an analysis perspective,in this work we consider these performance metrics from a design perspective.Specifically, we focus on the setting where a system operator is tasked withdesigning local utility functions to optimize these performance metrics in aclass of games termed covering games. Our main result characterizes afundamental trade-off between the price of anarchy and price of stability inthe form of a fully explicit Pareto frontier. Within this setup, optimizing theprice of anarchy comes directly at the expense of the price of stability (andvice versa). Our second results demonstrates how a system-operator couldincorporate an additional piece of system-level information into the design ofthe agents' utility functions to breach these limitations and improve thesystem's performance. This valuable piece of system-level information pertainsto the performance of worst performing agent in the system.

Journal article

Paccagnan D, Gairing M, In Congestion Games, Taxes Achieve Optimal Approximation

We consider the problem of minimizing social cost in atomic congestion gamesand show, perhaps surprisingly, that efficiently computed taxation mechanismsyield the same performance achievable by the best polynomial time algorithm,even when the latter has full control over the players' actions. It followsthat no other tractable approach geared at incentivizing desirable systembehavior can improve upon this result, regardless of whether it is based ontaxations, coordination mechanisms, information provision, or any otherprinciple. In short: Judiciously chosen taxes achieve optimal approximation. Three technical contributions underpin this conclusion. First, we show thatcomputing the minimum social cost is NP-hard to approximate within a givenfactor depending solely on the admissible resource costs. Second, we design atractable taxation mechanism whose efficiency (price of anarchy) matches thishardness factor, and thus is optimal. As these results extend to coarsecorrelated equilibria, any no-regret algorithm inherits the same performances,allowing us to devise polynomial time algorithms with optimal approximation.

Journal article

Paccagnan D, Distributed control and game design: From strategic agents to programmable machines

Large scale systems are forecasted to greatly impact our future lives thanksto their wide ranging applications including cooperative robotics, mobility ondemand, resource allocation, supply chain management. While technologicaldevelopments have paved the way for the realization of such futuristic systems,we have a limited grasp on how to coordinate the individual components toachieve the desired global objective. This thesis deals with the analysis andcoordination of large scale systems without the need of a centralizedauthority. In the first part of this thesis, we consider non-cooperative decision makingproblems where each agent's objective is a function of the aggregate behaviorof the population. First, we compare the performance of an equilibriumallocation with that of an optimal allocation and propose conditions underwhich all equilibrium allocations are efficient. Towards this goal, we prove anovel result bounding the distance between the strategies at a Nash and Wardropequilibrium that might be of independent interest. Second, we show how toderive scalable algorithms that guide agents towards an equilibrium allocation. In the second part of this thesis, we consider large-scale cooperativeproblems, where a number of agents need to be allocated to a set of resourceswith the goal of jointly maximizing a given submodular or supermodular setfunction. Since this class of problems is computationally intractable, we aimat deriving tractable algorithms for attaining approximate solutions. Weapproach the problem from a game-theoretic perspective and ask the following:how should we design agents' utilities so that any equilibrium configuration isalmost optimal? To answer this question we introduce a novel framework thatallows to characterize and optimize the system performance as a function of thechosen utilities by means of a tractable linear program.

Journal article

Salazar M, Paccagnan D, Agazzi A, H WPM, Heemelset al., Urgency-aware Optimal Routing in Repeated Games through Artificial Currencies

When people choose routes minimizing their individual delay, the aggregatecongestion can be much higher compared to that experienced by acentrally-imposed routing. Yet centralized routing is incompatible with thepresence of self-interested agents. How can we reconcile the two? In this paperwe address this question within a repeated game framework and propose a fairincentive mechanism based on artificial currencies that routes selfish agentsin a system-optimal fashion, while accounting for their temporal preferences.We instantiate the framework in a parallel-network whereby agents commuterepeatedly (e.g., daily) from a common start node to the end node. Thereafter,we focus on the specific two-arcs case whereby, based on an artificialcurrency, the agents are charged when traveling on the first, fast arc, whilstthey are rewarded when traveling on the second, slower arc. We assume theagents to be rational and model their choices through a game where each agentaims at minimizing a combination of today's discomfort, weighted by theirurgency, and the average discomfort encountered for the rest of the period(e.g., a week). We show that, if prices of artificial currencies arejudiciously chosen, the routing pattern converges to a system-optimal solution,while accommodating the agents' urgency. We complement our study throughnumerical simulations. Our results show that it is possible to achieve asystem-optimal solution whilst reducing the agents' perceived discomfort by14-20% when compared to a centralized optimal but urgency-unaware policy.

Journal article

Paccagnan D, Marden JR, Utility Design for Distributed Resource Allocation -- Part II: Applications to Submodular, Covering, and Supermodular Problems

A fundamental component of the game theoretic approach to distributed controlis the design of local utility functions.Relative to resource allocationproblems that are additive over the resources, Part I showed how to designlocal utilities so as to maximize the associated performance guarantees[Paccagnan et al., TAC 2019] which we measure by the price of anarchy. Thepurpose of the present manuscript is to specialize these results to the case ofsubmodular, covering, and supermodular problems. In all these cases we obtaintight expressions for the price of anarchy that often match or improve theguarantees associated to state-of-the-art approximation algorithms. Twoapplications and corresponding numerics are presented: the vehicle-targetassignment problem and a coverage problem arising in wireless data caching.

Journal article

This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.

Request URL: Request URI: /respub/WEB-INF/jsp/search-html.jsp Query String: respub-action=search.html&id=00976791&limit=30&person=true