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…
Competitive and Revenue-Optimal Pricing with Budgets
Simon Finster, Paul W. Goldberg, Edwin Lock
In markets with budget-constrained buyers, competitive equilibria need not be efficient in the utilitarian sense, or maximise the seller's revenue. We consider a setting with multi…
Decentralized Convergence to Equilibrium Prices in Trading Networks
Edwin Lock, Benjamin Patrick Evans, Eleonora Kreacic +4
We propose a decentralized market model in which agents can negotiate bilateral contracts. This builds on a similar, but centralized, model of trading networks introduced by Hatfie…
Solving Strong-Substitutes Product-Mix Auctions
Elizabeth Baldwin, Paul W. Goldberg, Paul Klemperer +1
This paper develops algorithms to solve strong-substitutes product-mix auctions. That is, it finds competitive equilibrium prices and quantities for agents who use this auction's b…
Learning Strong Substitutes Demand via Queries
Paul W. Goldberg, Edwin Lock, Francisco Marmolejo-CossÃo
This paper addresses the computational challenges of learning strong substitutes demand when given access to a demand (or valuation) oracle. Strong substitutes demand generalises t…
Decentralized Trading Networks: Equilibria and Fairness
Simon Finster, Paul W. Goldberg, Edwin Lock +1
We explore stability and fairness considerations in decentralized networked markets with bilateral contracts, building on the trading networks framework [Hatfield et al., 2013]. In…
Welfare-Maximizing Pooled Testing
Simon Finster, Michelle González Amador, Edwin Lock +3
Large-scale testing is crucial in pandemic containment, but resources are often prohibitively constrained. We study the optimal application of pooled testing for populations that a…
Characterising and recognising game-perfect graphs
Dominique Andres, Edwin Lock
Consider a vertex colouring game played on a simple graph with permissible colours. Two players, a maker and a breaker, take turns to colour an uncoloured vertex such that adja…