Vårt rst resultat visar medlemskap i PPAD för problemet med att beräkna ungefärlig jämvikt för en Arrow-Debreu utbytesmarknad för bitvis-linjär konkava (PLC) allmännyttiga funktioner. Som en följd av detta får vi också medlemskap i PPAD för Leontiefs allmännyttiga funktioner. Detta avgör en öppen fråga om Vazirani och Yannakakis (2011). Därefter visar vi FIXP-hårdhet av computing equilibria i ArrowDebreu utbytesmarknader under Leontief allmännyttiga funktioner, och Arrow-Debreu marknader under linjära allmännyttiga funktioner och Leontief produktion uppsättningar, vilket löser dessa öppna frågor av Vazirani och Yannakakis (2011). Som korollärer får vi FIXP-hårdhet för PLC-verktyg och för Arrow-Debreu-marknader under linjära allmännyttiga funktioner och polyhedral produktionssätt. I samtliga fall, som krävs enligt FIXP, kommer den uppsättning fall som kartlagts på att erkänna jämvikt, d.v.s., kommer att vara "ja" fall. Om alla fall är under övervägande, då bevisar vi i alla fall att problemet med att avgöra om en viss instans medger en jämvikt är ETR-fullständig, där ETR är klass Existentiell Teori av Reals. Som en följd av resultaten ovan, och det faktum att medlemskap i FIXP har fastställts för PLC verktyg, hela beräknings di kulty Arrow-Debreu marknader under PLC allmännyttiga funktioner ligger i Leontief allmännyttiga subcase. Detta är kanske den mest oväntade aspekten av vårt resultat, eftersom Leontief verktyg är avsedda för fallet att varor är perfekta komplement, medan PLC verktyg är mycket allmänna, fånga inte bara fall när varor är komplement och substitut, men också godtyckliga kombinationer av dessa och mycket mer. Slutligen, vi ger en polynom tid algoritm för nding en jämvikt i Arrow-Debreu börser under Leontief
Detta följdes av ett bevis på FIXP-hårdhet för Arrow-Debreu marknader med Leontief och PLC verktyg REF.
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}