Workshop on Risk Aversion in Algorithmic Game Theory and Mechanism Design
June 7, 2012, Valencia, Spain. (in conjunction with ACMEC 2012)

[Synopsis]
[Dates]
[Schedule]
[Plenary talk]
[Abstracts]
[CFP]
[Organization]
Synopsis
The VonNeumann Morgenstern expected utility theory addresses risk aversion
by concave utility functions for wealth. Nonexpected utility theories,
originally posed because of various "paradoxes" such as the Allais paradox,
provide alternative answers to human concerns.
Finance has taken a different direction altogether,
from the Markowitz meanvariance framework to the recent developments
on coherent measures of risk.
The purpose of this workshop is to immingle different communities:
(a) The CS oriented AGT community
(b) The Finance oriented community, and
(c) the nonEUT community such as those dealing with prospect theory.
Hopefully, this will lead to profitable interaction
between these (rather disjoint) communities.
The workshop will be held in conjunction with the ACM Conference on Electronic Commerce.
Submission Deadline  Tuesday, April 10th 
Acceptance Notification  Monday, April 30th 
Workshop  Thursday, June 7th 
Schedule
9:009:50  Contributed Session. Various topics. 
 Othman, Sandholm: Inventorybased versus Priorbased Options Trading Agents

 Chitnis, Hajiaghayi, Katz, Mukherjee: A GameTheoretic Model Motivated by the DARPA Network Challenge

Coffee break 

10:3011:40  Plenary talk: Garud Iyengar: Optimizing with Risk Measures 

11:4012:30  Contributed Session. Network Routing. 
 Hoy: The concavity of atomic splittable congestion games with nonlinear utility functions

 Gui, Ergun: A Robustness Analysis of a Capacity Exchange Mechanism in Multicommodity Networks under Demand Uncertainty


Lunch break 

2:003:15  Contributed Session. Mechanism Design. 
 Dughmi, Peres: Mechanisms for Risk Averse Agents, Without Loss

 Bhalgat, Chakraborty, Khanna: Mechanism Design and Risk Aversion

 Azar, Micali: Optimal Parametric Auctions

