Cooperative games model the allocation of profit from joint actions,
following considerations such as stability and fairness. We propose the
reliability extension of such games, where agents may fail to participate in
the game. In the reliability extension, each agent only "survives" with a
certain probability, and a coalition's value is the probability that its
surviving members would be a winning coalition in the base game. We study
prominent solution concepts in such games, showing how to approximate the
Shapley value and how to compute the core in games with few agent types.
Signaling is an important topic in the study of asymmetric information in
economic settings. In particular, the transparency of information available to
a seller in an auction setting is a question of major interest. We introduce
the study of signaling when conducting a second price auction of a
probabilistic good whose actual instantiation is known to the auctioneer but
not to the bidders. This framework can be used to model impressions selling in
display advertising. We study the problem of computing a signaling scheme that
maximizes the auctioneer's revenue in a Bayesian setting.
We study mechanisms for an allocation of goods among agents, where agents
have no incentive to lie about their true values (incentive compatible) and for
which no agent will seek to exchange outcomes with another (envy-free).
Mechanisms satisfying each requirement separately have been studied
extensively, but there are few results on mechanisms achieving both.
We study auctions with additive valuations where agents have a limit on the
number of items they may receive. We refer to this setting as {\em capacitated
allocation games.} We seek truthful and envy free mechanisms that maximize the
social welfare. {\sl I.e.}, where agents have no incentive to lie and no agent
seeks to exchange outcomes with another. In 1983, Leonard showed that VCG with
Clarke Pivot payments (which is known to be truthful, individually rational,
and have no positive transfers), is also an envy free mechanism for the special
case of $n$ items and $n$ unit capacity agents.
We study envy-free mechanisms for scheduling tasks on unrelated machines
(agents) that approximately minimize the makespan. For indivisible tasks, we
put forward an envy-free poly-time mechanism that approximates the minimal
makespan to within a factor of $O(\log m)$, where $m$ is the number of
machines. We also show a lower bound of $\Omega(\log m / \log\log m)$. This
improves the recent result of Hartline {\sl et al.} \cite{Ahuva:2008} who give
an upper bound of $(m+1)/2$, and a lower bound of $2-1/m$.