2023 [ nach oben ]

Doering, Michelle; Peters, Jannik Margin of Victory for Weighted Tournament SolutionsAutonomous Agents and Multi-Agent Systems (AAMAS) 2023
[ Abstract ] [ BibTeX ]
 
Determining how close a winner of an election is to becoming a loser, or distinguishing between different possible winners of an election, are major problems in computational social choice. We tackle these problems for so-called weighted tournament solutions by generalizing the notion of margin of victory (MoV) for tournament solutions by Brill et al. [2022][Artificial Intelligence] to weighted tournament solutions. For these, the MoV of a winner (resp. loser) is the total weight that needs to be changed in the tournament to make them a loser (resp. winner). We study three weighted tournament solutions: Borda’s rule, the weighted Uncovered Set, and Split Cycle. For all three rules, we determine whether the MoV for winners and non-winners is tractable and give upper and lower bounds on the possible values of the MoV. Further, we axiomatically study and generalize properties from the unweighted tournament setting to weighted tournaments.
@inproceedings{doering2023margin, abstract = {Determining how close a winner of an election is to becoming a loser, or distinguishing between different possible winners of an election, are major problems in computational social choice. We tackle these problems for so-called weighted tournament solutions by generalizing the notion of margin of victory (MoV) for tournament solutions by Brill et al. [2022][Artificial Intelligence] to weighted tournament solutions. For these, the MoV of a winner (resp. loser) is the total weight that needs to be changed in the tournament to make them a loser (resp. winner). We study three weighted tournament solutions: Borda’s rule, the weighted Uncovered Set, and Split Cycle. For all three rules, we determine whether the MoV for winners and non-winners is tractable and give upper and lower bounds on the possible values of the MoV. Further, we axiomatically study and generalize properties from the unweighted tournament setting to weighted tournaments.}, author = {Doering, Michelle and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {aamas michelledoering year2023}, title = {Margin of Victory for Weighted Tournament Solutions}, year = 2023 }

Deligkas, Argyrios; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed SourceAutonomous Agents and Multi-Agent Systems (AAMAS) 2023
[ Abstract ] [ BibTeX ] [ Download ]
 
We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on three objective functions.In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. Finally, in MaxViralTstep, the goal is to maximize the number of vertices that are infected at a given time step. We perform a thorough complexity theoretic analysis for these three objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of MaxSpread for periodic graphs, are intractable even for very simple underlying graphs.
@inproceedings{deligkas2023being, abstract = {We consider the influence maximization problem over a temporal graph, where there is a single fixed source. We deviate from the standard model of influence maximization, where the goal is to choose the set of most influential vertices. Instead, in our model we are given a fixed vertex, or source, and the goal is to find the best time steps to transmit so that the influence of this vertex is maximized. We frame this problem as a spreading process that follows a variant of the susceptible-infected-susceptible (SIS) model and we focus on three objective functions.In the MaxSpread objective, the goal is to maximize the total number of vertices that get infected at least once. In the MaxViral objective, the goal is to maximize the number of vertices that are infected at the same time step. Finally, in MaxViralTstep, the goal is to maximize the number of vertices that are infected at a given time step. We perform a thorough complexity theoretic analysis for these three objectives over three different scenarios: (1) the unconstrained setting where the source can transmit whenever it wants; (2) the window-constrained setting where the source has to transmit at either a predetermined, or a shifting window; (3) the periodic setting where the temporal graph has a small period. We prove that all of these problems, with the exception of MaxSpread for periodic graphs, are intractable even for very simple underlying graphs.}, author = {Deligkas, Argyrios and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {sys:relevantfor:ae aamas georgeskretas year2023}, title = {Being an Influencer is Hard: The Complexity of Influence Maximization in Temporal Graphs with a Fixed Source}, year = 2023 }

Friedrich, Tobias; Lenzner, Pascal; Molitor, Louise; Seifert, Lars Single-Peaked Jump Schelling GamesAutonomous Agents and Multiagent Systems (AAMAS) 2023
[ BibTeX ]
 
@article{friedrich2023singlepeaked, author = {Friedrich, Tobias and Lenzner, Pascal and Molitor, Louise and Seifert, Lars}, journal = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas larsseifert louisemolitor pascallenzner tobiasfriedrich year2023}, title = {Single-Peaked Jump Schelling Games}, year = 2023 }

Cseh, Ágnes; Führlich, Pascal; Lenzner, Pascal The Swiss GambitAutonomous Agents and Multiagent Systems (AAMAS) 2023
[ BibTeX ]
 
@article{cseh2023swiss, author = {Cseh, Ágnes and Führlich, Pascal and Lenzner, Pascal}, journal = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh pascallenzner year2023}, title = {The Swiss Gambit}, year = 2023 }

Bertschinger, Nils; Hoefer, Martin; Krogmann, Simon; Lenzner, Pascal; Schuldenzucker, Steffen; Wilhelmi, Lisa Equilibria and Convergence in Fire Sale GamesAutonomous Agents and Multiagent Systems (AAMAS) 2023
[ BibTeX ]
 
