Contributions published at Computation and Economics (Sven Seuken)

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

null

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.

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.

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.

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.

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.

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.