2024 [ nach oben ]

Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander; Uetz, Marc; Vos, Marnix C. Equilibria in Two-Stage Facility Location with Atomic ClientsInternational Joint Conference on Artificial Intelligence (IJCAI) 2024
[ Abstract ] [ BibTeX ]
 
We consider competitive facility location as a two-stage multi-agent system with two types of clients. For a given host graph with weighted clients on the vertices, first facility agents strategically select vertices for opening their facilities. Then, the clients strategically select which of the opened facilities in their neighborhood to patronize. Facilities want to attract as much client weight as possible, clients want to minimize congestion on the chosen facility. All recently studied versions of this model assume that clients can split their weight strategically. We consider clients with unsplittable weights, but allow mixed strategies. So clients may randomize over which facility to patronize. Besides modeling a natural client behavior, this subtle change yields drastic changes, e.g., for a given facility placement, qualitatively different client equilibria are possible. As our main result, we show that pure subgame perfect equilibria always exist if all client weights are identical. For this, we use a novel potential function argument, employing a hierarchical classification of the clients and sophisticated rounding in each step. In contrast, for non-identical clients, we show that deciding the existence of even approximately stable states is computationally intractable. On the positive side, we give a tight bound of 2 on the price of anarchy which implies high social welfare of equilibria, if they exist.
@inproceedings{krogmann2024equilibria, abstract = {We consider competitive facility location as a two-stage multi-agent system with two types of clients. For a given host graph with weighted clients on the vertices, first facility agents strategically select vertices for opening their facilities. Then, the clients strategically select which of the opened facilities in their neighborhood to patronize. Facilities want to attract as much client weight as possible, clients want to minimize congestion on the chosen facility. All recently studied versions of this model assume that clients can split their weight strategically. We consider clients with unsplittable weights, but allow mixed strategies. So clients may randomize over which facility to patronize. Besides modeling a natural client behavior, this subtle change yields drastic changes, e.g., for a given facility placement, qualitatively different client equilibria are possible. As our main result, we show that pure subgame perfect equilibria always exist if all client weights are identical. For this, we use a novel potential function argument, employing a hierarchical classification of the clients and sophisticated rounding in each step. In contrast, for non-identical clients, we show that deciding the existence of even approximately stable states is computationally intractable. On the positive side, we give a tight bound of 2 on the price of anarchy which implies high social welfare of equilibria, if they exist.}, author = {Krogmann, Simon and Lenzner, Pascal and Skopalik, Alexander and Uetz, Marc and Vos, Marnix C.}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai pascallenzner simonkrogmann year2024}, title = {Equilibria in Two-Stage Facility Location with Atomic Clients}, year = 2024 }

2023 [ nach oben ]

Deligkas, Argyrios; Eiben, Eduard; Skretas, George Minimizing Reachability Times on Temporal Graphs via Shifting LabelsInternational Joint Conference on Artificial Intelligence (IJCAI) 2023: 5333–5340
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study how we can accelerate the spreading of information in temporal graphs via delaying operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, the delay of some connections can in fact decrease the time required to reach from some vertex (source) to another vertex (target). We study how we can minimize the maximum time a set of source vertices needs to reach every other vertex of the graph when we are allowed to delay some of the connections of the graph. For one source, we prove that the problem is W[2]-hard and NP-hard, when parameterized by the number of allowed delays. On the other hand, we derive a polynomial-time algorithm for one source and unbounded number of delays. This is the best we can hope for; we show that the problem becomes NP-hard when there are two sources and the number of delays is not bounded. We complement our negative result by providing an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution. Finally, we provide polynomial-time algorithms for several classes of graphs.
@inproceedings{deligkas2023minimizing, abstract = {We study how we can accelerate the spreading of information in temporal graphs via delaying operations; a problem that captures real-world applications varying from information flows to distribution schedules. In a temporal graph there is a set of fixed vertices and the available connections between them change over time in a predefined manner. We observe that, in some cases, the delay of some connections can in fact decrease the time required to reach from some vertex (source) to another vertex (target). We study how we can minimize the maximum time a set of source vertices needs to reach every other vertex of the graph when we are allowed to delay some of the connections of the graph. For one source, we prove that the problem is W[2]-hard and NP-hard, when parameterized by the number of allowed delays. On the other hand, we derive a polynomial-time algorithm for one source and unbounded number of delays. This is the best we can hope for; we show that the problem becomes NP-hard when there are two sources and the number of delays is not bounded. We complement our negative result by providing an FPT algorithm parameterized by the treewidth of the graph plus the lifetime of the optimal solution. Finally, we provide polynomial-time algorithms for several classes of graphs.}, author = {Deligkas, Argyrios and Eiben, Eduard and Skretas, George}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {sys:relevantfor:ae georgeskretas ijcai myown year2023}, pages = {5333–5340}, title = {Minimizing Reachability Times on Temporal Graphs via Shifting Labels}, year = 2023 }

