TY - JOUR AU - Li, Bin AU - Hao, Dong AU - Zhao, Dengji TI - Diffusion auction design with transaction costs JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 38 PY - 2024 IS - 1 PG - 28 SN - 1387-2532 DO - 10.1007/s10458-023-09631-8 UR - https://m2.mtmt.hu/api/publication/34601386 ID - 34601386 AB - We study multi-unit auctions powered by intermediated markets, where all transactions are processed by intermediaries and incur certain costs. Each intermediary in the market owns a private set of buyers and all intermediaries are networked with each other. Our goal is to incentivize the intermediaries to share the auction information to individuals they can reach, including their private buyers and neighboring intermediaries, so that more potential buyers are able to participate in the auction. To this end, we build a diffusion-based auction framework to handle the transaction costs and the strategic interactions between intermediaries. The classic Vickrey-Clarke-Groves (VCG) mechanism within the scenario can obtain the maximum social welfare, but it can decrease the seller's revenue or even lead to a deficit. To overcome the revenue issue, we develop two deficit reduction strategies, based on which a family of diffusion auctions called Critical Neighborhood Auctions (CNA) is identified. The CNA not only maximizes the social welfare, but also eliminates all the seller's deficits. Moreover, the revenue given by the CNA is no less than the revenue given by the VCG mechanism with/without intermediaries. This is the first set of diffusion auctions with welfare and revenue advantages that can handle multiple items and transaction costs. LA - English DB - MTMT ER - TY - JOUR AU - Berger, Cyrille AU - Doherty, Patrick AU - Rudol, Piotr AU - Wzorek, Mariusz TI - RGS^\oplus : RDF graph synchronization for collaborative robotics JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 2 SP - & SN - 1387-2532 DO - 10.1007/s10458-023-09629-2 UR - https://m2.mtmt.hu/api/publication/34433175 ID - 34433175 AB - In the context of collaborative robotics, distributed situation awareness is essential for supporting collective intelligence in teams of robots and human agents where it can be used for both individual and collective decision support. This is particularly important in applications pertaining to emergency rescue and crisis management. During operational missions, data and knowledge is gathered incrementally and in different ways by heterogeneous robots and humans. The purpose of this paper is to describe an RDF Graph Synchronization System called RGS ^\oplus ⊕ . It is assumed that a dynamic set of agents provide or retrieve knowledge stored in their local RDF Graphs which are continuously synchronized between agents. The RGS ^\oplus ⊕ System was designed to handle unreliable communication and does not rely on a static centralized infrastructure. It is capable of synchronizing knowledge as timely as possible and allows agents to access knowledge while it is incrementally acquired. A deeper empirical analysis of the RGS ^\oplus ⊕ System is provided that shows both its efficiency and efficacy. LA - English DB - MTMT ER - TY - JOUR AU - Zivan, Roie AU - Rachmut, Ben AU - Perry, Omer AU - Yeoh, William TI - Effect of asynchronous execution and imperfect communication on max-sum belief propagation JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 2 PG - 28 SN - 1387-2532 DO - 10.1007/s10458-023-09621-w UR - https://m2.mtmt.hu/api/publication/34291823 ID - 34291823 AB - Max-sum is a version of belief propagation that was adapted for solving distributed constraint optimization problems. It has been studied theoretically and empirically, extended to versions that improve solution quality and converge rapidly, and is applicable to multiple distributed applications. The algorithm was presented both as synchronous and asynchronous algorithms. However, neither the differences in the performance of the two execution versions nor the implications of imperfect communication (i.e., massage delay and message loss) on the two versions have been investigated to the best of our knowledge. We contribute to the body of knowledge on Max-sum by: (1) Establishing the theoretical differences between the two execution versions of the algorithm, focusing on the construction of beliefs; (2) Empirically evaluating the differences between the solutions generated by the two versions of the algorithm, with and without message delay or loss; and (3) Establishing both theoretically and empirically the positive effect of damping on reducing the differences between the two versions. Our results indicate that, in contrast to recent published results indicating that message latency has a drastic (positive) effect on the performance of distributed local search algorithms, the effect of imperfect communication on Damped Max-sum (DMS) is minor. The version of Max-sum that includes both damping and splitting of function nodes converges to high quality solutions very fast, even when a large percentage of the messages sent by agents do not arrive at their destinations. Moreover, the quality of solutions in the different versions of DMS is dependent of the number of messages that were received by the agents, regardless of the amount of time they were delayed or if these messages are only a portion of the total number of messages that was sent by the agents. LA - English DB - MTMT ER - TY - JOUR AU - Qiao, Jianglin AU - de Jonge, Dave AU - Zhang, Dongmo AU - Simoff, Simeon AU - Sierra, Carles AU - Du, Bo TI - Price of anarchy of traffic assignment with exponential cost functions JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 2 PG - 32 SN - 1387-2532 DO - 10.1007/s10458-023-09625-6 UR - https://m2.mtmt.hu/api/publication/34266258 ID - 34266258 AB - The rapid evolution of technology in connected automated and autonomous vehicles offers immense potential for revolutionizing future intelligent traffic control and management. This potential is exemplified by the diverse range of control paradigms, ranging from self-routing to centralized control. However, the selection among these paradigms is beyond technical consideration but a delicate balance between autonomous decision-making and holistic system optimization. A pivotal quantitative parameter in navigating this balance is the concept of the "price of anarchy" (PoA) inherent in autonomous decision frameworks. This paper analyses the price of anarchy for road networks with traffic of CAV. We model a traffic network as a routing game in which vehicles are selfish agents who choose routes to travel autonomously to minimize travel delays caused by road congestion. Unlike existing research in which the latency function of road congestion was based on polynomial functions like the well-known BPR function, we focus on routing games where an exponential function can specify the latency of road traffic. We first calculate a tight upper bound for the price of anarchy for this class of games and then compare this result with the tight upper bound of the PoA for routing games with the BPR latency function. The comparison shows that as long as the traffic volume is lower than the road capacity, the tight upper bound of the PoA of the games with the exponential function is lower than the corresponding value with the BPR function. Finally, numerical results based on real-world traffic data demonstrate that the exponential function can approximate road latency as close as the BPR function with even tighter exponential parameters, which results in a relatively lower upper bound. LA - English DB - MTMT ER - TY - JOUR AU - Hayes, Conor F. AU - Reymond, Mathieu AU - Roijers, Diederik M. AU - Howley, Enda AU - Mannion, Patrick TI - Monte Carlo tree search algorithms for risk-aware and multi-objective reinforcement learning JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 2 PG - 37 SN - 1387-2532 DO - 10.1007/s10458-022-09596-0 UR - https://m2.mtmt.hu/api/publication/34235967 ID - 34235967 AB - In many risk-aware and multi-objective reinforcement learning settings, the utility of the user is derived from a single execution of a policy. In these settings, making decisions based on the average future returns is not suitable. For example, in a medical setting a patient may only have one opportunity to treat their illness. Making decisions using just the expected future returns-known in reinforcement learning as the value-cannot account for the potential range of adverse or positive outcomes a decision may have. Therefore, we should use the distribution over expected future returns differently to represent the critical information that the agent requires at decision time by taking both the future and accrued returns into consideration. In this paper, we propose two novel Monte Carlo tree search algorithms. Firstly, we present a Monte Carlo tree search algorithm that can compute policies for nonlinear utility functions (NLU-MCTS) by optimising the utility of the different possible returns attainable from individual policy executions, resulting in good policies for both risk-aware and multi-objective settings. Secondly, we propose a distributional Monte Carlo tree search algorithm (DMCTS) which extends NLU-MCTS. DMCTS computes an approximate posterior distribution over the utility of the returns, and utilises Thompson sampling during planning to compute policies in risk-aware and multi-objective settings. Both algorithms outperform the state-of-the-art in multi-objective reinforcement learning for the expected utility of the returns. LA - English DB - MTMT ER - TY - JOUR AU - Jalota, D. AU - Solovey, K. AU - Tsao, M. AU - Zoepf, S. AU - Pavone, M. TI - Balancing fairness and efficiency in traffic routing via interpolated traffic assignment JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 2 SN - 1387-2532 DO - 10.1007/s10458-023-09616-7 UR - https://m2.mtmt.hu/api/publication/34174837 ID - 34174837 N1 - Export Date: 4 October 2023 Correspondence Address: Jalota, D.; Institute for Computational and Mathematical Engineering, 450 Serra Mall, United States; email: djalota@stanford.edu LA - English DB - MTMT ER - TY - JOUR AU - Dinh, Le Cong AU - Mguni, David Henry AU - Tran-Thanh, Long AU - Wang, Jun AU - Yang, Yaodong TI - Online Markov decision processes with non-oblivious strategic adversary JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 1 PG - 32 SN - 1387-2532 DO - 10.1007/s10458-023-09599-5 UR - https://m2.mtmt.hu/api/publication/33892555 ID - 33892555 AB - We study a novel setting in Online Markov Decision Processes (OMDPs) where the loss function is chosen by a non-oblivious strategic adversary who follows a no-external regret algorithm. In this setting, we first demonstrate that MDP-Expert, an existing algorithm that works well with oblivious adversaries can still apply and achieve a policy regret bound of O( root T log(L) + tau(2)root T log(| A|)) where L is the size of adversary's pure strategy set and IAI denotes the size of agent's action space. Considering real-world games where the support size of a NE is small, we further propose a new algorithm: MDP-Online Oracle Expert (MDP-OOE), that achieves a policy regret bound of O( root T log(L) + tau(2)root Tk log(k)) where k depends only on the support size of the NE. MDP-OOE leverages the key benefit of Double Oracle in game theory and thus can solve games with prohibitively large action space. Finally, to better understand the learning dynamics of no-regret methods, under the same setting of no-external regret adversary in OMDPs, we introduce an algorithm that achieves last-round convergence to a NE result. To our best knowledge, this is the first work leading to the last iteration result in OMDPs. LA - English DB - MTMT ER - TY - JOUR AU - Boehmer, Niclas AU - Koana, Tomohiro AU - Niedermeier, Rolf TI - A refined complexity analysis of fair districting over graphs JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 1 PG - 37 SN - 1387-2532 DO - 10.1007/s10458-022-09594-2 UR - https://m2.mtmt.hu/api/publication/33848669 ID - 33848669 AB - We study the NP-hard Fair Connected Districting problem recently proposed by Stoica et al. [AAMAS 2020]: Partition a vertex-colored graph into k connected components (subsequently referred to as districts) so that in every district the most frequent color occurs at most a given number of times more often than the second most frequent color. Fair Connected Districting is motivated by various real-world scenarios where agents of different types, which are one-to-one represented by nodes in a network, have to be partitioned into disjoint districts. Herein, one strives for "fair districts " without any type being in a dominating majority in any of the districts. This is to e.g. prevent segregation or political domination of some political party. We conduct a fine-grained analysis of the (parameterized) computational complexity of Fair Connected Districting. In particular, we prove that it is polynomial-time solvable on paths, cycles, stars, and caterpillars, but already becomes NP-hard on trees. Motivated by the latter negative result, we perform a parameterized complexity analysis with respect to various graph parameters including treewidth, and problem-specific parameters, including, the numbers of colors and districts. We obtain a rich and diverse, close to complete picture of the corresponding parameterized complexity landscape (that is, a classification along the complexity classes FPT, XP, W[1]-hard, and para-NP-hard). LA - English DB - MTMT ER - TY - JOUR AU - Dodevska, Zorica AU - Petrovic, Andrija AU - Radovanovic, Sandro AU - Delibasic, Boris TI - Changing criteria weights to achieve fair VIKOR ranking: a postprocessing reranking approach JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 37 PY - 2023 IS - 1 PG - 44 SN - 1387-2532 DO - 10.1007/s10458-022-09591-5 UR - https://m2.mtmt.hu/api/publication/33502919 ID - 33502919 AB - Ranking is a prerequisite for making decisions, and therefore it is a very responsible and frequently applied activity. This study considers fairness issues in a multi-criteria decision-making (MCDM) method called VIKOR (in Serbian language-VIsekriterijumska optimizacija i KOmpromisno Resenje, which means Multiple Criteria Optimization and Compromise Solution). The method is specific because of its original property to search for the first-ranked compromise solutions based on the parameter v. The VIKOR method was modified in this paper to rank all the alternatives and find compromise solutions for each rank. Then, the obtained ranks were used to satisfy fairness constraints (i.e., the desired level of disparate impact) by criteria weights optimization. We built three types of mathematical models depending on decision makers' (DMs') preferences regarding the definition of the compromise parameter v. Metaheuristic optimization algorithms were explored in order to minimize the differences in VIKOR ranking prior to and after optimization. The proposed postprocessing reranking approach ensures fair ranking (i.e., the ranking without discrimination). The conducted experiments involve three real-life datasets of different sizes, well-known in the literature. The comparisons of the results with popular fair ranking algorithms include a comparative examination of several rank-based metrics intended to measure accuracy and fairness that indicate a high-quality competence of the suggested approach. The most significant contributions include developing automated and adaptive optimization procedures with the possibility of further adjustments following DMs' preferences and matching fairness metrics with traditional MCDM goals in a comprehensive full VIKOR ranking. LA - English DB - MTMT ER - TY - JOUR AU - Stolba, Michal AU - Urbanovska, Michaela AU - Komenda, Antonin TI - Privacy leakage of search-based multi-agent planning algorithms JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 36 PY - 2022 IS - 2 PG - 32 SN - 1387-2532 DO - 10.1007/s10458-022-09568-4 UR - https://m2.mtmt.hu/api/publication/33324168 ID - 33324168 AB - Privacy preservation has become one of the crucial research topics in multi-agent planning. A number of techniques to preserve private information throughout the planning process have emerged. One major difficulty of such research is the comparison of properties related to privacy among such techniques. A metric allowing for comparison of such privacy preservation was introduced only recently, having a number of drawbacks such as prohibitive computational complexity. In this work we strengthen the theoretical foundations and simplify the metric in order to be practically usable. Moreover, we test the usability of the metric in an analysis of various techniques in multi-agent heuristic computation and search, determining which are the most beneficial in terms of privacy preservation. We also evaluate the techniques in terms of the classical IPC score to assess their impact on the overall planning performance. The results are somewhat surprising and show that extracting any privacy-related information even from the simplest variant of heuristic search is a very complicated task. Existing techniques such as distributed heuristic and sending only relevant states is shown to reduce the privacy leakage even more. LA - English DB - MTMT ER -