@article{669, abstract = {{We study a new class of games which generalizes congestion games andits bottleneck variant. We introduce congestion games with mixed objectives to modelnetwork scenarios in which players seek to optimize for latency and bandwidths alike.We characterize the (non-)existence of pure Nash equilibria (PNE), the convergenceof improvement dynamics, the quality of equilibria and show the complexity of thedecision problem. For games that do not possess PNE we give bounds on the approx-imation ratio of approximate pure Nash equilibria.}}, author = {{Feldotto, Matthias and Leder, Lennart and Skopalik, Alexander}}, issn = {{1382-6905}}, journal = {{Journal of Combinatorial Optimization}}, number = {{4}}, pages = {{1145--1167}}, publisher = {{Springer Nature}}, title = {{{Congestion games with mixed objectives}}}, doi = {{10.1007/s10878-017-0189-y}}, volume = {{36}}, year = {{2018}}, } @misc{1186, author = {{Kemper, Arne}}, publisher = {{Universität Paderborn}}, title = {{{Pure Nash Equilibria in Robust Congestion Games via Potential Functions}}}, year = {{2018}}, } @misc{1187, author = {{Nachtigall, Marcel}}, publisher = {{Universität Paderborn}}, title = {{{Scenario-driven Strategy Analysis in a n-player Composition Game Model}}}, year = {{2018}}, } @misc{1188, author = {{Kempf, Jérôme}}, publisher = {{Universität Paderborn}}, title = {{{Learning deterministic bandit behaviour form compositions}}}, year = {{2018}}, } @article{1369, abstract = {{In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of each player who chose that resource equals his demand. Otherwise, the budget is shared proportionally. In the general case, pure Nash equilibria (NE) do not exist for such games. In this paper, we consider the natural classes of singleton and matroid budget games with additional constraints and show that for each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential function to prove that every matroid budget game has an approximate pure NE which depends on the largest ratio between the different demands of each individual player.}}, author = {{Drees, Maximilian and Feldotto, Matthias and Riechers, Sören and Skopalik, Alexander}}, issn = {{1382-6905}}, journal = {{Journal of Combinatorial Optimization}}, publisher = {{Springer Nature}}, title = {{{Pure Nash equilibria in restricted budget games}}}, doi = {{10.1007/s10878-018-0269-7}}, year = {{2018}}, } @inproceedings{112, abstract = {{We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.}}, author = {{Feldotto, Matthias and Leder, Lennart and Skopalik, Alexander}}, booktitle = {{Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC)}}, pages = {{222----233}}, title = {{{Congestion Games with Complementarities}}}, doi = {{10.1007/978-3-319-57586-5_19}}, year = {{2017}}, } @inproceedings{113, abstract = {{We study the computation of approximate pure Nash equilibria in Shapley value (SV) weighted congestion games, introduced in [19]. This class of games considers weighted congestion games in which Shapley values are used as an alternative (to proportional shares) for distributing the total cost of each resource among its users. We focus on the interesting subclass of such games with polynomial resource cost functions and present an algorithm that computes approximate pure Nash equilibria with a polynomial number of strategy updates. Since computing a single strategy update is hard, we apply sampling techniques which allow us to achieve polynomial running time. The algorithm builds on the algorithmic ideas of [7], however, to the best of our knowledge, this is the first algorithmic result on computation of approximate equilibria using other than proportional shares as player costs in this setting. We present a novel relation that approximates the Shapley value of a player by her proportional share and vice versa. As side results, we upper bound the approximate price of anarchy of such games and significantly improve the best known factor for computing approximate pure Nash equilibria in weighted congestion games of [7].}}, author = {{Feldotto, Matthias and Gairing, Martin and Kotsialou, Grammateia and Skopalik, Alexander}}, booktitle = {{Proceedings of the 13th International Conference on Web and Internet Economics (WINE)}}, title = {{{Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games}}}, doi = {{10.1007/978-3-319-71924-5_14}}, year = {{2017}}, } @inproceedings{17652, author = {{Polevoy, Gleb and Trajanovski, Stojan and Grosso, Paola and de Laat, Cees}}, booktitle = {{Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I}}, isbn = {{978-3-319-71150-8}}, keywords = {{flow, filter, MMSA, set cover, approximation, local ratio algorithm}}, pages = {{3--17}}, publisher = {{Springer International Publishing}}, title = {{{Filtering Undesirable Flows in Networks}}}, doi = {{10.1007/978-3-319-71150-8_1}}, year = {{2017}}, } @inproceedings{17653, author = {{Polevoy, Gleb and de Weerdt, M.M.}}, booktitle = {{Proceedings of the 29th Benelux Conference on Artificial Intelligence}}, keywords = {{interaction, reciprocation, contribute, shared effort, curbing, convergence, threshold, Nash equilibrium, social welfare, efficiency, price of anarchy, price of stability}}, publisher = {{Springer}}, title = {{{Reciprocation Effort Games}}}, year = {{2017}}, } @inproceedings{17654, author = {{Polevoy, Gleb and de Weerdt, M.M.}}, booktitle = {{Proceedings of the 29th Benelux Conference on Artificial Intelligence}}, keywords = {{agents, projects, contribute, shared effort game, competition, quota, threshold, Nash equilibrium, social welfare, efficiency, price of anarchy, price of stability}}, publisher = {{Springer}}, title = {{{Competition between Cooperative Projects}}}, year = {{2017}}, } @inproceedings{59, abstract = {{We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed).}}, author = {{Kling, Peter and Mäcker, Alexander and Riechers, Sören and Skopalik, Alexander}}, booktitle = {{Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}}, pages = {{123----132}}, title = {{{Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource}}}, doi = {{10.1145/3087556.3087578}}, year = {{2017}}, } @inproceedings{66, abstract = {{In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of each player who chose that resource equals his demand. Otherwise, the budget is shared proportionally. In the general case, pure Nash equilibria (NE) do not exist for such games. In this paper, we consider the natural classes of singleton and matroid budget games with additional constraints and show that for each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential function to prove that every matroid budget game has an approximate pure NE which depends on the largest ratio between the different demands of each individual player.}}, author = {{Drees, Maximilian and Feldotto, Matthias and Riechers, Sören and Skopalik, Alexander}}, booktitle = {{Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON)}}, pages = {{175----187}}, title = {{{Pure Nash Equilibria in Restricted Budget Games}}}, doi = {{10.1007/978-3-319-62389-4_15}}, year = {{2017}}, } @misc{1073, author = {{Nachtigall, Simon}}, publisher = {{Universität Paderborn}}, title = {{{Sortieren dynamischer Daten}}}, year = {{2017}}, } @misc{1074, author = {{Pukrop, Simon}}, publisher = {{Universität Paderborn}}, title = {{{Robuste Optimierung in Congestion Games}}}, year = {{2017}}, } @misc{1080, author = {{Bürmann, Jan}}, publisher = {{Universität Paderborn}}, title = {{{Complexity of Signalling in Routing Games under Uncertainty}}}, year = {{2017}}, } @misc{1081, author = {{Vijayalakshmi, Vipin Ravindran}}, publisher = {{Universität Paderborn}}, title = {{{Bounding the Inefficiency of Equilibria in Congestion Games under Taxation}}}, year = {{2017}}, } @inproceedings{1094, abstract = {{Many university students struggle with motivational problems, and gamification has the potential to address these problems. However, gamification is hardly used in education, because current approaches to gamification require instructors to engage in the time-consuming preparation of their course contents for use in quizzes, mini-games and the like. Drawing on research on limited attention and present bias, we propose a "lean" approach to gamification, which relies on gamifying learning activities (rather than learning contents) and increasing their salience. In this paper, we present the app StudyNow that implements such a lean gamification approach. With this app, we aim to enable more students and instructors to benefit from the advantages of gamification.}}, author = {{Feldotto, Matthias and John, Thomas and Kundisch, Dennis and Hemsen, Paul and Klingsieck, Katrin and Skopalik, Alexander}}, booktitle = {{Proceedings of the 12th International Conference on Design Science Research in Information Systems and Technology (DESRIST)}}, pages = {{462--467}}, title = {{{Making Gamification Easy for the Professor: Decoupling Game and Content with the StudyNow Mobile App}}}, doi = {{10.1007/978-3-319-59144-5_32}}, year = {{2017}}, } @inproceedings{1095, abstract = {{Many university students struggle with motivational problems, and gamification has the potential to address these problems. However, using gamification currently is rather tedious and time-consuming for instructors because current approaches to gamification require instructors to engage in the time-consuming preparation of course contents (e.g., for quizzes or mini-games). In reply to this issue, we propose a “lean” approach to gamification, which relies on gamifying learning activities rather than learning contents. The learning activities that are gamified in the lean approach can typically be drawn from existing course syllabi (e.g., attend certain lectures, hand in assignments, read book chapters and articles). Hence, compared to existing approaches, lean gamification substantially lowers the time requirements posed on instructors for gamifying a given course. Drawing on research on limited attention and the present bias, we provide the theoretical foundation for the lean gamification approach. In addition, we present a mobile application that implements lean gamification and outline a mixed-methods study that is currently under way for evaluating whether lean gamification does indeed have the potential to increase students’ motivation. We thereby hope to allow more students and instructors to benefit from the advantages of gamification. }}, author = {{John, Thomas and Feldotto, Matthias and Hemsen, Paul and Klingsieck, Katrin and Kundisch, Dennis and Langendorf, Mike}}, booktitle = {{Proceedings of the 25th European Conference on Information Systems (ECIS)}}, pages = {{2970--2979}}, title = {{{Towards a Lean Approach for Gamifying Education}}}, year = {{2017}}, } @phdthesis{200, author = {{Drees, Maximilian}}, publisher = {{Universität Paderborn}}, title = {{{Existence and Properties of Pure Nash Equilibria in Budget Games}}}, year = {{2016}}, } @misc{210, author = {{Leder, Lennart}}, publisher = {{Universität Paderborn}}, title = {{{Congestion Games with Mixed Objectives}}}, year = {{2016}}, }