Τμήμα Πληροφορικής / Department of Computer Science: Recent submissions
Now showing items 921-940 of 1952
-
Article
The complexity of equilibria for risk-modeling valuations
(2016)Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], we study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than ...
-
Article
Conditional value-at-risk: Structure and complexity of equilibria
(2017)Conditional Value-at-Risk, denoted as CVaRα, is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain
-
Article
Minimizing Expectation Plus Variance
(2015)We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuationV (mapping probability distributions to reals)
-
Article
Minimizing expectation plus variance
(2012)We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (mapping probability distributions to reals)
-
Article
The complexity of pure equilibria in mix-weighted congestion games on parallel links
(2015)We revisit the simple class of weighted congestion games on parallel links [10], where each player has a non-negative weight and her cost on the link she chooses is the sum of the weights of all players choosing the link. ...
-
Article
Congestion games with player-specific constants
(2007)We consider a special case of weighted congestion games with player-specific latency functions where each player uses for each particular resource a fixed (non-decreasing) delay function together with a player-specific ...
-
Article
Computing on a partially eponymous ring
(2006)We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
-
Article
Network game with attacker and protector entities
(2005)Consider an information network with harmful procedures called attackers (e.g., viruses)
-
Report
The impact of timing on linearizability in counting networks
(Max-Planck-Institut fu\0308r Informatik, 1996)
-
Article
Computing on a partially eponymous ring
(2009)We study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all ...
-
Article
A graph-theoretic network security game
(2005)Consider a network vulnerable to viral infection. The system security software can guarantee safety only to a limited part of the network. We model this practical network scenario as a non-cooperative multi-player game on ...
-
Article
A network game with attackers and a defender
(2008)Consider an information network with threats called attackers
-
Article
The price of defense
(2006)We consider a strategic game with two classes of confronting randomized players on a graph G(V, E): v attackers, each choosing vertices and wishing to minimize the probability of being caught, and a defender, who chooses ...
-
Article
Sequentially consistent versus linearizable counting networks
(2008)We compare the impact of timing conditions on implementing sequentially consistent and linearizable counters using (uniform) counting networks in distributed systems. For counting problems in application domains which do ...
-
Article
A substitution theorem for graceful trees and its applications
(2009)A graceful labeling of a graph G = (V, E) assigns | V | distinct integers from the set {0, ..., | E |} to the vertices of G so that the absolute values of their differences on the | E | edges of G constitute the set {1, ...
-
Book Chapter
Algorithmic Game Theory and Applications
(John Wiley & Sons, Inc., 2007)Methods from game theory and mechanism design have been proven to be a powerful mathematical tool in order to understand, control, and efficiently design dynamic, complex networks, such as the Internet. Game theory provides ...
-
Conference Object
An upper and a lower bound for tick synchronization
(1992)The tick synchronization problem is defined and studied in the semi-synchronous complete network with n processes. An algorithm for the tick synchronization problem enables each process to make an estimate of real time ...
-
Article
Efficiency of semi-synchronous versus asynchronous systems: Atomic shared memory
(1993)The s-session problem is studied in asynchronous and semi-synchronous shared-memory systems, under a particular shared-memory communication primitive-b-atomic registers-where b > 1 is an integer reflecting the communication ...
-
Article
Balancing networks: State of the art
(1997)Balancing networks have recently been proposed by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 1991, pp. 348-358 as a new class of distributed, low-contention data structures ...
-
Conference Object
Wait-free solvability via combinatorial topology
(1996)This paper addresses the question of whether Algebraic Topology is really necessary for determining the characterization of solvable tasks for the case of general t. A Combinatorial Topology framework, totally bypassing ...