Abstract: We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some parameter k, e.g., committee elections. We are interested in the minimax approval voting rule in which the outcome represents a compromise among the voters, in the sense that the maximum distance between the preference of any voter and the outcome is as small as possible. This voting rule has two main drawbacks. First, computing an outcome that minimizes the maximum distance is computationally hard. Furthermore, any algorithm that always returns such an outcome provides
incentives to voters to misreport their true preferences.
In order to circumvent these drawbacks, we consider approximation algorithms, i.e., algorithms that produce an outcome that approximates the minimax distance for any given instance. Such algorithms can be considered as alternative voting rules. We present a polynomial-time 2-approximation algorithm that uses a natural linearprogramming relaxation for the underlying optimization problem and deterministically
rounds the fractional solution in order to compute the outcome; this result improves upon the previously best known algorithm that has an approximation ratio of 3. We are furthermore interested in approximation algorithms that are resistant to manipulation by (coalitions of) voters, i.e., algorithms that do not motivate voters to misreport their true preferences in order to improve their distance from the outcome. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms.
Abstract: In this work we study the tractability of well supported approximate
Nash Equilibria (SuppNE in short) in bimatrix games. In view
of the apparent intractability of constructing Nash Equilibria (NE in
short) in polynomial time, even for bimatrix games, understanding the
limitations of the approximability of the problem is of great importance.
We initially prove that SuppNE are immune to the addition of arbitrary
real vectors to the rows (columns) of the row (column) player¢s
payoff matrix. Consequently we propose a polynomial time algorithm
(based on linearprogramming) that constructs a 0.5−SuppNE for arbitrary
win lose games.
We then parameterize our technique for win lose games, in order to
apply it to arbitrary (normalized) bimatrix games. Indeed, this new technique
leads to a weaker {\"o}−SuppNE for win lose games, where {\"o} = √5−1
2
is the golden ratio. Nevertheless, this parameterized technique extends
nicely to a technique for arbitrary [0, 1]−bimatrix games, which assures
a 0.658−SuppNE in polynomial time.
To our knowledge, these are the first polynomial time algorithms providing
{\aa}−SuppNE of normalized or win lose bimatrix games, for some
nontrivial constant {\aa} ∈ [0, 1), bounded away from 1.
Abstract: The simplex method has been successfully used in solving linearprogramming problems for many years. Parallel approaches have also extensively been studied due to the intensive computations required, especially for the solution of large linear problems (LPs). In this paper we present a highly scalable parallel implementation framework of the standard full tableau simplex method on a highly parallel (distributed memory) environment. Specifically, we have designed and implemented a suitable column distribution scheme as well as a row distribution scheme and we have entirely tested our implementations over a considerably powerful distributed platform (linux cluster with myrinet interface). We then compare our approaches (a) among each other for variable number of problem size (number of rows and columns) and (b) to other recent and valuable corresponding efforts in the literature. In most cases, the column distribution scheme performs quite/much better than the row distribution scheme. Moreover, both schemes (even the row distribution scheme over large-scale problems) lead to particularly high speedup and efficiency values, which are considerably better in all cases than the ones achieved in other similar research efforts and implementations. Moreover, we further evaluate our basic parallelization scheme over very large LPs in order to validate more reliably the high efficiency and scalability achieved.
Abstract: In this paper we study the problem of assigning transmission ranges to the nodes of a multihop
packet radio network so as to minimize the total power consumed under the constraint
that adequate power is provided to the nodes to ensure that the network is strongly connected
(i.e., each node can communicate along some path in the network to every other node). Such
assignment of transmission ranges is called complete. We also consider the problem of achieving
strongly connected bounded diameter networks.
For the case of n + 1 colinear points at unit distance apart (the unit chain) we give a tight
asymptotic bound for the minimum cost of a range assignment of diameter h when h is a xed
constant and when h>(1 + ) log n, for some constant > 0. When the distances between the
colinear points are arbitrary, we give an O(n4) time dynamic programming algorithm for nding
a minimum cost complete range assignment.
For points in three dimensions we show that the problem of deciding whether a complete
range assignment of a given cost exists, is NP-hard. For the same problem we give an O(n2)
time approximation algorithm which provides a complete range assignment with cost within a
factor of two of the minimum. The complexity of this problem in two dimensions remains open,
while the approximation algorithm works in this case as well.
Abstract: In view of the apparent intractability of constructing Nash Equilibria (NE
in short) in polynomial time, even for bimatrix games, understanding the limitations
of the approximability of the problem is an important challenge.
In this work we study the tractability of a notion of approximate equilibria in bimatrix
games, called well supported approximate Nash Equilibria (SuppNE in short).
Roughly speaking, while the typical notion of approximate NE demands that each
player gets a payoff at least an additive term less than the best possible payoff, in a
SuppNE each player is assumed to adopt with positive probability only approximate
pure best responses to the opponent¢s strategy.
As a first step, we demonstrate the existence of SuppNE with small supports and
at the same time good quality. This is a simple corollary of Alth{\"o}fer¢s Approximation
Lemma, and implies a subexponential time algorithm for constructing SuppNE of
arbitrary (constant) precision.
We then propose algorithms for constructing SuppNE in win lose and normalized
bimatrix games (i.e., whose payoff matrices take values from {0, 1} and [0, 1] respectively).
Our methodology for attacking the problem is based on the solvability of zero sum bimatrix games (via its connection to linearprogramming) and provides a
0.5-SuppNE for win lose games and a 0.667-SuppNE for normalized games.
To our knowledge, this paper provides the first polynomial time algorithms constructing
{\aa}-SuppNE for normalized or win lose bimatrix games, for any nontrivial
constant 0 ≤{\aa} <1, bounded away from 1.
