Workshop on Risk Aversion in Algorithmic Game Theory and Mechanism Design
June 7, 2012, Valencia, Spain. (in conjunction with ACM-EC 2012)
|
[Synopsis]
[Dates]
[Schedule]
[Plenary talk]
[Abstracts]
[CFP]
[Organization]
Synopsis
The Von-Neumann Morgenstern expected utility theory addresses risk aversion
by concave utility functions for wealth. Non-expected 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 mean-variance 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 non-EUT 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.
Dates
| Submission Deadline | Tuesday, April 10th |
| Acceptance Notification | Monday, April 30th |
| Workshop | Thursday, June 7th |
Schedule
| 9:00-9:50 | Contributed Session. Various topics. |
| Othman, Sandholm: Inventory-based versus Prior-based Options Trading Agents
|
| Chitnis, Hajiaghayi, Katz, Mukherjee: A Game-Theoretic Model Motivated by the DARPA Network Challenge
|
| Coffee break |
|
| 10:30-11:40 | Plenary talk: Garud Iyengar: Optimizing with Risk Measures |
|
| 11:40-12:30 | Contributed Session. Network Routing. |
| Hoy: The concavity of atomic splittable congestion games with non-linear utility functions
|
| Gui, Ergun: A Robustness Analysis of a Capacity Exchange Mechanism in Multicommodity Networks under Demand Uncertainty
|
|
| Lunch break |
|
| 2:00-3: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 multi-parameter 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 single-parameter multi-unit auctions.
We first consider the problem of designing optimal DSIC (dominant strategy incentive compatible) mechanism for a risk averse seller in
the case of multi-unit auctions, and we give a poly-time computable deterministic sequential posted pricing mechanism (SPM) that for any $\eps > 0$, yields a $(1-1/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 multi-parameter 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 truthful-in-expectation 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 poly-time algorithm to construct a truthful-in-expectation 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 pro ts. 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 Chebyshev-type 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 Game-Theoretic Model Motivated by the DARPA Network Challenge
(pdf)
by Rajesh Chitnis, MohammadTaghi Hajiaghayi, Jonathan Katz, Koyel Mukherjee.
In this paper we propose a game-theoretic model to analyze events similar to the 2009 \emph{DARPA Network
Challenge}~\cite{darpa-website}, which was organized by the Defense Advanced Research Projects Agency (DARPA) for exploring
the roles that the Internet and social networks play in incentivizing wide-area 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 one-dimensional 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 bounded-degree 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 non-linear
utility functions
by Darrell Hoy.
Classical work in network congestion games assumes networks are deterministic and agents are risk-neutral.
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 bene t
from packets arriving much earlier, but would rather prefer a more consistent delivery model.
We consider the atomic-splittable setting and model these preferences in two ways: when players have
non-linear 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 risk-neutral 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.
Inventory-based versus Prior-based Options Trading Agents
by Abraham Othman and Tuomas Sandholm.
Options are a basic, widely-traded form of financial derivative that
offer payouts based on the future price of an underlying asset. The
finance literature gives us option-trading 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 market-making
agents (like the popular LMSR) that are event-independent 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 previously-made
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.
Organization
Organizers: Amos Fiat (Tel Aviv University), Evdokia Nikolova
(Texas A&M University), Nicolas Stier-Moses (Columbia University, Universidad di Tella)
Program Committee: Saeed Alaei (University of Maryland-College Park), Amos Fiat (Tel Aviv University), Evdokia Nikolova (Texas A&M University), Georgios Piliouras (Georgia Institute of Technology), Nicolas Stier-Moses (Columbia University, Universidad di Tella), Mukund Sundararajan (Google), Chaitanya Swamy (University of Waterloo).