Source author record

Symeon Papavassiliou

Symeon Papavassiliou 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 Theory Discrete Mathematics math.PR Systems and Control

Catalog footprint

What is connected

3works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

A note on the network coloring game: A randomized distributed $(Δ+1)$-coloring algorithm

The network coloring game has been proposed in the literature of social sciences as a model for conflict-resolution circumstances. The players of the game are the vertices of a graph with $n$ vertices and maximum degree $Δ$. The game is played over rounds, and in each round all players simultaneously choose a color from a set of available colors. Players have local information of the graph: they only observe the colors chosen by their neighbors and do not communicate or cooperate with one another. A player is happy when she has chosen a color that is different from the colors chosen by her neighbors, otherwise she is unhappy, and a configuration of colors for which all players are happy is a proper coloring of the graph. It has been shown in the literature that, when the players adopt a particular greedy randomized strategy, the game reaches a proper coloring of the graph within $O(\log(n))$ rounds, with high probability, provided the number of colors available to each player is at least $Δ+2$. In this note we show that a modification of the aforementioned greedy strategy yields likewise a proper coloring of the graph, provided the number of colors available to each player is at least $Δ+1$, and results in a simple randomized distributed algorithm for the $(Δ+1)$-coloring problem..

preprint2021arXiv

A Fragile multi-CPR Game

A Fragile CPR Game is an instance of a resource sharing game where a common-pool resource, which is prone to failure due to overuse, is shared among several players. Each player has a fixed initial endowment and is faced with the task of investing in the common-pool resource without forcing it to fail. The return from the common-pool resource is subject to uncertainty and is perceived by the players in a prospect-theoretic manner. It is shown in [A.~R.~Hota, S.~Garg, S.~Sundaram, \textit{Fragility of the commons under prospect-theoretic risk attitudes}, Games and Economic Behavior \textbf{98} (2016) 135--164.] that, under some mild assumptions, a Fragile CPR Game admits a unique Nash equilibrium. In this article we investigate an extended version of a Fragile CPR Game, in which players are allowed to share multiple common-pool resources that are also prone to failure due to overuse. We refer to this game as a Fragile multi-CPR Game. Our main result states that, under some mild assumptions, a Fragile multi-CPR Game admits a Generalized Nash equilibrium. Moreover, we show that, when there are more players than common-pool resources, the set consisting of all Generalized Nash equilibria of a Fragile multi-CPR Game is of Lebesgue measure zero.

preprint2015arXiv

Cross-Layer Design of Wireless Multihop Networks over Stochastic Channels with Time-Varying Statistics

Network Utility Maximization (NUM) is often applied for the cross-layer design of wireless networks considering known wireless channels. However, realistic wireless channel capacities are stochastic bearing time-varying statistics, necessitating the redesign and solution of NUM problems to capture such effects. Based on NUM theory we develop a framework for scheduling, routing, congestion and power control in wireless multihop networks that considers stochastic Long or Short Term Fading wireless channels. Specifically, the wireless channel is modeled via stochastic differential equations alleviating several assumptions that exist in state-of-the-art channel modeling within the NUM framework such as the finite number of states or the stationarity. Our consideration of wireless channel modeling leads to a NUM problem formulation that accommodates non-convex and time-varying utilities. We consider both cases of non orthogonal and orthogonal access of users to the medium. In the first case, scheduling is performed via power control, while the latter separates scheduling and power control and the role of power control is to further increase users' optimal utility by exploiting random reductions of the stochastic channel power loss while also considering energy efficiency. Finally, numerical results evaluate the performance and operation of the proposed approach and study the impact of several involved parameters on convergence.