Publications (13)
The Computational Complexity of the Housing Market
Edwin Lock, Zephyr Qiu, Alexander Teytelboym
We prove that the classic problem of finding a competitive equilibrium in an exchange economy with indivisible goods, money, and unit-demand agents is PPAD-complete. In this "housi…
Maximising the Benefits of an Acutely Limited Number of COVID-19 Tests
Jakob Jonnerby, Philip Lazos, Edwin Lock +4
We propose a novel testing and containment strategy in order to contain the spread of SARS-CoV2 while permitting large parts of the population to resume social and economic activit…
Efficiently Restructuring Sovereign Debt via Arctic Auctions with Convex Costs
Jugal Garg, Edwin Lock, Vijay V. Vazirani
We study the problem of computing competitive equilibria in the Arctic product-mix auction, originally developed for the Icelandic government for exchanging blocked financial accou…
The Computational Intractability of Not Worst Responding
Mete Åeref Ahunbay, Paul W. Goldberg, Edwin Lock +3
Finding, counting, or determining the existence of Nash equilibria, where players must play optimally given each others' actions, are known to be computational intractable problems…
Optimal Testing and Containment Strategies for Universities in Mexico amid COVID-19
Luis Benavides-Vázquez, Héctor Alonso Guzmán-Gutiérrez, Jakob Jonnerby +5
This work sets out a testing and containment framework developed for reopening universities in Mexico following the lockdown due to COVID-19. We treat diagnostic testing as a resou…
Accelerated Preference Elicitation with LLM-Based Proxies
David Huang, Francisco Marmolejo-CossÃo, Edwin Lock +1
Bidders in combinatorial auctions face significant challenges when describing their preferences to an auctioneer. Classical work on preference elicitation focuses on query-based te…