TY - CONF AU - Hamann, Heiko AU - Sayama, Hiroki AU - Rieffel, John AU - Risi, Sebastian AU - Doursat, Rene AU - Lipson, Hod ID - 20129 T2 - 14th Int. Conf. on the Synthesis and Simulation of Living Systems (ALIFE 2014) TI - Evolution of Collective Behaviors by Minimizing Surprise ER - TY - CONF AU - Cervera, Enric AU - Khaluf, Yara AU - Birattari, Mauro AU - Hamann, Heiko AU - Pobil, Angel P. del AU - Chinellato, Eris AU - Martinez-Martin, Ester AU - Hallam, John AU - Morales, Antonio ID - 20130 T2 - Simulation of Adaptive Behavior (SAB 2014) TI - A Swarm Robotics Approach to Task Allocation Under Soft Deadlines and Negligible Switching Costs VL - 8575 ER - TY - CONF AB - We consider the problem of scheduling a number of jobs on $m$ identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement r_j \in {0,1}. The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their \emph{processing speeds}, have been studied under the term discrete-continuous scheduling. Known results are either very pessimistic or heuristic in nature.In this paper, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover, we prove that balanced schedules yield a 2-1/m-approximation for a fixed number of processors. Such schedules are computed by our GreedyBalance algorithm, for which the bound is tight. AU - Brinkmann, Andre AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm AU - Nagel, Lars AU - Riechers, Sören AU - Suess, Tim ID - 368 T2 - Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Scheduling Shared Continuous Resources on Many-Cores ER - TY - CONF AB - Max-min fairness (MMF) is a widely known approach to a fair allocation of bandwidth to each of the users in a network. This allocation can be computed by uniformly raising the bandwidths of all users without violating capacity constraints. We consider an extension of these allocations by raising the bandwidth with arbitrary and not necessarily uniform time-depending velocities (allocation rates). These allocations are used in a game-theoretic context for routing choices, which we formalize in progressive filling games (PFGs).We present a variety of results for equilibria in PFGs. We show that these games possess pure Nash and strong equilibria. While computation in general is NP-hard, there are polynomial-time algorithms for prominent classes of Max-Min-Fair Games (MMFG), including the case when all users have the same source-destination pair. We characterize prices of anarchy and stability for pure Nash and strong equilibria in PFGs and MMFGs when players have different or the same source-destination pairs. In addition, we show that when a designer can adjust allocation rates, it is possible to design games with optimal strong equilibria. Some initial results on polynomial-time algorithms in this direction are also derived. AU - Harks, Tobias AU - Höfer, Martin AU - Schewior, Kevin AU - Skopalik, Alexander ID - 370 T2 - Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM'14) TI - Routing Games with Progressive Filling ER - TY - GEN AU - Pahl, David ID - 373 TI - Reputationssysteme für zusammengesetzte Dienstleistungen ER - TY - CONF AB - 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. AU - Abshoff, Sebastian AU - Markarian, Christine AU - Meyer auf der Heide, Friedhelm ID - 379 T2 - Proceedings of the 8th Annual International Conference on Combinatorial Optimization and Applications (COCOA) TI - Randomized Online Algorithms for Set Cover Leasing Problems ER - TY - CONF AB - 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} AU - Cord-Landwehr, Andreas AU - Mäcker, Alexander AU - Meyer auf der Heide, Friedhelm ID - 380 T2 - Proceedings of the 10th International Conference on Web and Internet Economics (WINE) TI - Quality of Service in Network Creation Games ER - TY - CONF AU - Polevoy, Gleb AU - Trajanovski, Stojan AU - de Weerdt, Mathijs M. ID - 17659 KW - competition KW - equilibrium KW - market KW - models KW - shared effort games KW - simulation SN - 978-1-4503-2738-1 T2 - Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems TI - Nash Equilibria in Shared Effort Games ER - TY - CONF AU - Polevoy, Gleb AU - de Weerdt, Mathijs M. ID - 17660 KW - dynamics KW - emotion modeling KW - negotiation KW - network interaction KW - shared effort game SN - 978-1-4503-2738-1 T2 - Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems TI - Improving Human Interaction in Crowdsensing ER - TY - CONF AU - King, Thomas C. AU - Liu, Qingzhi AU - Polevoy, Gleb AU - de Weerdt, Mathijs AU - Dignum, Virginia AU - van Riemsdijk, M. Birna AU - Warnier, Martijn ID - 17661 KW - crowd-sensing KW - crowdsourcing KW - data aggregation KW - game theory KW - norms KW - reciprocation KW - self interested agents KW - simulation SN - 978-1-4503-2738-1 T2 - Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems TI - Request Driven Social Sensing ER -