BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Alexander Skopalik

Alexander Skopalik appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryComputational ComplexityData Structures and AlgorithmsDiscrete MathematicsDistributed, Parallel, and Cluster ComputingMultiagent SystemsNetworking and Internet Architecture

Catalog footprint

What is connected

9works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2020arXiv

Improving approximate pure Nash equilibria in congestion games

Congestion games constitute an important class of games to model resource allocation by different users. As computing an exact or even an approximate pure Nash equilibrium is in general PLS-complete, Caragiannis et al. (2011) present a polynomial-time algorithm that computes a ($2 + ε$)-approximate pure Nash equilibria for games with linear cost functions and further results for polynomial cost functions. We show that this factor can be improved to $(1.61+ε)$ and further improved results for polynomial cost functions, by a seemingly simple modification to their algorithm by allowing for the cost functions used during the best response dynamics be different from the overall objective function. Interestingly, our modification to the algorithm also extends to efficiently computing improved approximate pure Nash equilibria in games with arbitrary non-decreasing resource cost functions. Additionally, our analysis exhibits an interesting method to optimally compute universal load dependent taxes and using linear programming duality prove tight bounds on PoA under universal taxation, e.g, 2.012 for linear congestion games and further results for polynomial cost functions. Although our approach yield weaker results than that in Bilò and Vinci (2016), we remark that our cost functions are locally computable and in contrast to Bilò and Vinci (2016) are independent of the actual instance of the game.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Congestion Games with Mixed Objectives

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Budget-restricted utility games with ordered strategic decisions

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 analyzed. Finally, we show that the time an ordered budget game needs to convergence towards an equilibrium may be exponential.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multilevel Network Games

We consider a multilevel network game, where nodes can improve their communication costs by connecting to a high-speed network. The $n$ nodes are connected by a static network and each node can decide individually to become a gateway to the high-speed network. The goal of a node $v$ is to minimize its private costs, i.e., the sum (SUM-game) or maximum (MAX-game) of communication distances from $v$ to all other nodes plus a fixed price $α> 0$ if it decides to be a gateway. Between gateways the communication distance is $0$, and gateways also improve other nodes' distances by behaving as shortcuts. For the SUM-game, we show that for $α\leq n-1$, the price of anarchy is $Θ(n/\sqrtα)$ and in this range equilibria always exist. In range $α\in (n-1,n(n-1))$ the price of anarchy is $Θ(\sqrtα)$, and for $α\geq n(n-1)$ it is constant. For the MAX-game, we show that the price of anarchy is either $Θ(1 + n/\sqrtα)$, for $α\geq 1$, or else $1$. Given a graph with girth of at least $4α$, equilibria always exist. Concerning the dynamics, both the SUM-game and the MAX-game are not potential games. For the SUM-game, we even show that it is not weakly acyclic.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Routing Games with Progressive Filling

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure

We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of (pure Nash) equilibria is guaranteed by potential function arguments. Unfortunately, this proof of existence is inefficient and computing equilibria is such games is a {\sf PLS}-hard problem. The situation gets worse when superlinear latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and equilibria may not even exist. Given these obstacles, we consider approximate equilibria as alternative solution concepts. Do such equilibria exist? And if so, can we compute them efficiently? We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an "approximation" of such games by a new class of potential games that we call $Ψ$-games. This allows us to show that these games have $d!$-approximate equilibria, where $d$ is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate equilibria when $d$ is a constant. For games with linear latency functions, the approximation guarantee is $\frac{3+\sqrt{5}}{2}+O(γ)$ for arbitrarily small $γ>0$; for latency functions with maximum degree $d\geq 2$, it is $d^{2d+o(d)}$. The running time is polynomial in the number of bits in the representation of the game and $1/γ$. As a byproduct of our techniques, we also show the following structural statement for weighted congestion games with polynomial latency functions of maximum degree $d\geq 2$: polynomially-long sequences of best-response moves from any initial state to a $d^{O(d^2)}$-approximate equilibrium exist and can be efficiently identified in such games as long as $d$ is constant.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient computation of approximate pure Nash equilibria in congestion games

Congestion games constitute an important class of games in which computing an exact or even approximate pure Nash equilibrium is in general {\sf PLS}-complete. We present a surprisingly simple polynomial-time algorithm that computes O(1)-approximate Nash equilibria in these games. In particular, for congestion games with linear latency functions, our algorithm computes $(2+ε)$-approximate pure Nash equilibria in time polynomial in the number of players, the number of resources and $1/ε$. It also applies to games with polynomial latency functions with constant maximum degree $d$; there, the approximation guarantee is $d^{O(d)}$. The algorithm essentially identifies a polynomially long sequence of best-response moves that lead to an approximate equilibrium; the existence of such short sequences is interesting in itself. These are the first positive algorithmic results for approximate equilibria in non-symmetric congestion games. We strengthen them further by proving that, for congestion games that deviate from our mild assumptions, computing $ρ$-approximate equilibria is {\sf PLS}-complete for any polynomial-time computable $ρ$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Impact of Fair Best Response Dynamics

In this work we completely characterize how the frequency with which each player participates in the game dynamics affects the possibility of reaching efficient states, i.e., states with an approximation ratio within a constant factor from the price of anarchy, within a polynomially bounded number of best responses. We focus on the well known class of congestion games and we show that, if each player is allowed to play at least once and at most $β$ times any $T$ best responses, states with approximation ratio $O(β)$ times the price of anarchy are reached after $T \lceil \log \log n \rceil$ best responses, and that such a bound is essentially tight also after exponentially many ones. One important consequence of our result is that the fairness among players is a necessary and sufficient condition for guaranteeing a fast convergence to efficient states. This answers the important question of the maximum order of $β$ needed to fast obtain efficient states, left open by [9,10] and [3], in which fast convergence for constant $β$ and very slow convergence for $β=O(n)$ have been shown, respectively. Finally, we show that the structure of the game implicitly affects its performances. In particular, we show that in the symmetric setting, in which all players share the same set of strategies, the game always converges to an efficient state after a polynomial number of best responses, regardless of the frequency each player moves with.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Considerate Equilibrium

We consider the existence and computational complexity of coalitional stability concepts based on social networks. Our concepts represent a natural and rich combinatorial generalization of a recent approach termed partition equilibrium. We assume that players in a strategic game are embedded in a social network, and there are coordination constraints that restrict the potential coalitions that can jointly deviate in the game to the set of cliques in the social network. In addition, players act in a "considerate" fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors. We study the properties of such considerate equilibria in application to the class of resource selection games (RSG). Our main result proves existence of a considerate equilibrium in all symmetric RSG with strictly increasing delays, for any social network among the players. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for the standard RSG showing that there exists a state that is stable against selfish and considerate behavior simultaneously. In addition, we show results on convergence of considerate dynamics.

0 citations0 reviewsNo code linkedOpen access