88 citations · 311 across the 59 of their papers we have counts for
17 papers · 1 filter
Buy-Many Mechanisms for Many Unit-Demand Buyers
Shuchi Chawla, Rojin Rezvan, Yifeng Teng +1
A recent line of research has established a novel desideratum for designing approximately-revenue-optimal multi-item mechanisms, namely the buy-many constraint. Under this constrai…
Pricing Ordered Items
Shuchi Chawla, Rojin Rezvan, Yifeng Teng +1
We study the revenue guarantees and approximability of item pricing. Recent work shows that with heterogeneous items, item-pricing guarantees an approximation to th…
Menu-size Complexity and Revenue Continuity of Buy-many Mechanisms
Shuchi Chawla, Yifeng Teng, Christos Tzamos
We study the multi-item mechanism design problem where a monopolist sells heterogeneous items to a single buyer. We focus on buy-many mechanisms, a natural class of mechanisms…
The Complexity of Black-Box Mechanism Design with Priors
Evangelia Gergatsouli, Brendan Lucier, Christos Tzamos
We study black-box reductions from mechanism design to algorithm design for welfare maximization in settings of incomplete information. Given oracle access to an algorithm for an u…
Diversity and Exploration in Social Learning
Nicole Immorlica, Jieming Mao, Christos Tzamos
In consumer search, there is a set of items. An agent has a prior over her value for each item and can pay a cost to learn the instantiation of her value. After exploring a subset…
Buy-many mechanisms are not much better than item pricing
Shuchi Chawla, Yifeng Teng, Christos Tzamos
Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps…
Combinatorial Assortment Optimization
Nicole Immorlica, Brendan Lucier, Jieming Mao +2
Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each…
Certified Computation from Unreliable Datasets
Themis Gouleakis, Christos Tzamos, Manolis Zampetakis
A wide range of learning tasks require human input in labeling massive data. The collected data though are usually low quality and contain inaccuracies and errors. As a result, mod…
Truthful Facility Location with Additive Errors
Iddan Golomb, Christos Tzamos
We address the problem of locating facilities on the interval based on reports from strategic agents. The cost of each agent is her distance to the closest facility, and th…
Who to Trust for Truthfully Maximizing Welfare?
Dimitris Fotakis, Christos Tzamos, Emmanouil Zampetakis
We introduce a general approach based on \emph{selective verification} and obtain approximate mechanisms without money for maximizing the social welfare in the general domain of ut…
Optimal Pricing is Hard
Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos
We show that computing the revenue-optimal deterministic auction in unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is computationally hard even in singl…
Mechanism Design via Optimal Transport
Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos
Optimal mechanisms have been provided in quite general multi-item settings, as long as each bidder's type distribution is given explicitly by listing every type in the support alon…
The Value of Knowing Your Enemy
Christos Tzamos, Christopher A. Wilkens
Many auction settings implicitly or explicitly require that bidders are treated equally ex-ante. This may be because discrimination is philosophically or legally impermissible, or…
Strong Duality for a Multiple-Good Monopolist
Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos
We characterize optimal mechanisms for the multiple-good monopoly problem and provide a framework to find them. We show that a mechanism is optimal if and only if a measure der…
Strategy-Proof Facility Location for Concave Cost Functions
Dimitris Fotakis, Christos Tzamos
We consider k-Facility Location games, where n strategic agents report their locations on the real line, and a mechanism maps them to k facilities. Each agent seeks to minimize his…
The Complexity of Optimal Mechanism Design
Constantinos Daskalakis, Alan Deckelbaum, Christos Tzamos
Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders. Generalizing this work to selling multiple items at on…
On the Power of Deterministic Mechanisms for Facility Location Games
Dimitris Fotakis, Christos Tzamos
We consider K-Facility Location games, where n strategic agents report their locations in a metric space, and a mechanism maps them to K facilities. Our main result is an elegant c…