TY - GEN
AU - Kothe, Nils
ID - 277
TI - Multilevel Netzwerk Spiele mit konstanten Entfernungen im Highspeed-Netzwerk
ER -
TY - JOUR
AB - Inter-datacenter transfers of non-interactive but timely large flows over a private (managed) network is an important problem faced by many cloud service providers. The considered flows are non-interactive because they do not explicitly target the end users. However, most of them must be performed on a timely basis and are associated with a deadline. We propose to schedule these flows by a centralized controller, which determines when to transmit each flow and which path to use. Two scheduling models are presented in this paper. In the first, the controller also determines the rate of each flow, while in the second bandwidth is assigned by the network according to the TCP rules. We develop scheduling algorithms for both models and compare their complexity and performance.
AU - Cohen, R.
AU - Polevoy, Gleb
ID - 17657
IS - 99
JF - Cloud Computing, IEEE Transactions on
KW - Approximation algorithms
KW - Approximation methods
KW - Bandwidth
KW - Cloud computing
KW - Routing
KW - Schedules
KW - Scheduling
SN - 2168-7161
TI - Inter-Datacenter Scheduling of Large Data Flows
VL - PP
ER -
TY - JOUR
AB - Abstract We study the problem of bandwidth allocation with multiple interferences. In this problem the input consists of a set of users and a set of base stations. Each user has a list of requests, each consisting of a base station, a frequency demand, and a profit that may be gained by scheduling this request. The goal is to find a maximum profit set of user requests S that satisfies the following conditions: (i) S contains at most one request per user, (ii) the frequency sets allotted to requests in S that correspond to the same base station are pairwise non-intersecting, and (iii) the QoS received by any user at any frequency is reasonable according to an interference model. In this paper we consider two variants of bandwidth allocation with multiple interferences. In the first each request specifies a demand that can be satisfied by any subset of frequencies that is large enough. In the second each request specifies a specific frequency interval. Furthermore, we consider two interference models, multiplicative and additive. We show that these problems are extremely hard to approximate if the interferences depend on both the interfered and the interfering base stations. On the other hand, we provide constant factor approximation algorithms for both variants of bandwidth allocation with multiple interferences for the case where the interferences depend only on the interfering base stations. We also consider a restrictive special case that is closely related to the Knapsack problem. We show that this special case is NP-hard and that it admits an FPTAS.
AU - Bar-Yehuda, Reuven
AU - Polevoy, Gleb
AU - Rawitz, Dror
ID - 17658
JF - Discrete Applied Mathematics
KW - Local ratio
SN - 0166-218X
TI - Bandwidth allocation in cellular networks with multiple interferences
VL - 194
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
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 -
TY - JOUR
AU - Polevoy, Gleb
AU - Smorodinsky, Rann
AU - Tennenholtz, Moshe
ID - 17662
IS - 1
JF - ACM Trans. Econ. Comput.
KW - Competition
KW - efficiency
KW - equilibrium
KW - market
KW - social welfare
SN - 2167-8375
TI - Signaling Competition and Social Welfare
VL - 2
ER -
TY - CONF
AB - 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.
AU - Drees, Maximilian
AU - Riechers, Sören
AU - Skopalik, Alexander
ED - Lavi, Ron
ID - 451
T2 - Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT)
TI - Budget-restricted utility games with ordered strategic decisions
ER -