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

This paper resolves two of the handful of remaining questions on thecomputability of market equilibria, a central theme within algorithmic gametheory (AGT). Our results are as follows:  1. We show FIXP-hardness of computing equilibria in Arrow-Debreu marketsunder Leontief utility functions, and Arrow-Debreu markets under linear utilityfunctions and Leontief production sets. We note that these are the firstFIXP-hardness results ever since the introduction of the class FIXP and thehardness of 3-Nash established therein.  2. We note that for the problems stated above, the corresponding resultsshowing membership in FIXP were established after imposing suitable sufficiencyconditions to render the problems total, as is customary in economics. However,if all instances are under consideration, then in both cases we prove that theproblem of deciding if a given instance admits an equilibrium is\Exists-R-complete, where \Exists-R is the class of decision problems which canbe reduced in polynomial time to Existential Theory of the Reals.  3. For Arrow-Debreu markets under Leontief utility functions and a constantnumber of agents, we give a polynomial-time algorithm for computing anequilibrium. This settles part of an open problem of Devanur and Kannan(FOCS'08).  We note that PLC utilities are about the most general utilities of interestin economics and several fundamental utility functions studied within AGT arespecial cases of it. Several important problems, which have been shown to be inFIXP, are waiting for proofs of FIXP-hardness. In this context, our techniqueof reducing from 3-Nash to Multivariate Polynomial Equations and then to theproblem is likely to be useful in the future.

Settling the Complexity of Arrow-Debreu Markets under Leontief and PLC Utilities, using the Classes FIXP and \Exists-R