2024 [ nach oben ]

Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion ModelsThe 23rd International Conference on Autonomous Agents and Multi-Agent Systems 2024
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.
@inproceedings{friedrich2024market, abstract = {Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.}, author = {Friedrich, Tobias and Göbel, Andreas and Klodt, Nicolas and Krejca, Martin S. and Pappik, Marcus}, booktitle = {The 23rd International Conference on Autonomous Agents and Multi-Agent Systems}, keywords = {aamas andreasgoebel marcuspappik martinskrejca nicolasklodt tobiasfriedrich year2024}, title = {From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion Models}, year = 2024 }

2023 [ nach oben ]

Doering, Michelle; Peters, Jannik Margin of Victory for Weighted Tournament SolutionsAutonomous Agents and Multi-Agent Systems (AAMAS) 2023: 1716–1724
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
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}, pages = {1716–1724}, 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: 2222–2230
[ Abstract ] [ BibTeX ] [ URL ] [ 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 michelledoering year2023}, pages = {2222–2230}, 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: 2899–2901
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Schelling games model the wide-spread phenomenon of residential segregation in metropolitan areas from a game-theoretic point of view. In these games agents of different types each strategically select a node on a given graph that models the residential area to maximize their individual utility. The latter solely depends on the types of the agents on neighboring nodes and it has been a standard assumption to consider utility functions that are monotone in the number of same-type neighbors. This simplifying assumption has recently been challenged since sociological poll results suggest that real-world agents actually favor diverse neighborhoods. We contribute to the recent endeavor of investigating residential segregation models with realistic agent behavior by studying Jump Schelling Games with agents having a single-peaked utility function. In such games, there are empty nodes in the graph and agents can strategically jump to such nodes to improve their utility. We investigate the existence of equilibria and show that they exist under specific conditions. Contrasting this, we prove that even on simple topologies like paths or rings such stable states are not guaranteed to exist. Regarding the game dynamics, we show that improving response cycles exist independently of the position of the peak in the utility function. Moreover, we show high almost tight bounds on the Price of Anarchy and the Price of Stability with respect to the recently proposed degree of integration, which counts the number of agents with a diverse neighborhood and which serves as a proxy for measuring the segregation strength. Last but not least, we show that computing a beneficial state with high integration is NP-complete and, as a novel conceptual contribution, we also show that it is NP-hard to decide if an equilibrium state can be found via improving response dynamics starting from a given initial state.
@inproceedings{friedrich2023singlepeaked, abstract = {Schelling games model the wide-spread phenomenon of residential segregation in metropolitan areas from a game-theoretic point of view. In these games agents of different types each strategically select a node on a given graph that models the residential area to maximize their individual utility. The latter solely depends on the types of the agents on neighboring nodes and it has been a standard assumption to consider utility functions that are monotone in the number of same-type neighbors. This simplifying assumption has recently been challenged since sociological poll results suggest that real-world agents actually favor diverse neighborhoods. We contribute to the recent endeavor of investigating residential segregation models with realistic agent behavior by studying Jump Schelling Games with agents having a single-peaked utility function. In such games, there are empty nodes in the graph and agents can strategically jump to such nodes to improve their utility. We investigate the existence of equilibria and show that they exist under specific conditions. Contrasting this, we prove that even on simple topologies like paths or rings such stable states are not guaranteed to exist. Regarding the game dynamics, we show that improving response cycles exist independently of the position of the peak in the utility function. Moreover, we show high almost tight bounds on the Price of Anarchy and the Price of Stability with respect to the recently proposed degree of integration, which counts the number of agents with a diverse neighborhood and which serves as a proxy for measuring the segregation strength. Last but not least, we show that computing a beneficial state with high integration is NP-complete and, as a novel conceptual contribution, we also show that it is NP-hard to decide if an equilibrium state can be found via improving response dynamics starting from a given initial state.}, author = {Friedrich, Tobias and Lenzner, Pascal and Molitor, Louise and Seifert, Lars}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas larsseifert louisemolitor pascallenzner tobiasfriedrich year2023}, pages = {2899–2901}, title = {Single-Peaked Jump Schelling Games}, year = 2023 }

