138 citations · 191 across the 22 of their papers we have counts for
7 papers · 1 filter
Computational Hardness of the Hylland-Zeckhauser Scheme
Thomas Chen, Xi Chen, Binghui Peng +1
We study the complexity of the classic Hylland-Zeckhauser scheme [HZ'79] for one-sided matching markets. We show that the problem of finding an -approximate equilibrium in the H…
The Platform Design Problem
Christos Papadimitriou, Kiran Vodrahalli, Mihalis Yannakakis
On-line firms deploy suites of software platforms, where each platform is designed to interact with users during a certain activity, such as browsing, chatting, socializing, emaili…
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
Vijay V. Vazirani, Mihalis Yannakakis
In 1979, Hylland and Zeckhauser \cite{hylland} gave a simple and general scheme for implementing a one-sided matching market using the power of a pricing mechanism. Their method ha…
Reachability for Branching Concurrent Stochastic Games
Kousha Etessami, Emanuel Martinov, Alistair Stewart +1
We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperf…
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer
Xi Chen, George Matikas, Dimitris Paparas +1
We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, m…
The Complexity of Optimal Multidimensional Pricing
Xi Chen, Ilias Diakonikolas, Dimitris Paparas +2
We resolve the complexity of revenue-optimal deterministic auctions in the unit-demand single-buyer Bayesian setting, i.e., the optimal item pricing problem, when the buyer's value…
Recursive Concurrent Stochastic Games
Kousha Etessami, Mihalis Yannakakis
We study Recursive Concurrent Stochastic Games (RCSGs), extending our recent analysis of recursive simple stochastic games to a concurrent setting where the two players choose move…