enter search term and/or author name
A Truthful Mechanism for the Generalized Assignment Problem
Salman Fadaei, Martin Bichler
Article No.: 14
We propose a truthful-in-expectation, (1-1/e)-approximation mechanism for a strategic variant of the generalized assignment problem (GAP). In GAP, a set of items has to be optimally assigned to a set of bins without exceeding the capacity...
Dynamics at the Boundary of Game Theory and Distributed Computing
Aaron D. Jaggard, Neil Lutz, Michael Schapira, Rebecca N. Wright
Article No.: 15
We use ideas from distributed computing and game theory to study dynamic and decentralized environments in which computational nodes, or decision makers, interact strategically and with limited information. In such environments, which arise in...
Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare
Elliot Anshelevich, Koushik Kar, Shreyas Sekar
Article No.: 16
We study the classic setting of envy-free pricing, in which a single seller chooses prices for its many items, with the goal of maximizing revenue once the items are allocated. Despite the large body of work addressing such settings, most versions...
A Geometric Perspective on Minimal Peer Prediction
Rafael Frongillo, Jens Witkowski
Article No.: 17
Minimal peer prediction mechanisms truthfully elicit private information (e.g., opinions or experiences) from rational agents without the requirement that ground truth is eventually revealed. In this article, we use a geometric perspective to...