2024 [ nach oben ]

Harder, Jonathan Gadea; Kötzing, Timo; Li, Xiaoyue; Radhakrishnan, Aishwarya; Ruff, Janosch Run Time Bounds for Integer-Valued OneMax FunctionsGenetic and Evolutionary Computation Conference (GECCO ’24) 2024
[ BibTeX ] [ DOI ] [ Download ]
 
@conference{2024bounds, author = {Harder, Jonathan Gadea and Kötzing, Timo and Li, Xiaoyue and Radhakrishnan, Aishwarya and Ruff, Janosch}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO '24)}, keywords = {sys:relevantfor:ae aishwaryaradhakrishnan gecco janoschruff jonathangadeaharder timokoetzing xiaoyueli year2024}, title = {Run Time Bounds for Integer-Valued OneMax Functions}, year = 2024 }

2023 [ nach oben ]

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 }

2021 [ nach oben ]

Berger, Julian; Böther, Maximilian; Doskoč, Vanja; Gadea Harder, Jonathan; Klodt, Nicolas; Kötzing, Timo; Lötzsch, Winfried; Peters, Jannik; Schiller, Leon; Seifert, Lars; Wells, Armin; Wietheger, Simon Learning Languages with Decidable HypothesesComputability in Europe (CiE) 2021: 25–37
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In \emph{language learning in the limit, the most common type of hypothesis is to give an enumerator for a language, a \(W\)-index. These hypotheses have the drawback that even the membership problem is undecidable. In this paper, we use a different system which allows for naming arbitrary decidable languages, namely \emph{programs for characteristic functions (called \(C\)-indices). These indices have the drawback that it is now not decidable whether a given hypothesis is even a legal \(C\)-index. In this first analysis of learning with \(C\)-indices, we give a structured account of the learning power of various restrictions employing \(C\)-indices, also when compared with \(W\)-indices. We establish a hierarchy of learning power depending on whether \(C\)-indices are required (a) on all outputs; (b) only on outputs relevant for the class to be learned or (c) only in the limit as final, correct hypotheses. We analyze all these questions also in relation to the mode of data presentation. Finally, we also ask about the relation of semantic versus syntactic convergence and derive the map of pairwise relations for these two kinds of convergence coupled with various forms of data presentation.
@inproceedings{berger2021learning, abstract = {In \emph{language learning in the limit}, the most common type of hypothesis is to give an enumerator for a language, a \(W\)-index. These hypotheses have the drawback that even the membership problem is undecidable. In this paper, we use a different system which allows for naming arbitrary decidable languages, namely \emph{programs for characteristic functions} (called \(C\)-indices). These indices have the drawback that it is now not decidable whether a given hypothesis is even a legal \(C\)-index. In this first analysis of learning with \(C\)-indices, we give a structured account of the learning power of various restrictions employing \(C\)-indices, also when compared with \(W\)-indices. We establish a hierarchy of learning power depending on whether \(C\)-indices are required (a) on all outputs; (b) only on outputs relevant for the class to be learned or (c) only in the limit as final, correct hypotheses. We analyze all these questions also in relation to the mode of data presentation. Finally, we also ask about the relation of semantic versus syntactic convergence and derive the map of pairwise relations for these two kinds of convergence coupled with various forms of data presentation.}, author = {Berger, Julian and Böther, Maximilian and Doskoč, Vanja and Gadea Harder, Jonathan and Klodt, Nicolas and Kötzing, Timo and Lötzsch, Winfried and Peters, Jannik and Schiller, Leon and Seifert, Lars and Wells, Armin and Wietheger, Simon}, booktitle = {Computability in Europe (CiE)}, keywords = {arminwells cie jannikpeters jonathangadeaharder julianberger larsseifert leonschiller maximilianboether nicolasklodt simonwietheger timokoetzing vanjadoskoc winfriedloetzsch year2021}, pages = {25-37}, title = {Learning Languages with Decidable Hypotheses}, year = 2021 }