5 papers
Stable Voting is PSPACE-Complete
Ethan Dickey, Alexandros Psomas, Athina Terzoglou
Stable Voting and Simple Stable Voting, introduced by Holliday and Pacuit, are Condorcet-consistent voting rules defined recursively: a candidate wins if they would win after remov…
Hallucinating Flows for Optimal Mechanisms
Marios Mertzanidis, Athina Terzoglou
Myerson's seminal characterization of the revenue-optimal auction for a single item \cite{myerson1981optimal} remains a cornerstone of mechanism design. However, generalizing this…
Pseudo-Equilibria, or: How to Stop Worrying About Crypto and Just Analyze the Game
Alexandros Psomas, Athina Terzoglou, Yu Wei +1
We consider the problem of a game theorist analyzing a game that uses cryptographic protocols. Ideally, a theorist abstracts protocols as ideal, implementation-independent primitiv…
V3rified: Revelation vs Non-Revelation Mechanisms for Decentralized Verifiable Computation
Tiantian Gong, Aniket Kate, Alexandros Psomas +1
In the era of Web3, decentralized technologies have emerged as the cornerstone of a new digital paradigm. Backed by a decentralized blockchain architecture, the Web3 space aims to…
On the Robustness of Mechanism Design under Total Variation Distance
Anuran Makur, Marios Mertzanidis, Alexandros Psomas +1
We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distrib…