Abstracts
Mechanism Design and Risk Aversion
(pdf)
by Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna.
We develop efficient algorithms to construct utility maximizing mechanisms in the presence of risk averse players (buyers and sellers) in Bayesian single parameter and multiparameter settings. We model risk aversion by a concave utility function, and players play strategically to maximize their expected utility. Bayesian mechanism design has usually focused on maximizing expected revenue in a {\em risk neutral} environment, {\em i.e.} where all the buyers and the seller have linear utility, and no succinct characterization of expected utility maximizing mechanisms is known even for singleparameter multiunit auctions.
We first consider the problem of designing optimal DSIC (dominant strategy incentive compatible) mechanism for a risk averse seller in
the case of multiunit auctions, and we give a polytime computable deterministic sequential posted pricing mechanism (SPM) that for any $\eps > 0$, yields a $(11/e\eps)$approximation to the expected utility of the seller in an optimal DSIC mechanism. Our result is based on a novel application of a correlation gap bound, along with {\em splitting} and {\em merging} of random variables to redistribute probability mass across buyers. This allows us to reduce our problem to that of checking feasibility of a small number of distinct configurations, each of which corresponds to a covering LP. A feasible solution to the LP gives us the distribution on prices for each buyer to use in a randomized SPM. We get a deterministic SPM by sampling from this randomized SPM. Our techniques extend to the multiparameter setting with unit demand buyers.
We next consider the setting when buyers as well as the seller are risk averse, and the objective is to maximize the seller's expected utility. We design a truthfulinexpectation mechanism whose utility is a $\left(\left(1\frac{1}{e}\right)^2\times\max\left(1\frac{1}{e}, 1\frac{1}{\sqrt{2\pi k}}\right)\right)$approximation to the optimal BIC mechanism under two mild assumptions: (a) ex post individual rationality and (b) no positive transfers. Our mechanism consists of multiple rounds. It considers each buyer in a round with small probability, and when a buyer is considered, it allocates an item to the buyer according to payment functions that are computed using stochastic techniques developed for DSIC mechanisms. Lastly, we consider the problem of revenue maximization for a risk neutral seller in presence of risk averse buyers, and give a polytime algorithm to construct a truthfulinexpectation mechanism whose expected revenue is a $\max\left(1\frac{1}{e}, 1\frac{1}{\sqrt{2\pi k}}\right)$approximation to the expected revenue of the optimal BIC mechanism, bounding the gap between these two classes of mechanisms.
We believe that the techniques developed in this work will be useful in handling other stochastic optimization problems with a concave objective function.
Optimal Parametric Auctions
by Pablo Azar and Silvio Micali.
We study the problem of an auctioneer who wants to maximize her prots. In our model, there are n
buyers with private valuations drawn from independent distributions. When these distributions
are known to the seller, Myerson's optimal auction [20] is a well known mechanism that maximizes
revenue. However, in many cases it is too strong to assume that the seller knows these distributions.
We propose an alternative model where the seller only knows the mean and variance of each distribution. We call mechanisms that only use this information parametric auctions. We construct
such auctions for settings where the seller only has one copy of the good to sell, and when she has an
infinite number of identical copies of the good (digital auctions). For a very large class of distributions,
including (but not limited to) distributions with a monotone hazard rate, our auctions achieve a constant
fraction of the revenue of Myerson's auction.
When the seller has absolutely no knowledge about the distributions, it is well known that no auction
can achieve a constant fraction of the optimal revenue when the players are not identically distributed.
Our parametric model gives the seller a small amount of extra information, allowing her to construct
auctions for which (1) she does not know the full distribution of valuations, (2) no two bidders need to
be drawn from identical distributions and (3) the revenue obtained is a constant fraction of the revenue
in Myerson's optimal auction.
In addition to being competitive with traditional benchmarks, our digital parametric auction is optimal in a new sense, which we call maximin optimality. Informally, an auction is maximin optimal if it
maximizes revenue in the worst case over an adversary's choice of the distribution. We show that our
digital parametric is maximin optimality among the class of posted price mechanisms.
Our techniques include using Chebyshevtype inequalities to give bounds on the optimal reserve prices.
These techniques have not been used before in auction theory, and might be of independent interest.
A GameTheoretic Model Motivated by the DARPA Network Challenge
(pdf)
by Rajesh Chitnis, MohammadTaghi Hajiaghayi, Jonathan Katz, Koyel Mukherjee.
In this paper we propose a gametheoretic model to analyze events similar to the 2009 \emph{DARPA Network
Challenge}~\cite{darpawebsite}, which was organized by the Defense Advanced Research Projects Agency (DARPA) for exploring
the roles that the Internet and social networks play in incentivizing widearea collaborations. The challenge was to form a
group that would be the first to find the locations of ten moored weather balloons across the United States. We consider a
model in which $N$ people are located in the space with a fixed coverage volume around each person's geographical location,
and these people can join together to form groups. A balloon is placed in the space and a group wins if it is the first one to
report the location of the balloon. A larger team has a higher probability of finding the balloon, but the prize money is
divided equally among the team members and hence there is a competing tension to keep teams as small as possible. We analyze
this model under a natural set of utilities, and under the assumption that the players are \emph{risk averse}. Risk aversion
is the reluctance of a person to accept a bargain with an uncertain payoff rather than another bargain with a more certain,
but possibly lower, expected payoff. We are interested in analyzing the structures of the groups in Nash equilibria for our
model. We show if the game is played in the onedimensional space (line), or more generally in the $d$dimensional Euclidean
space for any $d\geq 1$, then in any Nash equilibrium there always exists a group covering a constant fraction of the total
volume. In the discrete version, the players are located at the vertices of a graph and each vertex can cover itself and all
its neighbors. For the class of boundeddegree regular graphs, we show in any Nash equilibrium there always exists a group
covering a constant fraction of the total number of vertices. Our techniques do not generalize to all graphs: we give explicit
examples of graphs where our techniques fail. We believe for general graphs there exists a Nash equilibrium such that no group
covers a constant fraction of the total number of vertices, and show this under the assumption that defecting to an empty
group is not allowed.
Mechanisms for Risk Averse Agents, Without Loss
(pdf)
by Shaddin Dughmi and Yuval Peres.
A Robustness Analysis of a Capacity Exchange Mechanism in
Multicommodity Networks under Demand Uncertainty
by Luyi Gui and Ozlem Ergun.
We study the coordination of a decentralized multicommodity network system where the edge capacity is
individually owned but can be accessed by all participants for their own routing operations. In particular,
we consider designing a capacity exchange mechanism under which capacity is traded according to predetermined
unit prices. The goal is to maximize the social efficiency, measured by the total routing revenue,
of the flow composed by individual players selfish routing of their own commodities motivated by the mechanism.
A practical challenge to do this arises from uncertainties in demand, as in many cases the mechanism
is designed before the demand is revealed. Hence, it is desirable that the capacity exchange mechanism is
robust, i.e., it can effectively coordinate the network under all potential demand scenarios using a fixed set
of exchange prices. This task becomes more challenging as in practice, there often exists a certain level of
information asymmetry between the mechanism designer and the players about demand.
In this paper, we perform the following two studies on the robustness of the capacity exchange mechanism
under demand uncertainty. First, we characterize how network structure affects the robustness of the
mechanism. Second, we investigate the computational side of designing a robust capacity exchange mechanism
in any given network. In particular, we propose a general pricing algorithm and quantify the routing
performance under the resulting prices by providing bounds to the expected total revenue and the degree of
potential capacity violation in the network.
The concavity of atomic splittable congestion games with nonlinear
utility functions
by Darrell Hoy.
Classical work in network congestion games assumes networks are deterministic and agents are riskneutral.
In many settings, this is unrealistic and players have more complicated preferences. When driving to work
in the morning, a commuter may prefer a safer route, rather than the faster but riskier route. A website
sending out streaming video packets may not care about packets once they are late or derive much benet
from packets arriving much earlier, but would rather prefer a more consistent delivery model.
We consider the atomicsplittable setting and model these preferences in two ways: when players have
nonlinear preferences over (i) the delay on every path, and (ii) on the total delay they experience over all
paths. We ask  when are these games concave?
In the riskneutral setting, the concavity of the setting underlies many results, including the existence
of pure Nash equilibria. In setting (ii), when players have preferences over the total cost seen, the game
is concave and pure Nash equilibria will always exist. In setting (i) however, we show that the game is no
longer concave, and as a result we no longer know if pure Nash equilibria always exist. In both of these
settings, we show that we can reduce questions about them in the stochastic setting to questions about
them in the deterministic setting.
Inventorybased versus Priorbased Options Trading Agents
by Abraham Othman and Tuomas Sandholm.
Options are a basic, widelytraded form of financial derivative that
offer payouts based on the future price of an underlying asset. The
finance literature gives us optiontrading algorithms that take into
consideration information about how prices move over time but do not
explicitly involve the trades the agent made in the past. In contrast,
the prediction market literature gives us automated marketmaking
agents (like the popular LMSR) that are eventindependent and price
trades based only on the inventories the agent holds. We simulate
the performance of five trading agents inspired by these literatures
on a large database of recent historical option prices. We find that
a combination of the two approaches produced the best results in
our experiments: a trading agent that keeps track of previouslymade
trades combined with a good prior distribution on how prices move
over time. The experimental success of this synthesized trader has
implications for agent design in both financial and prediction markets.
Call for papers
The conference is soliciting full papers on the
topics outlined above. Submitted papers will be evaluated on
significance, originality, technical quality, and exposition. The
workshop will not have an archival proceedings and will consider
papers simultaneously submitted for publication elsewhere subject to
their expected publication being after June 8th, 2011 (the last day of
the Conference on Electronic Commerce). To receive full consideration
papers should be submitted
to risk.workshop.2012@gmail.com
by April 10. Notification of accepted papers will be on April 30.
Organizers: Amos Fiat (Tel Aviv University), Evdokia Nikolova
(Texas A&M University), Nicolas StierMoses (Columbia University, Universidad di Tella)
Program Committee: Saeed Alaei (University of MarylandCollege Park), Amos Fiat (Tel Aviv University), Evdokia Nikolova (Texas A&M University), Georgios Piliouras (Georgia Institute of Technology), Nicolas StierMoses (Columbia University, Universidad di Tella), Mukund Sundararajan (Google), Chaitanya Swamy (University of Waterloo).