Bilò, Davide; Bilò, Vittorio; Döring, Michelle; Lenzner, Pascal; Molitor, Louise; Schmidt, Jonas Schelling Games with Continuous TypesInternational Joint Conference on Artificial Intelligence (IJCAI) 2023: 2520–2527
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling’s model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants.
@inproceedings{bilo2023continuous, abstract = {In most major cities and urban areas, residents form homogeneous neighborhoods along ethnic or socioeconomic lines. This phenomenon is widely known as residential segregation and has been studied extensively. Fifty years ago, Schelling proposed a landmark model that explains residential segregation in an elegant agent-based way. A recent stream of papers analyzed Schelling’s model using game-theoretic approaches. However, all these works considered models with a given number of discrete types modeling different ethnic groups. We focus on segregation caused by non-categorical attributes, such as household income or position in a political left-right spectrum. For this, we consider agent types that can be represented as real numbers. This opens up a great variety of reasonable models and, as a proof of concept, we focus on several natural candidates. In particular, we consider agents that evaluate their location by the average type-difference or the maximum type-difference to their neighbors, or by having a certain tolerance range for type-values of neighboring agents. We study the existence and computation of equilibria and provide bounds on the Price of Anarchy and Stability. Also, we present simulation results that compare our models and shed light on the obtained equilibria for our variants.}, author = {Bilò, Davide and Bilò, Vittorio and Döring, Michelle and Lenzner, Pascal and Molitor, Louise and Schmidt, Jonas}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai louisemolitor michelledoering pascallenzner year2023}, pages = {2520–2527}, title = {Schelling Games with Continuous Types}, year = 2023 }

Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Gawendowicz, Hans; Klodt, Nicolas; Lenzner, Pascal; Skretas, George Temporal Network Creation GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2023: 2511–2519
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.
@inproceedings{bilo2023temporal, abstract = {Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.}, author = {Bilò, Davide and Cohen, Sarel and Friedrich, Tobias and Gawendowicz, Hans and Klodt, Nicolas and Lenzner, Pascal and Skretas, George}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {georgeskretas hansgawendowicz ijcai nicolasklodt pascallenzner sarelcohen tobiasfriedrich year2023}, pages = {2511–2519}, title = {Temporal Network Creation Games}, year = 2023 }

Gadea Harder, Jonathan; Krogmann, Simon; Lenzner, Pascal; Skopalik, Alexander Strategic Resource Selection with Homophilic AgentsInternational Joint Conference on Artificial Intelligence (IJCAI) 2023: 2701–2709
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The strategic selection of resources by selfish agents is a classic research direction, with Resource Selection Games and Congestion Games as prominent examples. In these games, agents select available resources and their utility then depends on the number of agents using the same resources. This implies that there is no distinction between the agents, i.e., they are anonymous. We depart from this very general setting by proposing Resource Selection Games with heterogeneous agents that strive for joint resource usage with similar agents. So, instead of the number of other users of a given resource, our model considers agents with different types and the decisive feature is the fraction of same-type agents among the users. More precisely, similarly to Schelling Games, there is a tolerance threshold \(\tau \in [0,1]\) which specifies the agents' desired minimum fraction of same-type agents on a resource. Agents strive to select resources where at least a \(\tau\)-fraction of those resources' users have the same type as themselves. For \(\tau=1\), our model generalizes Hedonic Diversity Games with a peak at \(1\). For our general model, we consider the existence and quality of equilibria and the complexity of maximizing social welfare. Additionally, we consider a bounded rationality model, where agents can only estimate the utility of a resource, since they only know the fraction of same-type agents on a given resource, but not the exact numbers. Thus, they cannot know the impact a strategy change would have on a target resource. Interestingly, we show that this type of bounded rationality yields favorable game-theoretic properties and specific equilibria closely approximate equilibria of the full knowledge setting.
@inproceedings{gadeaharder2023strategic, abstract = {The strategic selection of resources by selfish agents is a classic research direction, with Resource Selection Games and Congestion Games as prominent examples. In these games, agents select available resources and their utility then depends on the number of agents using the same resources. This implies that there is no distinction between the agents, i.e., they are anonymous. We depart from this very general setting by proposing Resource Selection Games with heterogeneous agents that strive for joint resource usage with similar agents. So, instead of the number of other users of a given resource, our model considers agents with different types and the decisive feature is the fraction of same-type agents among the users. More precisely, similarly to Schelling Games, there is a tolerance threshold \(\tau \in [0,1]\) which specifies the agents' desired minimum fraction of same-type agents on a resource. Agents strive to select resources where at least a \(\tau\)-fraction of those resources' users have the same type as themselves. For \(\tau=1\), our model generalizes Hedonic Diversity Games with a peak at \(1\). For our general model, we consider the existence and quality of equilibria and the complexity of maximizing social welfare. Additionally, we consider a bounded rationality model, where agents can only estimate the utility of a resource, since they only know the fraction of same-type agents on a given resource, but not the exact numbers. Thus, they cannot know the impact a strategy change would have on a target resource. Interestingly, we show that this type of bounded rationality yields favorable game-theoretic properties and specific equilibria closely approximate equilibria of the full knowledge setting.}, author = {Gadea Harder, Jonathan and Krogmann, Simon and Lenzner, Pascal and Skopalik, Alexander}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai jonathangadeaharder pascallenzner simonkrogmann year2023}, pages = {2701-2709}, title = {Strategic Resource Selection with Homophilic Agents}, year = 2023 }

