@inproceedings{379, abstract = {{In the leasing variant of Set Cover presented by Anthony et al.[1], elements U arrive over time and must be covered by sets from a familyF of subsets of U. Each set can be leased for K different periods of time.Let |U| = n and |F| = m. Leasing a set S for a period k incurs a cost ckS and allows S to cover its elements for the next lk time steps. The objectiveis to minimize the total cost of the sets leased, such that elements arrivingat any time t are covered by sets which contain them and are leased duringtime t. Anthony et al. [1] gave an optimal O(log n)-approximation forthe problem in the offline setting, unless P = NP [22]. In this paper, wegive randomized algorithms for variants of Set Cover Leasing in the onlinesetting, including a generalization of Online Set Cover with Repetitionspresented by Alon et al. [2], where elements appear multiple times andmust be covered by a different set at each arrival. Our results improve theO(log2(mn)) competitive factor of Online Set Cover with Repetitions [2]to O(log d log(dn)) = O(logmlog(mn)), where d is the maximum numberof sets an element belongs to.}}, author = {{Abshoff, Sebastian and Markarian, Christine and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}}, pages = {{25--34}}, title = {{{Randomized Online Algorithms for Set Cover Leasing Problems}}}, doi = {{10.1007/978-3-319-12691-3_3}}, year = {{2014}}, } @inproceedings{380, abstract = {{Network creation games model the creation and usage costs of networks formed by n selfish nodes. Each node v can buy a set of edges, each for a fixed price α > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances from v to all other nodes plus the prices of the bought edges. The above papers show the existence of Nash equilibria as well as upper and lower bounds for the prices of anarchy and stability. In several subsequent papers, these bounds were improved for a wide range of prices α. In this paper, we extend these models by incorporating quality-of-service aspects: Each edge cannot only be bought at a fixed quality (edge length one) for a fixed price α. Instead, we assume that quality levels (i.e., edge lengths) are varying in a fixed interval [βˇ,β^] , 0 series = {LNCS}}}, author = {{Cord-Landwehr, Andreas and Mäcker, Alexander and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceedings of the 10th International Conference on Web and Internet Economics (WINE)}}, pages = {{423--428}}, title = {{{Quality of Service in Network Creation Games}}}, doi = {{10.1007/978-3-319-13129-0_34}}, year = {{2014}}, } @inproceedings{382, abstract = {{This paper explores how cloud provider competition influences instance pricing in an IaaS (Infrastructure-as-a-Service) market. When reserved instance pricing includes an on-demand price component in addition to a reservation fee (two-part tariffs), different providers might offer different price combinations, where the client’s choice depends on its load profile. We investigate a duopoly of providers and analyze stable market prices in two-part tariffs. Further, we study offers that allow a specified amount of included usage (three-part tariffs). Neither two-part nor three-part tariffs produce an equilibrium market outcome other than a service pricing that equals production cost, i.e., complex price structures do not significantly affect the results from ordinary Bertrand competition.}}, author = {{Künsemöller, Jörn and Brangewitz, Sonja and Karl, Holger and Haake, Claus-Jochen}}, booktitle = {{Proceedings of the 2014 IEEE International Conference on Services Computing (SCC)}}, pages = {{203--210}}, title = {{{Provider Competition in Infrastructure-as-a-Service}}}, doi = {{10.1109/SCC.2014.35}}, year = {{2014}}, } @misc{391, author = {{Feldkord, Björn}}, publisher = {{Universität Paderborn}}, title = {{{On Variants of the Page Migration Problem}}}, year = {{2014}}, } @techreport{443, abstract = {{The objective of this paper is to analyze the formation of group structures where individuals are allowed to engage in several groups at the same time. These structures are interpreted here as social networks. Each of the groups is supposed to have specific rules or constitutions governing which members may join or leave it. A social network is then considered to be stable if none of the groups is altered any more. Given this framework, we not only analyze which influence the constitutions have on network formation but we also provide requirements under which stable networks are induced for sure. Furthermore, by embedding many-to-many matchings into our setting, we apply our model to job markets with labor unions. To some extent the unions may provide job guarantees and, therefore, have influence on the stability of the job market.}}, author = {{Mauleon, Ana and Röhl, Nils and Vannetelbosch, Vincent}}, publisher = {{Universität Paderborn}}, title = {{{Constitutions and Social Networks}}}, year = {{2014}}, } @article{444, abstract = {{BackgroundMedical nonpersistence is a worldwide problem of striking magnitude. Although many fields of studies including epidemiology, sociology, and psychology try to identify determinants for medical nonpersistence, comprehensive research to explain medical nonpersistence from an economics perspective is rather scarce.ObjectivesThe aim of the study was to develop a conceptual framework that augments standard economic choice theory with psychological concepts of behavioral economics to understand how patients’ preferences for discontinuing with therapy arise over the course of the medical treatment. The availability of such a framework allows the targeted design of mechanisms for intervention strategies.MethodsOur conceptual framework models the patient as an active economic agent who evaluates the benefits and costs for continuing with therapy. We argue that a combination of loss aversion and mental accounting operations explains why patients discontinue with therapy at a specific point in time. We designed a randomized laboratory economic experiment with a student subject pool to investigate the behavioral predictions.ResultsSubjects continue with therapy as long as experienced utility losses have to be compensated. As soon as previous losses are evened out, subjects perceive the marginal benefit of persistence lower than in the beginning of the treatment. Consequently, subjects start to discontinue with therapy.ConclusionsOur results highlight that concepts of behavioral economics capture the dynamic structure of medical nonpersistence better than does standard economic choice theory. We recommend that behavioral economics should be a mandatory part of the development of possible intervention strategies aimed at improving patients’ compliance and persistence behavior.}}, author = {{Mir Djawadi, Behnud and Fahr, Rene and Turk, Florian}}, journal = {{Value in Health}}, number = {{8}}, pages = {{814--822}}, publisher = {{Elsevier}}, title = {{{Conceptual Model and Economic Experiments to Explain Nonpersistence and Enable Mechanism Designs Fosterin Behavioral Change}}}, doi = {{10.1016/j.jval.2014.08.2669}}, year = {{2014}}, } @article{445, abstract = {{We consider the inner core as a solution concept for cooperative games with non-transferable utility (NTU) and its relationship to payoffs of competitive equilibria of markets that are induced by NTU games. An NTU game is an NTU market game if there exists a market such that the set of utility allocations a coalition can achieve in the market coincides with the set of utility allocations the coalition can achieve in the game. In this paper, we introduce a new construction of a market based on a closed subset of the inner core which satisfies a strict positive separability. We show that the constructed market represents the NTU game and, further, has the given closed set as the set of payoff vectors of competitive equilibria. It turns out that this market is not uniquely determined, and thus, we obtain a class of markets. Our results generalize those relating to competitive outcomes of NTU market games in the literature.}}, author = {{Brangewitz, Sonja and Gamp, Jan-Philip}}, journal = {{Economic Theory}}, number = {{3}}, pages = {{529--554}}, publisher = {{Springer}}, title = {{{Competitive outcomes and the inner core of NTU market games}}}, doi = {{10.1007/s00199-014-0846-7}}, year = {{2014}}, } @inproceedings{451, abstract = {{We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. We study strategic budget games, where the budget is shared proportionally. We also consider a variant in which the order of the strategic decisions influences the distribution of the budgets. The complexity of the optimal solution as well as existence, complexity and quality of equilibria are analysed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.}}, author = {{Drees, Maximilian and Riechers, Sören and Skopalik, Alexander}}, booktitle = {{Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)}}, editor = {{Lavi, Ron}}, pages = {{110--121}}, title = {{{Budget-restricted utility games with ordered strategic decisions}}}, doi = {{10.1007/978-3-662-44803-8_10}}, year = {{2014}}, } @inproceedings{452, abstract = {{Today's networks, like the Internet, do not consist of one but a mixture of several interconnected networks. Each has individual qualities and hence the performance of a network node results from the networks' interplay.We introduce a new game theoretic model capturing the interplay between a high-speed backbone network and a low-speed general purpose network. In our model, n nodes are connected by a static network and each node can decide individually to become a gateway node. A gateway node pays a fixed price for its connection to the high-speed network, but can utilize the high-speed network to gain communication distance 0 to all other gateways. Communication distances in the low-speed network are given by the hop distances. The effective communication distance between any two nodes then is given by the shortest path, which is possibly improved by using gateways as shortcuts.Every node v has the objective to minimize its communication costs, given by the sum (SUM-game) or maximum (MAX-game) of the effective communication distances from v to all other nodes plus a fixed price \alpha > 0, if it decides to be a gateway. For both games and different ranges of \alpha, we study the existence of equilibria, the price of anarchy, and convergence properties of best-response dynamics.}}, author = {{Abshoff, Sebastian and Cord-Landwehr, Andreas and Jung, Daniel and Skopalik, Alexander}}, booktitle = {{Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)}}, editor = {{Lavi, Ron}}, pages = {{294}}, title = {{{Brief Announcement: A Model for Multilevel Network Games}}}, year = {{2014}}, } @inproceedings{453, abstract = {{In this paper we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions. We show that the value of the potential function $\Phi(\sf s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential value $\Phi(\sf s^*)$ by a factor $\Psi_{\mathcal{F}}$ which only depends on the set of cost/utility functions $\mathcal{F}$, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome $\sf s$. The significance of this result is twofold. On the one hand it provides \emph{Price-of-Anarchy}-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute $(1+\varepsilon)\cdot\Psi_{\mathcal{F}}$-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.}}, author = {{Feldotto, Matthias and Gairing, Martin and Skopalik, Alexander}}, booktitle = {{Proceedings of the 10th International Conference on Web and Internet Economics (WINE)}}, pages = {{30--43}}, title = {{{Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria}}}, doi = {{10.1007/978-3-319-13129-0_3}}, year = {{2014}}, } @inproceedings{455, abstract = {{We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.}}, author = {{Hansknecht, Christoph and Klimm, Max and Skopalik, Alexander}}, booktitle = {{Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}}, pages = {{242 -- 257}}, title = {{{Approximate pure Nash equilibria in weighted congestion games}}}, doi = {{10.4230/LIPIcs.APPROX-RANDOM.2014.242}}, year = {{2014}}, } @inproceedings{456, abstract = {{We study the existence of approximate pure Nash equilibriain social context congestion games. For any given set of allowed costfunctions F, we provide a threshold value μ(F), and show that for theclass of social context congestion games with cost functions from F, α-Nash dynamics are guaranteed to converge to α-approximate pure Nashequilibrium if and only if α > μ(F).Interestingly, μ(F) is related and always upper bounded by Roughgarden’sanarchy value [19].}}, author = {{Gairing, Martin and Kotsialou, Grammateia and Skopalik, Alexander}}, booktitle = {{Proceedings of the 10th International Conference on Web and Internet Economics (WINE)}}, pages = {{480 -- 485}}, title = {{{Approximate pure Nash equilibria in Social Context Congestion Games}}}, doi = {{10.1007/978-3-319-13129-0_43}}, year = {{2014}}, } @misc{458, author = {{Dreimann, Philipp}}, publisher = {{Universität Paderborn}}, title = {{{Anticipatory Power Cycling of Mobile Network Equipment for High-Demand Multimedia Traffic}}}, year = {{2014}}, } @inproceedings{459, abstract = {{In this survey article, we discuss two algorithmic research areas that emerge from problems that arise when resources are offered in the cloud. The first area, online leasing, captures problems arising from the fact that resources in the cloud are not bought, but leased by cloud vendors. The second area, Distributed Storage Systems, deals with problems arising from so-called cloud federations, i.e., when several cloud providers are needed to fulfill a given task.}}, author = {{Kniesburges, Sebastian and Markarian, Christine and Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{Proceedings of the 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO)}}, pages = {{1--13}}, title = {{{Algorithmic Aspects of Resource Management in the Cloud}}}, doi = {{10.1007/978-3-319-09620-9_1}}, year = {{2014}}, } @misc{461, author = {{Dräxler, Sevil}}, publisher = {{Universität Paderborn}}, title = {{{Adaptive Placement of Programmable Virtual Network Function Chains}}}, year = {{2014}}, } @inproceedings{462, abstract = {{We discuss a technique to analyze complex infinitely repeated games using techniques from the fields of game theory and simulations. Our research is motivated by the analysis of electronic markets with thousands of participants and possibly complex strategic behavior. We consider an example of a global market of composed IT services to demonstrate the use of our simulation technique. We present our current work in this area and we want to discuss further approaches for the future.}}, author = {{Feldotto, Matthias and Skopalik, Alexander}}, booktitle = {{Proceedings of the 4th International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH 2014)}}, pages = {{625--630}}, title = {{{A Simulation Framework for Analyzing Complex Infinitely Repeated Games}}}, doi = {{10.5220/0005110406250630}}, year = {{2014}}, } @article{464, abstract = {{Topological self-stabilization is an important concept to build robust open distributed systems (such as peer-to-peer systems) where nodes can organize themselves into meaningful network topologies. The goal is to devise distributed algorithms where nodes forward, insert, and delete links to neighboring nodes, and that converge quickly to such a desirable topology, independently of the initial network configuration. This article proposes a new model to study the parallel convergence time. Our model sheds light on the achievable parallelism by avoiding bottlenecks of existing models that can yield a distorted picture. As a case study, we consider local graph linearization—i.e., how to build a sorted list of the nodes of a connected graph in a distributed and self-stabilizing manner. In order to study the main structure and properties of our model, we propose two variants of a most simple local linearization algorithm. For each of these variants, we present analyses of the worst-case and bestcase parallel time complexities, as well as the performance under a greedy selection of the actions to be executed. It turns out that the analysis is non-trivial despite the simple setting, and to complement our formal insights we report on our experiments which indicate that the runtimes may be better in the average case.}}, author = {{Gall, Dominik and Jacob, Riko and Richa, Andrea W. and Scheideler, Christian and Schmid, Stefan and Täubig, Hanjo }}, journal = {{Theory of Computing Systems}}, number = {{1}}, pages = {{110--135}}, publisher = {{Springer}}, title = {{{A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization}}}, doi = {{10.1007/s00224-013-9504-x}}, year = {{2014}}, } @article{467, abstract = {{Financial benefits are an important factor when cloud infrastructure is considered to meet processing demand. The dynamics of on-demand pricing and service usage are investigated in a two-stage game model for a monopoly Infrastructure-as-a-Service (IaaS) market. The possibility of hybrid clouds (public clouds plus own infrastructure) turns out to be essential in order that not only the provider but also the clients have significant benefits from on-demand services. Even if the client meets all demand in the public cloud, the threat of building a hybrid cloud keeps the instance price low. This is not the case when reserved instances are offered as well. Parameters like load profiles and economies of scale have a huge effect on likely future pricing and on a cost-optimal split-up of client demand between either a client’s own data center and a public cloud service or between reserved and on-demand cloud instances.}}, author = {{Künsemöller, Jörn and Karl, Holger}}, journal = {{Future Generation Computer Systems}}, pages = {{44----52}}, publisher = {{Elsevier}}, title = {{{A Game-Theoretic Approach to the Financial Benefits of Infrastructure-as-a-Service}}}, doi = {{10.1016/j.future.2014.03.005}}, year = {{2014}}, } @inproceedings{762, author = {{Schwabe, Arne and Karl, Holger}}, booktitle = {{Proceedings of the third workshop on Hot topics in software defined networking, HotSDN '14, Chicago, Illinois, USA, August 22, 2014}}, pages = {{115----120}}, title = {{{Using MAC addresses as efficient routing labels in data centers}}}, doi = {{10.1145/2620728.2620730}}, year = {{2014}}, } @misc{392, author = {{Brummel, NinaMadeleine}}, publisher = {{Universität Paderborn}}, title = {{{On the Relation between Innovation and Competion: The Case of Energy Industry}}}, year = {{2014}}, }