Publications
30 results found
Paccagnan D, Gairing M, 2023, In Congestion Games, Taxes Achieve Optimal Approximation, OPERATIONS RESEARCH, ISSN: 0030-364X
Huang EY, Paccagnan D, Mei W, et al., 2023, Assign and Appraise: Achieving Optimal Performance in Collaborative Teams, IEEE TRANSACTIONS ON AUTOMATIC CONTROL, Vol: 68, Pages: 1614-1627, ISSN: 0018-9286
- Author Web Link
- Cite
- Citations: 1
Jalota D, Paccagnan D, Schiffer M, et al., 2023, Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements, INFORMS JOURNAL ON COMPUTING, ISSN: 1091-9856
Zhang K, Paccagnan D, Macias JJE, et al., 2023, Last-mile Collaboration: A Decentralized Mechanism with Performance Guarantees and its Implementation, Pages: 2916-2918, ISSN: 1548-8403
The last-mile urban freight market is characterised by soaring fragmentation, fierce competition and low profit margin. Horizontal collaboration could enable operators to exchange customers and coordinate routes, resulting in reduced costs and higher level of service. Previous research has focused on combinatorial auctions and scalable mechanisms are still limited. In this work, we propose an Iterative, Decentralized, and Auction-based Mechanism (IDAM) which is individually rational and budget balanced. It parallelizes several independent local auctions but still guarantees a bounded performance. When considering its best-case performance, IDAM could be as efficient as the centralized optimization while the worst-case performance depends on the fleet capacity and spatial distribution of customers. A case study of the Inner London Area, involving 50 companies and 1000 customers, showed that our approach achieves up to 76% cost savings.
Ferguson BL, Paccagnan D, Marden JR, 2023, The Cost of Informing Decision-Makers in Multi-Agent Maximum Coverage Problems With Random Resource Values, IEEE CONTROL SYSTEMS LETTERS, Vol: 7, Pages: 2928-2933, ISSN: 2475-1456
Hussain A, Belardinelli F, Paccagnan D, 2023, The impact of exploration on convergence and performance of multi-agent Q-learning dynamics, International Conference on Machine Learning, Publisher: Proceedings of Machine Learning Research, Pages: 14178-14202, ISSN: 2640-3498
Understanding the impact of exploration on the behaviour of multi-agent learning has, so far, benefited from the restriction to potential, or network zero-sum games in which convergence to an equilibrium can be shown. Outside of these classes, learning dynamics rarely converge and little is known about the effect of exploration in the face of non-convergence. To progress this front, we study the smooth Q-Learning dynamics. We show that, in any network game, exploration by agents results in the convergence of Q-Learning to a neighbourhood of an equilibrium. This holds independently of whether the dynamics reach the equilibrium or display complex behaviours. We show that increasing the exploration rate decreases the size of this neighbourhood and also decreases the ability of all agents to improve their payoffs. Furthermore, in a broad class of games, the payoff performance of Q-Learning dynamics, measured by Social Welfare, decreases when the exploration rate increases. Our experiments show this to be a general phenomenon, namely that exploration leads to improved convergence of Q-Learning, at the cost of payoff performance.
Ramaswamy V, Paccagnan D, Marden JR, 2022, Multiagent Maximum Coverage Problems: The Tradeoff Between Anarchy and Stability, IEEE TRANSACTIONS ON AUTOMATIC CONTROL, Vol: 67, Pages: 1698-1712, ISSN: 0018-9286
- Author Web Link
- Cite
- Citations: 1
Paccagnan D, Marden JR, 2022, Utility Design for Distributed Resource Allocation-Par II: Applications to Submodular, Covering, and Supermodular Problems, IEEE TRANSACTIONS ON AUTOMATIC CONTROL, Vol: 67, Pages: 618-632, ISSN: 0018-9286
- Author Web Link
- Cite
- Citations: 2
Zhang K, Macias JJE, Paccagnan D, et al., 2022, The Competition and Inefficiency in Urban Road Last-Mile Delivery, Pages: 1473-1481, ISSN: 1548-8403
The last-mile delivery market is highly competitive and is saturated with numerous small operators. In this context, the fierce competition between operators, joint with the rapid increase in the demand for home-delivery, resulted in a significant increase in urban freight traffic further worsening congestion and pollution. To tackle these issues, previous research has studied the implementation of collaborative last-mile operations, with organisations sharing resources in the form of inventory space or transportation capacity. However, a common limitation of the proposed models is ignoring time windows and the effects of externalities such as network congestion. In this work, we propose a framework to quantify the efficiency loss in urban last-mile delivery system by comparing the solutions of a fully-decentralised and fully-centralised last-mile delivery problem. In doing so, we develop a Multi-depot Vehicle Routing Problem with Time Windows and Congestible Network that is solved using a bespoke Parallel Hybrid Genetic Algorithm that accounts for the non-linearities arising from modelling endogenous network congestion. The model is evaluated on a case study based on central London to assess the efficiency gaps of realistic last-mile delivery operations. When time window constraints are not included, our results show that the efficiency loss fluctuates the most with a small number of customers, while it stabilises to less than 15% for instances with over 100 customers. However, time windows could significantly exacerbate this issue, resulting in an additional 25% of efficiency loss.
Chandan R, Paccagnan D, Marden JR, 2022, The Tension Between Anarchy and Stability in Congestion Games, American Control Conference (ACC), Publisher: IEEE, Pages: 1260-1265
Paccagnan D, Chandan R, Marden JR, 2022, Utility and mechanism design in multi-agent systems: An overview, ANNUAL REVIEWS IN CONTROL, Vol: 53, Pages: 315-328, ISSN: 1367-5788
- Author Web Link
- Cite
- Citations: 3
Gentile B, Paccagnan D, Ogunsula B, et al., 2021, The Nash Equilibrium With Inertia in Population Games, IEEE TRANSACTIONS ON AUTOMATIC CONTROL, Vol: 66, Pages: 5742-5755, ISSN: 0018-9286
Salazar M, Paccagnan D, Agazzi A, et al., 2021, Urgency-aware optimal routing in repeated games through artificial currencies, EUROPEAN JOURNAL OF CONTROL, Vol: 62, Pages: 22-32, ISSN: 0947-3580
- Author Web Link
- Cite
- Citations: 3
Paccagnan D, Chandan R, Ferguson BL, et al., 2021, Optimal Taxes in Atomic Congestion Games, ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION, Vol: 9, ISSN: 2167-8375
- Author Web Link
- Cite
- Citations: 11
Duan X, Paccagnan D, Bullo F, 2021, Stochastic Strategies for Robotic Surveillance as Stackelberg Games, IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, Vol: 8, Pages: 769-780, ISSN: 2325-5870
- Author Web Link
- Cite
- Citations: 1
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.
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.
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.
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.
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.
Chandan R, Paccagnan D, Ferguson BL, et 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.
Paccagnan D, Gentile B, Parise F, et 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.
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.
Gentile B, Paccagnan D, Ogunsola B, et 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.
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.
Burger G, Paccagnan D, Gentile B, et 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.
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.
Paccagnan D, Gentile B, Parise F, et 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.
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.
Jorgensen MJ, Paccagnan D, Poulsen NK, et 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.
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.