2022 [ nach oben ]

Bullinger, Martin; Lenzner, Pascal; Melnichenko, Anna Network Creation with Homophilic AgentsInternational Joint Conference on Artificial Intelligence (IJCAI) 2022: 151–157
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.
@inproceedings{bullinger2022network, abstract = {Network Creation Games are an important framework for understanding the formation of real-world networks such as social networks. These games usually assume a set of indistinguishable agents strategically buying edges at a uniform price leading to a network among them. However, in real life, agents are heterogeneous and their relationships often display a bias towards similar agents, say of the same ethnic group. This homophilic behavior on the agent level can then lead to the emergent global phenomenon of social segregation. We initiate the study of Network Creation Games with multiple types of homophilic agents and non-uniform edge cost. Specifically, we introduce and compare two models, focusing on the perception of same-type and different-type neighboring agents, respectively. Despite their different initial conditions, both our theoretical and experimental analysis show that the resulting equilibrium networks are almost identical in the two models, indicating a robust structure of social networks under homophily. Moreover, we investigate the segregation strength of the formed networks and thereby offer new insights on understanding segregation.}, author = {Bullinger, Martin and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {annamelnichenko ijcai pascallenzner year2022}, pages = {151–157}, publisher = {ijcai.org}, title = {Network Creation with Homophilic Agents}, year = 2022 }

Bilò, Davide; Bilò, Vittorio; Lenzner, Pascal; Molitor, Louise Tolerance is Necessary for Stability: Single-Peaked Swap Schelling GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2022: 81–87
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.
@inproceedings{bilo2022tolerance, abstract = {Residential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs.}, author = {Bilò, Davide and Bilò, Vittorio and Lenzner, Pascal and Molitor, Louise}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai louisemolitor pascallenzner year2022}, pages = {81–87}, publisher = {ijcai.org}, title = {Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games}, year = 2022 }

2021 [ nach oben ]

Krogmann, Simon; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander Two-Stage Facility Location Games with Strategic Clients and FacilitiesInternational Joint Conference on Artificial Intelligence (IJCAI) 2021: 292–298
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to her spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting times for getting serviced, where a facility’s waiting time corresponds to its total attracted client weight. We show that subgame perfect equilibria exist and give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients’ behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.
@inproceedings{krogmann2021twostage, abstract = {We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to her spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting times for getting serviced, where a facility’s waiting time corresponds to its total attracted client weight. We show that subgame perfect equilibria exist and give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients’ behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.}, author = {Krogmann, Simon and Lenzner, Pascal and Molitor, Louise and Skopalik, Alexander}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai louisemolitor pascallenzner simonkrogmann year2021}, pages = {292-298}, title = {Two-Stage Facility Location Games with Strategic Clients and Facilities}, year = 2021 }

2020 [ nach oben ]

