Sven Seuken, David C. Parkes, Eric Horvitz, Kamal Jain, Mary Czerwinski, Desney Tan, Market User Interface Design, In: Harvard University, No. 1, 2011. (Working Paper)
Despite the pervasiveness of electronic markets in our lives, only little is known about the role
of user interfaces (UIs) in promoting good performance in market domains. How does the way
we display market information to end-users, and the set of choices we offer, influence economic
efficiency? In this paper, we introduce a new research agenda on “market user interface design.”
We take the domain of 3G bandwidth allocation as an illustrative example, and consider the design
space of UIs in terms of varying the number of choices offered, fixed vs. changing market prices,
and situation-dependent choice sets. The UI design induces a Markov decision process, the solution
to which provides a gold standard against which user behavior is studied. We provide a systematic,
empirical study of the effect of different UI levers on user behavior and market performance, along
with considerations of behavioral factors including loss aversion, incomplete search, and position
effects. Finally, we fit a quantal-best response model to users’ actions and evaluate an optimized
market user interface. |
|
Sven Seuken, Michel Meulpolder, Dick H. J. Epema, David C. Parkes, Johan A. Pouwelse, Jie Tang, Work Accounting Mechanisms: Theory and Practice, In: Harvard University, No. 1, 2011. (Working Paper)
The Internet has enabled a new paradigm of economic production, where individual users per-
form work for others, often in small units, for short periods of time, and without formal contracts
or monetary payments. These distributed work systems can arise in many places, for example in
peer-to-peer (P2P) ¯le-sharing networks, in ad-hoc wireless routing networks, or in 3G content
distribution systems. The particular challenge is to incentivize users to perform work for others,
even though all interactions are bilateral and monitoring is not possible. In this paper, we formal-
ize the problem of designing incentive-compatible work accounting mechanisms that measure the
net contributions of users, despite relying on voluntary reports. We describe a fully distributed
accounting mechanism called BarterCast and introduce the Drop-Edge extension which re-
moves any incentive for a user to make misreports about its own interactions. We prove that the
information loss necessary to achieve this incentive compatibility is small and vanishes in the limit
as the number of users grows. In some domains, users may be able to cheaply create fake identities
(i.e, sybils) and use those to manipulate the accounting mechanism. A striking negative result is
that no sybil-proof accounting mechanism exists if one requires responsiveness to a single positive
report. To evaluate the welfare properties of BarterCast+DropEdge, we ¯rst present results
from a discrete, round-based simulation, showing that the mechanism achieves very high e±ciency.
We have also implemented the mechanism in Tribler, a BitTorrent software client, that is al-
ready deployed in the real world and has thousands of users. Experimental results using Tribler
demonstrate that the mechanism successfully prevents free-riding in P2P-¯le-sharing systems, and
achieves better e±ciency than the standard BitTorrent protocol. |
|
Mike Ruberry, Sven Seuken, Sharing in BitTorrent can be Rational, In: Harvard University, No. 1, 2011. (Working Paper)
The widely used BitTorrent protocol is regularly extended
to produce new protocols with empirically preferable characteristics, like
shorter le acquisition times and fewer upload bandwidth usage. How-
ever, these advances have outpaced theoretical understanding, necessary
for formally analyzing the eciency and rationality of existing protocols,
and the design of new ones. We address this discrepancy by presenting a
new model, a stochastic \goal oriented" game, that captures BitTorrent's
salient features more accurately. In particular, players only obtain a posi-
tive payo when all pieces of a le are acquired. Our model leads to equi-
librium results that are distinct from prior work. We show that without
altruists, it is irrational for peers to share with each other using BitTor-
rent, while with altruists, a sharing equilibrium exists. Furthermore, we
present the design of an expanded protocol using \cheap pseudonyms",
such that sharing becomes an equilibrium even without the presence of
altruists. The usefulness of cheap pseudonyms in this setting is surprising
as it contrasts with prior research showing that cheap pseudonyms are a
negative externality. |
|
Sven Seuken, Kamal Jain, David C. Parkes, Hidden Market Design, In: Proceedings of the Conference on Artificial Intelligence (AAAI), Atlanta, GA, 2010. (Conference or Workshop Paper published in Proceedings)
The next decade will see an abundance of new intelligent
systems, many of which will be market-based.
Soon, users will interact with many new markets, perhaps
without even knowing it: when driving their car,
when listening to a song, when backing up their files,
or when surfing the web. We argue that these new systems
can only be successful if a new approach is chosen
towards designing them. In this paper we introduce
the general problem of “Hidden Market Design.” The
design of a “weakly hidden” market involves reducing
some of the market complexities and providing a user
interface (UI) that makes the interaction seamless for
the user. A “strongly hidden market” is one where some
semantic aspect of a market is hidden altogether (e.g.,
budgets, prices, combinatorial constraints). We show
that the intersection of UI design and market design is
of particular importance for this research agenda. To
illustrate hidden market design, we give a series of potential
applications. We hope that the problem of hidden
market design will inspire other researchers and lead to
new research in this direction, paving the way for more
successful market-based systems in the future. |
|
Sven Seuken, Denis Charles, Max Chickering, Sidd Puri, Market Design and Analysis for a P2P Backup System, In: Proceedings of the ACM Conference on Electronic Commerence (EC), Cambridge, MA, 2010. (Conference or Workshop Paper published in Proceedings)
In this paper we take the problem of a market-based P2P
backup application and carry it through market design, to
implementation, to theoretical and experimental analysis.
While the long-term goal is an open market using real money,
here we consider a system where monetary transfers are pro-
hibited. We ¯rst describe the design of the P2P resource ex-
change market and the UI we developed. Second, we prove
theorems on equilibrium existence and uniqueness. Third,
we prove a surprising impossibility result regarding the lim-
ited controllability of the equilibrium and show how to ad-
dress this. Fourth, we present a price update algorithm that
uses daily supply and demand information to move prices
towards the equilibrium and we provide a theoretical and
experimental convergence analysis. The market design de-
scribed in this paper is already implemented as part of a
Microsoft research project on P2P backup systems and an
alpha version of the software has been successfully tested. |
|
Jie Tang, Sven Seuken, David C. Parkes, Hybrid Transitive Trust Mechanisms, In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Toronto, Canada, 2010. (Conference or Workshop Paper published in Proceedings)
Establishing trust amongst agents is of central importance to the development
of well-functioning multi-agent systems. For example,
the anonymity of transactions on the Internet can lead to inefficiencies;
e.g., a seller on eBay failing to ship a good as promised, or
a user free-riding on a file-sharing network. Trust (or reputation)
mechanisms can help by aggregating and sharing trust information
between agents. Unfortunately these mechanisms can often be manipulated
by strategic agents. Existing mechanisms are either very
robust to manipulation (i.e., manipulations are not beneficial for
strategic agents), or they are very informative (i.e., good at aggregating
trust data), but never both. This paper explores this trade-off
between these competing desiderata. First, we introduce a metric to
evaluate the informativeness of existing trust mechanisms. We then
show analytically that trust mechanisms can be combined to generate
new hybrid mechanisms with intermediate robustness properties.
We establish through simulation that hybrid mechanisms can
achieve higher overall efficiency in environments with risky transactions
and mixtures of agent types (some cooperative, some malicious,
and some strategic) than any previously known mechanism. |
|
Sven Seuken, Kamal Jain, Desney Tan, Mary Czerwinski, Hidden Markets: UI Design for a P2P Backup Application, In: Proceedings of the Conference on Human Factors in Computing Systems (CHI), Atlanta, GA, 2010. (Conference or Workshop Paper published in Proceedings)
The Internet has allowed market-based systems to become
increasingly pervasive. In this paper we explore the role of
user interface (UI) design for these markets. Different UIs
induce different mental models which in turn determine how
users understand and interact with a market. Thus, the intersection
of UI design and economics is a novel and important
research area. We make three contributions at this intersection.
First, we present a novel design paradigm which
we call hidden markets. The primary goal of hidden markets
is to hide as much of the market complexities as possible.
Second, we explore this new design paradigm using one
particular example: a P2P backup application. We explain
the market underlying this system and provide a detailed description
of the new UI we developed. Third, we present results
from a formative usability study. Our findings indicate
that a number of users could benefit from a market-based
P2P backup system. Most users intuitively understood the
give & take principle as well as the bundle constraints of
the market. However, the pricing aspect was difficult to discover/
understand for many users and thus needs further investigation.
Overall, the results are encouraging and show
promise for the hidden market paradigm. |
|
Sven Seuken, Jie Tang, David C. Parkes, Accounting Mechanisms for Distributed Work Systems, In: Proceedings of the Conference on Artificial Intelligence (AAAI), Atlanta, GA, 2010. (Conference or Workshop Paper published in Proceedings)
In distributed work systems, individual users perform
work for other users. A significant challenge in these
systems is to provide proper incentives for users to
contribute as much work as they consume, even when
monitoring is not possible. We formalize the problem
of designing incentive-compatible accounting mechanisms
that measure the net contributions of users, despite
relying on voluntary reports. We introduce the
Drop-Edge Mechanism that removes any incentive for
a user to manipulate via misreports about work contributed
or consumed. We prove that Drop-Edge provides
a good approximation to a user’s net contribution,
and is accurate in the limit as the number of users grows.
We demonstrate very good welfare properties in simulation
compared to an existing, manipulable mechanism.
In closing, we discuss our ongoing work, including a
real-world implementation and evaluation of the Drop-
Edge Mechanism in a BitTorrent client. |
|
Sven Seuken, Denis Charles, Max Chickering, Mary Czerwinski, Kamal Jain, David C. Parkes, Sidd Puri, Desney Tan, Design and Analysis of a Hidden Peer-to-peer Backup Market, In: Harvard University, No. 1, 2010. (Working Paper)
We present a new market design for a peer-to-peer (p2p) backup application and provide a
theoretical and experimental analysis. In domains such as p2p backup, where many non-expert
users find markets unnatural or unexpected, it is often a pragmatic requisite to remove or hide the
market’s complexities. To this end, we introduce a new design paradigm which we call “hidden
market design,” and show, how a market and its user interface (UI) can be designed to hide
the underlying complexities, while maintaining the market’s functionality. We enable the p2p
backup market using a virtual currency only, and we develop a novel market UI that makes the
interaction for the users as seamless as possible. The UI hides or simplifies many aspects of the
market, including combinatorial resource constraints, prices, account balances and payments. In
a real p2p backup system, we can expect users to update their settings with a delay upon price
changes. Therefore, the market is designed to work well even out of equilibrium, by maximizing
the buffer between demand and supply. The main theoretical result is an existence and uniqueness
theorem, which also holds if a certain percentage of the user population is price-insensitive or even
adversarial. However, we also show that the more freedom we give the users, the less robust the
system becomes against adversarial attacks. Furthermore, the buffer size has limited controllability
via price changes alone and we show how to address this. We introduce a price update algorithm
that uses daily aggregate supply and demand data to move prices towards the equilibrium, and
we prove that the algorithm converges quickly towards the equilibrium. Finally, we present results
from a formative usability study of the market UI, where we found encouraging results regarding
the hidden markets paradigm. The market design presented here is implemented as part of a
Microsoft research project and an alpha version of the software has been successfully tested. |
|
Sven Seuken, Denis Charles, Max Chickering, Sidd Puri, Designing User Interfaces for Hidden Markets, In: Proceedings of the IJCAI Workshop on Intelligence and Interaction, Pasadena, CA, 2009. (Conference or Workshop Paper published in Proceedings)
Market-based intelligent systems are becoming increasingly
important in our everyday lives. However,
when the goal of these systems is not the sale
or purchase of items, traditional interfaces allowing
users to specify bid or ask prices are no longer appropriate.
Thus, there is a need for different kinds
of user interfaces to interact with these “hidden
markets”. In this paper, we present a novel user
interface for one particular market-based system: a
P2P backup application. The primary goal of the
UI is to hide the market from the user as much as
possible. Thus, the two main design challenges are
how to provide current market information to the
user without using prices or account balances, and
how to elicit the user’s preferences with as little interaction
as possible. The UI described in this paper
is already implemented as part of a Microsoft research
project on P2P backup systems and an internal
alpha version of the software has been released.
We are currently designing a usability study to evaluate
the UI empirically. |
|
Sven Seuken, Denis Charles, Max Chickering, Sidd Puri, Market Design and Analysis for a P2P Backup System [2], In: Proceedings of the Workshop on the Economics of Networks, Systems, and Computation (NetEcon), Stanford, CA, 2009. (Conference or Workshop Paper published in Proceedings)
This paper presents the design and theoretical analysis of a
P2P resource exchange market, a novel application of mar-
kets to the domain of P2P backup. While the long-term
goal is an open market using real money, here we consider
a system where monetary transfers are prohibited. We ¯rst
describe the design of the market and the user interface we
developed. Second, we prove theorems on equilibrium ex-
istence and uniqueness. Third, we present a price update
algorithm that uses daily supply and demand information
to move prices towards the equilibrium. The market design
described in this paper is already implemented as part of a
Microsoft research project on P2P backup systems and an
internal alpha version of the software has been released. We
will thus complement the theoretical analysis with discus-
sions of implementation challenges that arise in practice. |
|
Sven Seuken, Denis Charles, Max Chickering, Sidd Puri, Market Design for a P2P Backup System, In: 1st Conference on Auctions, Market Mechanisms and Applications (AMMA), Boston, MA, 2009. (Conference or Workshop Paper published in Proceedings)
|
|
Mark Klein, Gabriel Moreno, David C. Parkes, Daniel Plakosh, Sven Seuken, Kurt Wallnau, Handling Interdependent Values in an Auction Mechanism for Enhanced Bandwidth Allocation in Tactical Data Networks, In: Proceedings of the Workshop on the Economics of Networks, Systems, and Computation (NetEcon), Seattle, WA, 2008. (Conference or Workshop Paper published in Proceedings)
We consider a tactical data network with limited bandwidth,
in which each agent is tracking objects and may have value
for receiving data from other agents. The agents are self-
interested and would prefer to receive data than share data.
Each agent has private information about the quality of its
data and can misreport this quality and degrade or other-
wise decline to share its data. The problem is one of inter-
dependent value mechanism design because the value to one
agent for the broadcast of data on an object depends on the
quality of the data, which is privately known to the sender.
A recent two-stage mechanism due to Mezzetti (2004) can
be modified to our setting. Our mechanism achieves effi-
cient bandwidth allocation and provides incentive compat-
ibility by conditioning payments on the realized value for
data shared between agents. |
|
Sven Seuken, Ruggiero Cavallo, David C. Parkes, Partially-Synchronized DEC-MDPs in Dynamic Mechanism Design, In: Proceedings of the 23rd Conference on Artificial Intelligence (AAAI), Chicago, IL, 2008. (Conference or Workshop Paper published in Proceedings)
In this paper, we combine for the first time the methods of dynamic
mechanism design with techniques from decentralized
decision making under uncertainty. Consider a multi-agent
system with self-interested agents acting in an uncertain environment,
each with private actions, states and rewards. There
is also a social planner with its own actions, rewards, and
states, acting as a coordinator and able to influence the agents
via actions (e.g., resource allocations). Agents can only communicate
with the center, but may become inaccessible, e.g.,
when their communication device fails. When accessible to
the center, agents can report their local state (and models) and
receive recommendations from the center about local policies
to follow for the present period and also, should they
become inaccessible, until becoming accessible again. Without
self-interest, this poses a new problem class which we
call partially-synchronized DEC-MDPs, and for which we
establish some positive complexity results under reasonable
assumptions. Allowing for self-interested agents, we are able
to bridge to methods of dynamic mechanism design, aligning
incentives so that agents truthfully report local state when
accessible and choose to follow the prescribed “emergency
policies” of the center. |
|
Sven Seuken, Shlomo Zilberstein, Formal Models and Algorithms for Decentralized Decision Making Under Uncertainty, Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS), Vol. 17 (2), 2008. (Journal Article)
Over the last 5 years, the AI community has shown considerable interest in
decentralized control of multiple decision makers or “agents” under uncertainty. This problem
arises in many application domains, such as multi-robot coordination, manufacturing,
information gathering, and load balancing. Such problems must be treated as decentralized
decision problems because each agent may have different partial information about the other
agents and about the state of theworld. It has been shown that these problems are significantly
harder than their centralized counterparts, requiring new formal models and algorithms to be
developed. Rapid progress in recent years has produced a number of different frameworks,
complexity results, and planning algorithms. The objectives of this paper are to provide a
comprehensive overview of these results, to compare and contrast the existing frameworks,
and to provide a deeper understanding of their relationships with one another, their strengths,
and their weaknesses. While we focus on cooperative systems, we do point out important
connections with game-theoretic approaches. We analyze five different formal frameworks,
three different optimal algorithms, as well as a series of approximation techniques. The paper
provides interesting insights into the structure of decentralized problems, the expressiveness
of the various models, and the relative advantages and limitations of the different solution
techniques. A better understanding of these issues will facilitate further progress in the field
and help resolve several open problems that we identify. |
|
Sven Seuken, Shlomo Zilberstein, Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs, In: Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence (UAI), Vancouver, Canada, 2007. (Conference or Workshop Paper published in Proceedings)
Memory-Bounded Dynamic Programming
(MBDP) has proved extremely effective in
solving decentralized POMDPs with large
horizons. We generalize the algorithm and
improve its scalability by reducing the complexity
with respect to the number of observations
from exponential to polynomial. We
derive error bounds on solution quality with
respect to this new approximation and analyze
the convergence behavior. To evaluate
the effectiveness of the improvements, we introduce
a new, larger benchmark problem.
Experimental results show that despite the
high complexity of decentralized POMDPs,
scalable solution techniques such as MBDP
perform surprisingly well. |
|
Sven Seuken, Shlomo Zilberstein, Memory-Bounded Dynamic Programming for DEC-POMDPs, In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, 2007. (Conference or Workshop Paper published in Proceedings)
Decentralized decision making under uncertainty
has been shown to be intractable when each agent
has different partial information about the domain.
Thus, improving the applicability and scalability
of planning algorithms is an important challenge.
We present the first memory-bounded dynamic programming
algorithm for finite-horizon decentralized
POMDPs. A set of heuristics is used to identify
relevant points of the infinitely large belief
space. Using these belief points, the algorithm
successively selects the best joint policies for each
horizon. The algorithm is extremely efficient, having
linear time and space complexity with respect
to the horizon length. Experimental results show
that it can handle horizons that are multiple orders
of magnitude larger than what was previously possible,
while achieving the same or better solution
quality. These results significantly increase the applicability
of decentralized decision-making techniques. |
|
Günter Müller, Torsten Eymann, Norbert Nopper, Sven Seuken, EMIKA System: Architecture and Prototypic Realization, In: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (SMC), The Hague, The Netherlands, 2004. (Conference or Workshop Paper published in Proceedings)
Life critical applications in hospital
environments have got special requirements concerning
IT support: a real-time cooperation is necessary to ensure
a continuous workflow. This article describes the
prototypic realization of the EMIKA project, a real-time
controlled mobile information system for clinical
applications. The EMIKA architecture is comprised of
three layers: first of all, the Communication Layer
provides wireless device interaction. Secondly, the
Middleware Layer establishes a common service platform
for automated service provision and access. Finally, the
Application Layer implements a multi-agent-system for
the real-time coordination needed for a self-organizing
patient logistics environment. |
|