English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The linear complementarity problem, LCP(q,M), is defined as follows. Forgiven M,q find z such that q+Mz>=0, z>=0, z(q + M z)=0,or certify that there isno such z. It is well known that the problem of finding a Nash equilibrium fora bimatrix game (2-NASH) can be formulated as a linear complementarity problem(LCP). In addition, 2-NASH is known to be complete in the complexity class PPAD(Polynomial-time Parity Argument Directed). However, the ingeniouslyconstructed reduction (which is designed for any PPAD problem) is verycomplicated, so while of great theoretical significance, it is not practicalfor actually solving an LCP via 2-NASH, and it may not provide the potentialinsight that can be gained from studying the game obtained from a problemformulated as an LCP (e.g. market equilibrium). The main goal of this paper isthe construction of a simple explicit reduction of any LCP(q,M) that can beverified as belonging to PPAD via the graph induced by the generic Lemkealgorithm with some positive covering vector d, to a symmetric 2-NASH. Inparticular, any endpoint of this graph (with the exception of the initial pointof the algorithm) corresponds to either a solution or to a so-called secondaryray. Thus, an LCP problem is verified as belonging to PPAD if any secondary raycan be used to construct, in polynomial time, a certificate that there is nosolution to the problem. We achieve our goal by showing that for any M,q and apositive d satisfying a certain nondegeneracy assumption with respect to M, wecan simply and directly construct a symmetric 2-NASH whose Nash equilibriacorrespond one-to-one to the end points of the graph induced by LCP(q,M) andthe Lemke algorithm with a covering vector d. We note that for a given M thereduction works for all positive d with the exception of a subset of measure 0.

A direct reduction of PPAD Lemke-verified linear complementarity problems to bimatrix games