50
50
Sep 22, 2013
09/13
by
Kyle Burke; Shang-Hua Teng
texts
eye 50
favorite 0
comment 0
We create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to have a winner. Second, like many other interesting games such as Hex and Geography, we prove that deciding whether one can win our game is a PSPACE-complete problem. Third, there is an elegant balance in the game such that neither the first nor the second player always has a decisive advantage. We provide a web-based...
Source: http://arxiv.org/abs/cs/0702153v1
4
4.0
Jun 29, 2018
06/18
by
Wei Chen; Shang-Hua Teng
texts
eye 4
favorite 0
comment 0
We study network centrality based on dynamic influence propagation models in social networks. To illustrate our integrated mathematical-algorithmic approach for understanding the fundamental interplay between dynamic influence processes and static network structures, we focus on two basic centrality measures: (a) Single Node Influence (SNI) centrality, which measures each node's significance by its influence spread; and (b) Shapley Centrality, which uses the Shapley value of the influence...
Topics: Physics and Society, Physics, Computing Research Repository, Social and Information Networks
Source: http://arxiv.org/abs/1602.03780
51
51
Sep 19, 2013
09/13
by
Xi Chen; Shang-Hua Teng
texts
eye 51
favorite 0
comment 0
In this paper, inspired by the work of Megiddo on the formation of preferences and strategic analysis, we consider an early market model studied in the field of economic theory, in which each trader's utility may be influenced by the bundles of goods obtained by her social neighbors. The goal of this paper is to understand and characterize the impact of social influence on the complexity of computing and approximating market equilibria. We present complexity-theoretic and algorithmic results...
Source: http://arxiv.org/abs/1009.0309v1
38
38
Sep 22, 2013
09/13
by
Xi Chen; Shang-Hua Teng
texts
eye 38
favorite 0
comment 0
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a...
Source: http://arxiv.org/abs/cs/0702088v1
48
48
Sep 18, 2013
09/13
by
Daniel A. Spielman; Shang-Hua Teng
texts
eye 48
favorite 0
comment 0
We study the design of local algorithms for massive graphs. A local algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a non-empty local cluster, is nearly linear in the size of the cluster...
Source: http://arxiv.org/abs/0809.3232v1
69
69
Sep 18, 2013
09/13
by
Daniel A. Spielman; Shang-Hua Teng
texts
eye 69
favorite 0
comment 0
Spielman and Teng introduced the smoothed analysis of algorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could not be understood through the traditional worst-case and average-case analyses. In this talk, we survey some of the smoothed analyses that have been performed.
Source: http://arxiv.org/abs/math/0212413v1
77
77
Sep 21, 2013
09/13
by
Li-Sha Huang; Shang-Hua Teng
texts
eye 77
favorite 0
comment 0
We show that the problem of finding an \epsilon-approximate Nash equilibrium of an n by n two-person games can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, that is, there is no algorithm that can compute an \epsilon-approximate market equilibrium in...
Source: http://arxiv.org/abs/cs/0602090v1
47
47
Sep 20, 2013
09/13
by
Daniel A. Spielman; Shang-Hua Teng
texts
eye 47
favorite 0
comment 0
We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma))$. In contrast, the best known bound on the worst-case complexity of linear programming is $O (m^{3} L)$, where $L$ could be as large as $m$. We include an introduction to...
Source: http://arxiv.org/abs/cs/0301019v1
58
58
Sep 22, 2013
09/13
by
Adam Tauman Kalai; Shang-Hua Teng
texts
eye 58
favorite 0
comment 0
We consider the problem of PAC-learning decision trees, i.e., learning a decision tree over the n-dimensional hypercube from independent random labeled examples. Despite significant effort, no polynomial-time algorithm is known for learning polynomial-sized decision trees (even trees of any super-constant size), even when examples are assumed to be drawn from the uniform distribution on {0,1}^n. We give an algorithm that learns arbitrary polynomial-sized decision trees for {\em most product...
Source: http://arxiv.org/abs/0812.0933v1
58
58
Sep 21, 2013
09/13
by
Daniel A. Spielman; Shang-Hua Teng
texts
eye 58
favorite 0
comment 0
We introduce a new notion of graph sparsificaiton based on spectral similarity of graph Laplacians: spectral sparsification requires that the Laplacian quadratic form of the sparsifier approximate that of the original. This is equivalent to saying that the Laplacian of the sparsifier is a good preconditioner for the Laplacian of the original. We prove that every graph has a spectral sparsifier of nearly linear size. Moreover, we present an algorithm that produces spectral sparsifiers in time...
Source: http://arxiv.org/abs/0808.4134v3
46
46
Sep 22, 2013
09/13
by
Daniel A. Spielman; Shang-Hua Teng
texts
eye 46
favorite 0
comment 0
We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.
Source: http://arxiv.org/abs/cs/0111050v7
46
46
Sep 20, 2013
09/13
by
Daniel A. Spielman; Shang-Hua Teng
texts
eye 46
favorite 0
comment 0
We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y - \pinv{A} b}_{A} \leq \epsilon \norm{\pinv{A} b}_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon)),$ for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive...
Source: http://arxiv.org/abs/cs/0607105v5
100
100
Sep 22, 2013
09/13
by
Daniel A. Spielman; Shang-Hua Teng
texts
eye 100
favorite 0
comment 0
We present a linear-system solver that, given an $n$-by-$n$ symmetric positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb $, produces a vector $\xxt$ within relative distance $\epsilon$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log (n \kappa_{f} (A)/\epsilon)^{O (1)})$, where $\kappa_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (\kappa_{f} (A)) = O (b \log n)$, where...
Source: http://arxiv.org/abs/cs/0310036v2
71
71
Sep 18, 2013
09/13
by
Xi Chen; Xiaotie Deng; Shang-Hua Teng
texts
eye 71
favorite 0
comment 0
We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. This is the first of a series of results concerning the complexity of Nash equilibria. In particular, we prove the following theorems: Bimatrix does not have a fully polynomial-time approximation scheme unless every...
Source: http://arxiv.org/abs/0704.1678v1
68
68
Sep 21, 2013
09/13
by
Xi Chen; Xiaotie Deng; Shang-Hua Teng
texts
eye 68
favorite 0
comment 0
We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/\epsilon can compute an \epsilon-approximate Nash equilibrium of an n by nbimatrix game, unless PPAD is in P. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional cube with a constant side-length, such as on an n-dimensional cube with side-length 7, and show that they are...
Source: http://arxiv.org/abs/cs/0602043v2
6
6.0
Jun 29, 2018
06/18
by
Kristina Lerman; Shang-Hua Teng; Xiaoran Yan
texts
eye 6
favorite 0
comment 0
It is common for people to access multiple social networks, for example, using phone, email, and social media. Together, the multi-layer social interactions form a "integrated social network." How can we extend well developed knowledge about single-layer networks, including vertex centrality and community structure, to such heterogeneous structures? In this paper, we approach these challenges by proposing a principled framework of network composition based on a unified dynamical...
Topics: Physics and Society, Physics, Computing Research Repository, Social and Information Networks
Source: http://arxiv.org/abs/1609.01641
51
51
Sep 22, 2013
09/13
by
Arvind Sankar; Daniel A. Spielman; Shang-Hua Teng
texts
eye 51
favorite 0
comment 0
Let $\orig{A}$ be any matrix and let $A$ be a slight random perturbation of $\orig{A}$. We prove that it is unlikely that $A$ has large condition number. Using this result, we prove it is unlikely that $A$ has large growth factor under Gaussian elimination without pivoting. By combining these results, we bound the smoothed precision needed by Gaussian elimination without pivoting. Our results improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan...
Source: http://arxiv.org/abs/cs/0310022v4
136
136
Sep 17, 2013
09/13
by
Dan A. Spielman; Shang-hua Teng; Alper Ungor
texts
eye 136
favorite 0
comment 0
In this paper, we analyze the complexity of natural parallelizations of Delaunay refinement methods for mesh generation. The parallelizations employ a simple strategy: at each iteration, they choose a set of ``independent'' points to insert into the domain, and then update the Delaunay triangulation. We show that such a set of independent points can be constructed efficiently in parallel and that the number of iterations needed is $O(\log^2(L/s))$, where $L$ is the diameter of the domain, and...
Source: http://arxiv.org/abs/cs/0207063v1
81
81
Sep 19, 2013
09/13
by
John Dunagan; Daniel A. Spielman; Shang-Hua Teng
texts
eye 81
favorite 0
comment 0
We show that the smoothed complexity of the logarithm of Renegar's condition number is O(log (n/sigma)).
Source: http://arxiv.org/abs/cs/0302011v2
4
4.0
Jun 30, 2018
06/18
by
Christian Borgs; Jennifer Chayes; Adrian Marple; Shang-Hua Teng
texts
eye 4
favorite 0
comment 0
We provide the first social choice theory approach to the question of what constitutes a community in a social network. Inspired by the classic preferences models in social choice theory, we start from an abstract social network framework, called preference networks; these consist of a finite set of members where each member has a total-ranking preference of all members in the set. Within this framework, we develop two complementary approaches to axiomatically study the formation and structures...
Topics: Computational Complexity, Computer Science and Game Theory, Computing Research Repository, Data...
Source: http://arxiv.org/abs/1410.5152
47
47
Sep 18, 2013
09/13
by
Nina Amenta; Marshall Bern; David Eppstein; Shang-Hua Teng
texts
eye 47
favorite 0
comment 0
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression...
Source: http://arxiv.org/abs/cs/9809037v2
3
3.0
Jun 30, 2018
06/18
by
Rumi Ghosh; Kristina Lerman; Shang-Hua Teng; Xiaoran Yan
texts
eye 3
favorite 0
comment 0
We study the interplay between a dynamic process and the structure of the network on which it is defined. Specifically, we examine the impact of this interaction on the quality-measure of network clusters and node centrality. This enables us to effectively identify network communities and important nodes participating in the dynamics. As the first step towards this objective, we introduce an umbrella framework for defining and characterizing an ensemble of dynamic processes on a network. This...
Topics: Physics, Discrete Mathematics, Computing Research Repository, Physics and Society, Social and...
Source: http://arxiv.org/abs/1406.3387
78
78
Sep 23, 2013
09/13
by
Christian Borgs; Michael Brautbar; Jennifer Chayes; Shang-Hua Teng
texts
eye 78
favorite 0
comment 0
A fundamental problem arising in many applications in Web science and social network analysis is, given an arbitrary approximation factor $c>1$, to output a set $S$ of nodes that with high probability contains all nodes of PageRank at least $\Delta$, and no node of PageRank smaller than $\Delta/c$. We call this problem {\sc SignificantPageRanks}. We develop a nearly optimal, local algorithm for the problem with runtime complexity $\tilde{O}(n/\Delta)$ on networks with $n$ nodes. We show that...
Source: http://arxiv.org/abs/1202.2771v5
57
57
Sep 19, 2013
09/13
by
Nikolaos Laoutaris; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng
texts
eye 57
favorite 0
comment 0
Motivated by applications in peer-to-peer and overlay networks we define and study the \emph{Bounded Degree Network Formation} (BDNF) game. In an $(n,k)$-BDNF game, we are given $n$ nodes, a bound $k$ on the out-degree of each node, and a weight $w_{vu}$ for each ordered pair $(v,u)$ representing the traffic rate from node $v$ to node $u$. Each node $v$ uses up to $k$ directed links to connect to other nodes with an objective to minimize its average distance, using weights $w_{vu}$, to all...
Source: http://arxiv.org/abs/cs/0701071v2
60
60
Sep 23, 2013
09/13
by
Xi Chen; Decheng Dai; Ye Du; Shang-Hua Teng
texts
eye 60
favorite 0
comment 0
We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time.
Source: http://arxiv.org/abs/0904.0644v1
43
43
Sep 23, 2013
09/13
by
Michael Elkin; Yuval Emek; Daniel A. Spielman; Shang-Hua Teng
texts
eye 43
favorite 0
comment 0
We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).
Source: http://arxiv.org/abs/cs/0411064v5
45
45
Sep 22, 2013
09/13
by
Laura J. Poplawski; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng
texts
eye 45
favorite 0
comment 0
We study the complexity of computing equilibria in two classes of network games based on flows - fractional BGP (Border Gateway Protocol) games and fractional BBC (Bounded Budget Connection) games. BGP is the glue that holds the Internet together and hence its stability, i.e. the equilibria of fractional BGP games (Haxell, Wilfong), is a matter of practical importance. BBC games (Laoutaris et al) follow in the tradition of the large body of work on network formation games and capture a variety...
Source: http://arxiv.org/abs/0812.0598v2
74
74
Sep 18, 2013
09/13
by
Rumi Ghosh; Kristina Lerman; Tawan Surachawala; Konstantin Voevodski; Shang-Hua Teng
texts
eye 74
favorite 0
comment 0
The random walk is fundamental to modeling dynamic processes on networks. Metrics based on the random walk have been used in many applications from image processing to Web page ranking. However, how appropriate are random walks to modeling and analyzing social networks? We argue that unlike a random walk, which conserves the quantity diffusing on a network, many interesting social phenomena, such as the spread of information or disease on a social network, are fundamentally non-conservative....
Source: http://arxiv.org/abs/1102.4639v3
18
18
Jun 26, 2018
06/18
by
Dehua Cheng; Yu Cheng; Yan Liu; Richard Peng; Shang-Hua Teng
texts
eye 18
favorite 0
comment 0
We consider a fundamental algorithmic question in spectral graph theory: Compute a spectral sparsifier of random-walk matrix-polynomial $$L_\alpha(G)=D-\sum_{r=1}^d\alpha_rD(D^{-1}A)^r$$ where $A$ is the adjacency matrix of a weighted, undirected graph, $D$ is the diagonal matrix of weighted degrees, and $\alpha=(\alpha_1...\alpha_d)$ are nonnegative coefficients with $\sum_{r=1}^d\alpha_r=1$. Recall that $D^{-1}A$ is the transition matrix of random walks on the graph. The sparsification of...
Topics: Statistics, Discrete Mathematics, Computing Research Repository, Learning, Data Structures and...
Source: http://arxiv.org/abs/1502.03496
69
69
Sep 18, 2013
09/13
by
Michael A. Bender; Bradley C. Kuszmaul; Shang-Hua Teng; Kebin Wang
texts
eye 69
favorite 0
comment 0
A mesh is a graph that divides physical space into regularly-shaped regions. Meshes computations form the basis of many applications, e.g. finite-element methods, image rendering, and collision detection. In one important mesh primitive, called a mesh update, each mesh vertex stores a value and repeatedly updates this value based on the values stored in all neighboring vertices. The performance of a mesh update depends on the layout of the mesh in memory. This paper shows how to find a memory...
Source: http://arxiv.org/abs/0705.1033v2
19
19
Jun 30, 2018
06/18
by
Dehua Cheng; Yu Cheng; Yan Liu; Richard Peng; Shang-Hua Teng
texts
eye 19
favorite 0
comment 0
Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf \mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficient access to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that $${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ The solution is based on factoring...
Topics: Computation, Statistics, Mathematics, Computing Research Repository, Numerical Analysis, Data...
Source: http://arxiv.org/abs/1410.5392
66
66
Sep 21, 2013
09/13
by
Jonathan A. Kelner; James R. Lee; Gregory N. Price; Shang-Hua Teng
texts
eye 66
favorite 0
comment 0
We present a method for proving upper bounds on the eigenvalues of the graph Laplacian. A main step involves choosing an appropriate "Riemannian" metric to uniformize the geometry of the graph. In many interesting cases, the existence of such a metric is shown by examining the combinatorics of special types of flows. This involves proving new inequalities on the crossing number of graphs. In particular, we use our method to show that for any positive integer k, the kth smallest...
Source: http://arxiv.org/abs/1008.3594v3
136
136
Sep 23, 2013
09/13
by
Shiva Kintali; Laura J. Poplawski; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng
texts
eye 136
favorite 0
comment 0
In this paper, we resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance: Fractional Stable Paths Problem (FSPP) [21] - Internet routing; Core of Balanced Games [41] - Economics and Game theory; Scarf's Lemma [41] - Combinatorics; Hypergraph Matching [1]- Social Choice and Preference Systems; Fractional Bounded Budget Connection Games...
Source: http://arxiv.org/abs/0904.1435v1
19
19
Aug 11, 2020
08/20
by
Konstantin Voevodski; Maria-Florina Balcan; Heiko Rglin; Shang-Hua Teng; Yu Xia
data
eye 19
favorite 0
comment 0
Source: http://academictorrents.com/details/9dd1a91e17e2294624f643e3f1073cb26aa39a2c
44
44
Sep 19, 2013
09/13
by
Konstantin Voevodski; Maria-Florina Balcan; Heiko Roglin; Shang-Hua Teng; Yu Xia
texts
eye 44
favorite 0
comment 0
Given a point set S and an unknown metric d on S, we study the problem of efficiently partitioning S into k clusters while querying few distances between the points. In our model we assume that we have access to one versus all queries that given a point s in S return the distances between s and all other points. We show that given a natural assumption about the structure of the instance, we can efficiently find an accurate clustering using only O(k) distance queries. Our algorithm uses an...
Source: http://arxiv.org/abs/1009.5168v2
45
45
Sep 18, 2013
09/13
by
Maria-Florina Balcan; Christian Borgs; Mark Braverman; Jennifer Chayes; Shang-Hua Teng
texts
eye 45
favorite 0
comment 0
A central problem in e-commerce is determining overlapping communities among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, each with a vector characterizing its preference for all other elements in the set. We define a...
Source: http://arxiv.org/abs/1201.4899v2
52
52
Sep 22, 2013
09/13
by
Konstantin Voevodski; Maria-Florina Balcan; Heiko Roglin; Shang-Hua Teng; Yu Xia
texts
eye 52
favorite 0
comment 0
We study the problem of efficiently clustering protein sequences in a limited information setting. We assume that we do not know the distances between the sequences in advance, and must query them during the execution of the algorithm. Our goal is to find an accurate clustering using few queries. We model the problem as a point set $S$ with an unknown metric $d$ on $S$, and assume that we have access to \emph{one versus all} distance queries that given a point $s \in S$ return the distances...
Source: http://arxiv.org/abs/1101.3620v2
83
83
Sep 18, 2013
09/13
by
Nikolaos Laoutaris; Laura J. Poplawski; Rajmohan Rajaraman; Ravi Sundaram; Shang-Hua Teng
texts
eye 83
favorite 0
comment 0
Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game - we have a collection of n players or nodes each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the...
Source: http://arxiv.org/abs/0806.1727v1
39
39
Sep 19, 2013
09/13
by
Paul Christiano; Jonathan A. Kelner; Aleksander Madry; Daniel A. Spielman; Shang-Hua Teng
texts
eye 39
favorite 0
comment 0
We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges,...
Source: http://arxiv.org/abs/1010.2921v2
25
25
Jun 28, 2018
06/18
by
Yu Cheng; Ho Yee Cheung; Shaddin Dughmi; Ehsan Emamjomeh-Zadeh; Li Han; Shang-Hua Teng
texts
eye 25
favorite 0
comment 0
We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function $g$ from the $n$-dimensional hypercube to the bounded interval $[-1,1]$, and an $n \times m$ matrix $A$ with bounded entries, maximize $g(Ax)$ over $x$ in the $m$-dimensional simplex. This problem arises naturally when one seeks to design a lottery over items for sale in an auction, or craft the posterior beliefs for agents...
Topics: Computing Research Repository, Data Structures and Algorithms, Computer Science and Game Theory
Source: http://arxiv.org/abs/1508.03679