Echzell, Hagen; Friedrich, Tobias; Lenzner, Pascal; Melnichenko, Anna Flow-Based Network Creation GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2020: 139–145
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is~1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.
@inproceedings{echzell2020flowbased, abstract = {Network Creation Games (NCGs) model the creation of decentralized communication networks like the Internet. In such games strategic agents corresponding to network nodes selfishly decide with whom to connect to optimize some objective function. Past research intensively analyzed models where the agents strive for a central position in the network. This models agents optimizing the network for low-latency applications like VoIP. However, with today's abundance of streaming services it is important to ensure that the created network can satisfy the increased bandwidth demand. To the best of our knowledge, this natural problem of the decentralized strategic creation of networks with sufficient bandwidth has not yet been studied. We introduce Flow-Based NCGs where the selfish agents focus on bandwidth instead of latency. In essence, budget-constrained agents create network links to maximize their minimum or average network flow value to all other network nodes. Equivalently, this can also be understood as agents who create links to increase their connectivity and thus also the robustness of the network. For this novel type of NCG we prove that pure Nash equilibria exist, we give a simple algorithm for computing optimal networks, we show that the Price of Stability is 1 and we prove an (almost) tight bound of 2 on the Price of Anarchy. Last but not least, we show that our models do not admit a potential function.}, author = {Echzell, Hagen and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, editor = {Bessiere, Christian}, keywords = {annamelnichenko hagenechzell ijcai pascallenzner tobiasfriedrich year2020}, pages = {139-145}, publisher = {ijcai.org}, title = {Flow-Based Network Creation Games}, year = 2020 }

2019 [ nach oben ]

Friedrich, Tobias; Rothenberger, Ralf Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.International Joint Conference on Artificial Intelligence (IJCAI) 2019: 6151–6155
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^-k/(2k-1) \log^{-(k-1)/(2k-1)(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.
@inproceedings{friedrich2019satisfiabilityIJCAI, abstract = {We study non-uniform random k-SAT on n variables with an arbitrary probability distribution p on the variable occurrences. The number \(t = t(n)\) of randomly drawn clauses at which random formulas go from asymptotically almost surely (a.a.s.) satisfiable to a.a.s. unsatisfiable is called the satisfiability threshold. Such a threshold is called sharp if it approaches a step function as n increases. We show that a threshold t(n) for random k-SAT with an ensemble \((p_n)_{n\in\mathbb{N}}\) of arbitrary probability distributions on the variable occurrences is sharp if \(\|p\|_2^2 = O_n(t^{-2/k})\) and \(\|p\|_\infty\) \(= o_n(t^{-k/(2k-1)} \log^{-(k-1)/(2k-1)}(t))\). This result generalizes Friedgut’s sharpness result from uniform to non-uniform random k-SAT and implies sharpness for thresholds of a wide range of random k-SAT models with heterogeneous probability distributions, for example such models where the variable probabilities follow a power-law distribution.}, author = {Friedrich, Tobias and Rothenberger, Ralf}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai ralfrothenberger scalefree_sat tobiasfriedrich year2019}, pages = {6151-6155}, title = {Sharpness of the Satisfiability Threshold for Non-Uniform Random \(k\)-SAT.}, year = 2019 }

2011 [ nach oben ]

Bringmann, Karl; Friedrich, Tobias; Neumann, Frank; Wagner, Markus Approximation-Guided Evolutionary Multi-Objective OptimizationInternational Joint Conference on Artificial Intelligence (IJCAI) 2011: 1198–1203
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Multi-objective optimization problems arise frequently in applications but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a new framework of an evolutionary algorithm for multi-objective optimization that allows to work with a formal notion of approximation. Our experimental results show that our approach outperforms state-of-the-art evolutionary algorithms in terms of the quality of the approximation that is obtained in particular for problems with many objectives.
@inproceedings{DBLP:conf/ijcai/BringmannFNW11, abstract = {Multi-objective optimization problems arise frequently in applications but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a new framework of an evolutionary algorithm for multi-objective optimization that allows to work with a formal notion of approximation. Our experimental results show that our approach outperforms state-of-the-art evolutionary algorithms in terms of the quality of the approximation that is obtained in particular for problems with many objectives.}, author = {Bringmann, Karl and Friedrich, Tobias and Neumann, Frank and Wagner, Markus}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {frankneumann ijcai imported karlbringmann markuswagner tobiasfriedrich year2011}, pages = {1198-1203}, publisher = {{IJCAI/AAAI}}, title = {Approximation-Guided Evolutionary Multi-Objective Optimization}, year = 2011 }

Fellows, Michael R.; Friedrich, Tobias; Hermelin, Danny; Narodytska, Nina; Rosamond, Frances A. Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints TractableInternational Joint Conference on Artificial Intelligence (IJCAI) 2011: 522–527
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.
@inproceedings{DBLP:conf/ijcai/FellowsFHNR11, abstract = {We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations, and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable even though it is provably intractable in general. Interestingly, the convexity of constraints is the key property in achieving fixed parameter tractability, while the convexity of domains does not usually make the problem easier.}, author = {Fellows, Michael R. and Friedrich, Tobias and Hermelin, Danny and Narodytska, Nina and Rosamond, Frances A.}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {ijcai imported tobiasfriedrich year2011}, pages = {522-527}, publisher = {{IJCAI/AAAI}}, title = {Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable}, year = 2011 }