Cseh, Ágnes; Führlich, Pascal; Lenzner, Pascal The Swiss GambitAutonomous Agents and Multi-Agent Systems (AAMAS) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
In each round of a Swiss-system tournament, players of similar score are paired against each other. An intentional early loss therefore might lead to weaker opponents in later rounds and thus to a better final tournament result a phenomenon known as the Swiss Gambit. To the best of our knowledge it is an open question whether this strategy can actually work. This paper provides answers based on an empirical agent-based analysis for the most prominent application area of the Swiss-system format, namely chess tournaments. We simulate realistic tournaments by employing the official FIDE pairing system for computing the player pairings in each round. We show that even though gambits are widely possible in Swiss-system chess tournaments, profiting from them requires a high degree of predictability of match results. Moreover, even if a Swiss Gambit succeeds, the obtained improvement in the final ranking is limited. Our experiments prove that counting on a Swiss Gambit is indeed a lot more of a risky gambit than a reliable strategy to improve the final rank.
@inproceedings{cseh2023swiss, abstract = {In each round of a Swiss-system tournament, players of similar score are paired against each other. An intentional early loss therefore might lead to weaker opponents in later rounds and thus to a better final tournament result a phenomenon known as the Swiss Gambit. To the best of our knowledge it is an open question whether this strategy can actually work. This paper provides answers based on an empirical agent-based analysis for the most prominent application area of the Swiss-system format, namely chess tournaments. We simulate realistic tournaments by employing the official FIDE pairing system for computing the player pairings in each round. We show that even though gambits are widely possible in Swiss-system chess tournaments, profiting from them requires a high degree of predictability of match results. Moreover, even if a Swiss Gambit succeeds, the obtained improvement in the final ranking is limited. Our experiments prove that counting on a Swiss Gambit is indeed a lot more of a risky gambit than a reliable strategy to improve the final rank.}, author = {Cseh, Ágnes and Führlich, Pascal and Lenzner, Pascal}, booktitle = {Autonomous Agents and Multi-Agent 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: 215–223
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
The complex interactions between algorithmic trading agents can have a severe influence on the functioning of our economy, as witnessed by recent banking crises and trading anomalies. A common phenomenon in these situations are fire sales, a contagious process of asset sales that trigger further sales. We study the existence and structure of equilibria in a game-theoretic model of fire sales. We prove that for a wide parameter range (e.g., convex price impact functions), equilibria exist and form a complete lattice. This is contrasted with a non-existence result for concave price impact functions. Moreover, we study the convergence of best-response dynamics towards equilibria when they exist. In general, best-response dynamics may cycle. However, in many settings they are guaranteed to converge to the socially optimal equilibrium when starting from a natural initial state. Moreover, we discuss a simplified variant of the dynamics that is less informationally demanding and converges to the same equilibria. We compare the dynamics in terms of convergence speed.
@inproceedings{bertschinger2023equilibria, abstract = {The complex interactions between algorithmic trading agents can have a severe influence on the functioning of our economy, as witnessed by recent banking crises and trading anomalies. A common phenomenon in these situations are fire sales, a contagious process of asset sales that trigger further sales. We study the existence and structure of equilibria in a game-theoretic model of fire sales. We prove that for a wide parameter range (e.g., convex price impact functions), equilibria exist and form a complete lattice. This is contrasted with a non-existence result for concave price impact functions. Moreover, we study the convergence of best-response dynamics towards equilibria when they exist. In general, best-response dynamics may cycle. However, in many settings they are guaranteed to converge to the socially optimal equilibrium when starting from a natural initial state. Moreover, we discuss a simplified variant of the dynamics that is less informationally demanding and converges to the same equilibria. We compare the dynamics in terms of convergence speed.}, author = {Bertschinger, Nils and Hoefer, Martin and Krogmann, Simon and Lenzner, Pascal and Schuldenzucker, Steffen and Wilhelmi, Lisa}, booktitle = {Autonomous Agents and Multiagent Systems (AAMAS)}, keywords = {aamas pascallenzner simonkrogmann year2023}, pages = {215-223}, 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 ] [ 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 ] [ 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 ] [ 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 ] [ 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 ] [ 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 ] [ 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 }