We study a combinatorial market design problem, where a collection of indivisible objects is
to be priced and sold to potential buyers subject to equilibrium constraints. The classic …

This paper presents inapproximability results for paradigmatic multi-dimensional truthful
mechanism design problems. We first show a lower bound of 2− 1 n for the scheduling …

We consider profit maximizing (incentive compatible) mechanism design in general
environments that include, eg, position auctions (for selling advertisements on Internet …

We study the makespan minimization problem with unrelated selfish machines under the
assumption that job sizes are stochastic. We design simple truthful mechanisms that under …

Multi-agent resource allocation is an important and well-studied problem within AI and
economics. It is generally assumed that the quantity of each resource is known a priori …

We study the mechanism design version of the unrelated machines scheduling problem,
which is at the core of Algorithmic Game Theory and was first proposed and studied in a …

When allocating indivisible resources or tasks, an envy-free allocation or equitable
allocation may not exist. We present a sufficient condition and an algorithm to achieve envy …

Optimally allocating cellphone spectrum, advertisements on the Internet, and landing slots at
airports is computationally intractable. When the participants may strategize, not only must …

Envy-freeness is a well-known fairness concept for analyzing mechanisms. Its traditional
definition requires that no individual envies another individual. However, an individual (or a …

We consider k-envy-free assignments for scheduling problems in which the completion time
of each machine is not k times larger than the one she could achieve by getting the jobs of …