@article{bertschinger2023equilibria, author = {Bertschinger, Nils and Hoefer, Martin and Krogmann, Simon and Lenzner, Pascal and Schuldenzucker, Steffen and Wilhelmi, Lisa}, journal = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas pascallenzner simonkrogmann year2023}, title = {Equilibria and Convergence in Fire Sale Games}, year = 2023 }

2022 [ nach oben ]

Cseh, Ágnes; Peters, Jannik Three-Dimensional Popular Matching with Cyclic PreferencesAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 77–87
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.
@inproceedings{cseh2022threedimensional, abstract = {Two actively researched problem settings in matchings under preferences are popular matchings and the three-dimensional stable matching problem with cyclic preferences. In this paper, we apply the optimality notion of the first topic to the input characteristics of the second one. We investigate the connection between stability, popularity, and their strict variants, strong stability and strong popularity in three-dimensional instances with cyclic preferences. Furthermore, we also derive results on the complexity of these problems when the preferences are derived from master lists.}, author = {Cseh, Ágnes and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {aamas agnescseh jannikpeters year2022}, pages = {77–87}, title = {Three-Dimensional Popular Matching with Cyclic Preferences}, year = 2022 }

Berenbrink, Petra; Hoefer, Martin; Kaaser, Dominik; Lenzner, Pascal; Rau, Malin; Schmand, Daniel Asynchronous Opinion Dynamics in Social NetworksAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 109–117
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of \(\mathcal{O(n |E|^2 (\varepsilon/\delta)^2)\) on the expected number of opinion updates until convergence, where |E| is the number of edges of the social network. For the complete social network we show a bound of \( \mathcal{O(n^3(n^2 + (\varepsilon/\delta)^2)) \) that represents a major improvement over the previously best upper bound of \( \mathcal{O(n^9(\varepsilon/\delta)^2) \). Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.
@inproceedings{berenbrink2022asynchronous, abstract = {Opinion spreading in a society decides the fate of elections, the success of products, and the impact of political or social movements. The model by Hegselmann and Krause is a well-known theoretical model to study such opinion formation processes in social networks. In contrast to many other theoretical models, it does not converge towards a situation where all agents agree on the same opinion. Instead, it assumes that people find an opinion reasonable if and only if it is close to their own. The system converges towards a stable situation where agents sharing the same opinion form a cluster, and agents in different clusters do not influence each other. We focus on the social variant of the Hegselmann-Krause model where agents are connected by a social network and their opinions evolve in an iterative process. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion. By this, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network. We show that such opinion dynamics with random agent activation are guaranteed to converge for any social network. We provide an upper bound of \(\mathcal{O}(n |E|^2 (\varepsilon/\delta)^2)\) on the expected number of opinion updates until convergence, where |E| is the number of edges of the social network. For the complete social network we show a bound of \( \mathcal{O}(n^3(n^2 + (\varepsilon/\delta)^2)) \) that represents a major improvement over the previously best upper bound of \( \mathcal{O}(n^9(\varepsilon/\delta)^2) \). Our bounds are complemented by simulations that indicate asymptotically matching lower bounds.}, author = {Berenbrink, Petra and Hoefer, Martin and Kaaser, Dominik and Lenzner, Pascal and Rau, Malin and Schmand, Daniel}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {aamas pascallenzner year2022}, pages = {109–117}, title = {Asynchronous Opinion Dynamics in Social Networks}, year = 2022 }

Cseh, Ágnes; Friedrich, Tobias; Peters, Jannik Pareto Optimal and Popular House Allocation with Lower and Upper QuotasAutonomous Agents and Multi-Agent Systems (AAMAS) 2022: 300–308
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.
@inproceedings{cseh2022pareto, abstract = {In the house allocation problem with lower and upper quotas, we are given a set of applicants and a set of projects. Each applicant has a strictly ordered preference list over the projects, while the projects are equipped with a lower and an upper quota. A feasible matching assigns the applicants to the projects in such a way that a project is either matched to no applicant or to a number of applicants between its lower and upper quota. In this model we study two classic optimality concepts: Pareto optimality and popularity. We show that finding a popular matching is hard even if the maximum lower quota is 2 and that finding a perfect Pareto optimal matching, verifying Pareto optimality, and verifying popularity are all NP-complete even if the maximum lower quota is 3. We complement the last three negative results by showing that the problems become polynomial-time solvable when the maximum lower quota is 2, thereby answering two open questions of Cechlárová and Fleiner. Finally, we also study the parameterized complexity of all four mentioned problems.}, author = {Cseh, Ágnes and Friedrich, Tobias and Peters, Jannik}, booktitle = {Autonomous Agents and Multi-Agent Systems (AAMAS)}, keywords = {aamas agnescseh jannikpeters tobiasfriedrich year2022}, pages = {300–308}, title = {Pareto Optimal and Popular House Allocation with Lower and Upper Quotas}, year = 2022 }

2021 [ nach oben ]

Kraiczy, Sonja; Cseh, Ágnes; Manlove, David On Weakly and Strongly Popular RankingsAutonomous Agents and Multiagent Systems (AAMAS) 2021: 1563–1565
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly-ordered list of all candidates. A popular ranking pi of the candidates is at least as good as any other ranking sigma in the following sense: if we compare pi to sigma, at least half of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity---as applied to popular matchings, a well-established topic in computational social choice---is stricter, because it requires at least half of the voters who are not indifferent between pi and sigma to prefer pi. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results by van Zylen et al. We also point out connections to the famous open problem of finding a Kemeny consensus with 3 voters.
@inproceedings{kraiczy2021weakly, abstract = {Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly-ordered list of all candidates. A popular ranking pi of the candidates is at least as good as any other ranking sigma in the following sense: if we compare pi to sigma, at least half of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity—as applied to popular matchings, a well-established topic in computational social choice—is stricter, because it requires at least half of the voters who are not indifferent between pi and sigma to prefer pi. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results by van Zylen et al. We also point out connections to the famous open problem of finding a Kemeny consensus with 3 voters.}, author = {Kraiczy, Sonja and Cseh, Ágnes and Manlove, David}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh davidfmanlove sonjakraiczy year2021}, pages = {1563-1565}, title = {On Weakly and Strongly Popular Rankings}, year = 2021 }

Aziz, Haris; Chan, Hau; Cseh, Ágnes; Li, Bo; Ramezani, Fahimeh; Wang, Chenhao Multi-Robot Task Allocation—Complexity and ApproximationAutonomous Agents and Multiagent Systems (AAMAS) 2021: 133–141
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.
@inproceedings{aziz2021multirobot, abstract = {Multi-robot task allocation is one of the most fundamental classes of problems in robotics and is crucial for various real-world robotic applications such as search, rescue and area exploration. We consider the Single-Task robots and Multi-Robot tasks Instantaneous Assignment (ST-MR-IA) setting where each task requires at least a certain number of robots and each robot can work on at most one task and incurs an operational cost for each task. Our aim is to consider a natural computational problem of allocating robots to complete the maximum number of tasks subject to budget constraints. We consider budget constraints of three different kinds: (1) total budget, (2) task budget, and (3) robot budget. We provide a detailed complexity analysis including results on approximations as well as polynomial-time algorithms for the general setting and important restricted settings.}, author = {Aziz, Haris and Chan, Hau and Cseh, Ágnes and Li, Bo and Ramezani, Fahimeh and Wang, Chenhao}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas agnescseh boli chenhaowang fahimehramezani harisaziz hauchan year2021}, pages = {133-141}, title = {Multi-Robot Task Allocation—Complexity and Approximation}, year = 2021 }

2019 [ nach oben ]

Feldotto, Matthias; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander From Hotelling to Load Balancing: Approximation and the Principle of Minimum DifferentiationAutonomous Agents and Multiagent Systems (AAMAS) 2019: 1949–1951
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Competing firms tend to select similar locations for their stores. This phenomenon, called the principle of minimum differentiation, was captured by Hotelling with a landmark model of spatial competition but is still the object of an ongoing scientific debate. Although consistently observed in practice, many more realistic variants of Hotelling's model fail to support minimum differentiation or do not have pure equilibria at all. In particular, it was recently proven for a generalized model which incorporates negative network externalities and which contains Hotelling's model and classical selfish load balancing as special cases, that the unique equilibria do not adhere to minimum differentiation. Furthermore, it was shown that for a significant parameter range pure equilibria do not exist. We derive a sharp contrast to these previous results by investigating Hotelling's model with negative network externalities from an entirely new angle: approximate pure subgame perfect equilibria. This approach allows us to prove analytically and via agent-based simulations that approximate equilibria having good approximation guarantees and that adhere to minimum differentiation exist for the full parameter range of the model. Moreover, we show that the obtained approximate equilibria have high social welfare.
@inproceedings{feldotto2019hotelling, abstract = {Competing firms tend to select similar locations for their stores. This phenomenon, called the principle of minimum differentiation, was captured by Hotelling with a landmark model of spatial competition but is still the object of an ongoing scientific debate. Although consistently observed in practice, many more realistic variants of Hotelling's model fail to support minimum differentiation or do not have pure equilibria at all. In particular, it was recently proven for a generalized model which incorporates negative network externalities and which contains Hotelling's model and classical selfish load balancing as special cases, that the unique equilibria do not adhere to minimum differentiation. Furthermore, it was shown that for a significant parameter range pure equilibria do not exist. We derive a sharp contrast to these previous results by investigating Hotelling's model with negative network externalities from an entirely new angle: approximate pure subgame perfect equilibria. This approach allows us to prove analytically and via agent-based simulations that approximate equilibria having good approximation guarantees and that adhere to minimum differentiation exist for the full parameter range of the model. Moreover, we show that the obtained approximate equilibria have high social welfare.}, author = {Feldotto, Matthias and Lenzner, Pascal and Molitor, Louise and Skopalik, Alexander}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas alexanderskopalik louisemolitor matthiasfeldotto pascallenzner year2019}, pages = {1949-1951}, title = {From Hotelling to Load Balancing: Approximation and the Principle of Minimum Differentiation}, year = 2019 }