445 research outputs found
Hyperproperty-Preserving Register Specifications
No full textReasoning about hyperproperties of concurrent implementations, such as the guarantees these implementations provide to randomized client programs, has been a long-standing challenge. Standard linearizability enables the use of atomic specifications for reasoning about standard properties, but not about hyperproperties. A stronger correctness criterion, called strong linearizability, enables such reasoning, but is rarely achievable, leaving various useful implementations with no means for reasoning about their hyperproperties. In this paper, we focus on registers and devise non-atomic specifications that capture a wide-range of well-studied register implementations and enable reasoning about their hyperproperties. First, we consider the class of write strong-linearizable implementations, a recently proposed useful weakening of strong linearizability, which allows more implementations, such as the well-studied single-writer ABD distributed implementation. We introduce a simple shared-memory register specification that can be used for reasoning about hyperproperties of programs that use write strongly-linearizable implementations. Second, we introduce a new linearizability class, which we call decisive linearizability, that is weaker than write strong-linearizability and includes multi-writer ABD, and develop a second shared-memory register specification for reasoning about hyperproperties of programs that use register implementations of this class. These results shed light on the hyperproperties guaranteed when simulating shared memory in a crash-resilient message-passing system
Spiteful Bidding in Sealed-Bid Auctions
No full textWe study the bidding behavior of spiteful agents who, contrary to the common assumption of self-interest, maximize the weighted difference of their own profit and their competitors ’ profit. This assumption is motivated by inherent spitefulness, or, for example, by competitive scenarios such as in closed markets where the loss of a competitor will likely result in future gains for oneself. We derive symmetric Bayes Nash equilibria for spiteful agents in 1 st-price and 2 nd-price sealed-bid auctions. In 1 st-price auctions, bidders become “more truthful ” the more spiteful they are. Surprisingly, the equilibrium strategy in 2 nd-price auctions does not depend on the number of bidders. Based on these equilibria, we compare revenue in both auction types. It turns out that expected revenue in 2 nd-price auctions is higher than expected revenue in 1 st-price auctions whenever agents have the slightest interest in reducing others’ profit as long as they still care for their own profit. In other words, revenue equivalence only holds for auctions in which all agents are either self-interested or completely malicious
Adaptive Load Balancing: A Study in Multi-Agent Learning
No full textWe study the process of multi-agent reinforcement learning in the context of load balancing in a distributed system, without use of either central coordination or explicit communication. We first define a precise framework in which to study adaptive load balancing, important features of which are its stochastic nature and the purely local information available to individual agents. Given this framework, we show illuminating results on the interplay between basic adaptive behavior parameters and their effect on system efficiency. We then investigate the properties of adaptive load balancing in heterogeneous populations, and address the issue of exploration vs. exploitation in that context. Finally, we show that naive use of communication may not improve, and might even harm system efficiency. 1. Introduction This article investigates multi-agent reinforcement learning in the context of a concrete problem of undisputed importance -- load balancing. Real life provides us with many exampl..
Deriving Properties of Belief Update from Theories of Action (II)
No full textIn [ del Val and Shoham, 1992 ] we showed that the postulates for belief update recently proposed by Katsuno and Mendelzon [ 1991 ] can be analytically derived using the formal theory of action proposed by Lin and Shoham [ 1991 ] . The contribution of this paper is twofold: ffl Whereas in [ del Val and Shoham, 1992 ] we only showed that our encoding of the update problem satisfied the KM postulates, here we use an independently motivated generalization of the theory of action used in that paper to provide a one-to-one correspondence between our construction and KM update semantics. ffl We show how the KM semantics can be generalized by relaxing our construction in a number of ways, each justified in certain intuitive circumstances and each corresponding to one specific postulate. It follows that there are reasonable update operators outside the KM family. 1 Introduction Katsuno and Mendelzon [ 1991 ] have recently proposed a characterization of belief update in terms of a set of po..
Combinatorial Auctions
No full textA comprehensive book on combinatorial auctions?auctions in which bidders can bid on packages of items. The book consists of original material intended for researchers, students, and practitioners of auction design. It includes a foreword by Vernon Smith, an introduction to combinatorial auctions, and twenty-three cross-referenced chapters in five parts. Part I covers mechanisms, such as the Vickrey auction and the ascending proxy auction. Part II is on bidding and efficiency issues. Part III examines computational issues and algorithmic considerations, especially the winner determination problem?how to identify the (tentative) winning set of bids that maximizes revenue. Part IV discusses implementation and methods of testing the performance of combinatorial auctions, including simulation and experiment. Part V considers four important applications: airport runway access, trucking, bus routes, and industrial procurement. The chapters develop and apply a unified language, integrating ideas from economics, operations research, and computer science. A glossary defines the central terms. The contributors are Lawrence Ausubel, Michael Ball, Martin Bichler, Sushil Bikhchandani, Craig Boutilier, Estelle Cantillon, Chris Caplice, Peter Cramton, Andrew Davenport, George Donohue, Karla Hoffman, Gail Hohner, Jayant Kalagnanam, Ailsa Land, Daniel Lehmann, Kevin Leyton-Brown, Dinesh Menon, Paul Milgrom, Rudolf Müller, Noam Nisan, Eugene Nudelman, Joseph Ostroy, David Parkes, Aleksandar Pekec, Martin Pesendorfer, Susan Powell, Amir Ronen, Michael Rothkopf, Tuomas Sandholm, Ilya Segal, Yossi Sheffi, Yoav Shoham, Richard Steinberg, Susara van den Heever, Thomas Wilson, and Makoto Yokoo.Auctions, Combinatorial Auctions, Market Design
Epistemic semantics for fixed-point non-monotonic logics
No full textDefault Logic and Autoepistemic Logic are the two best-known fixed-points non-monotonic logics. Despite the fact that they are known to be closely related and that the epistemic nature of Autoepistemic Logic is obvious, the only semantics that have been offered for Default Logic to date are complex and have little to do with epistemic notions [Etherington 1987]. In this paper we provide simple uniform epistemic semantics for the two logics. We do so by translating them both into a new logic, called GK, of Grounded Knowledge, which embodies a modification of preference semantics [Shoham 1987]. Beside their simplicity and uniformity, the semantics have two other advantages: They allow easy proofs of the connections be-tween Default Logic and Autoepistemic Logic, and suggest a general class of logics of which the two logics are special cases.
Improving the quality of the personalized electronic program guide
No full textAs Digital TV subscribers are offered more and more channels, it is becoming increasingly difficult for them to locate the right programme information at the right time. The personalized Electronic Programme Guide (pEPG) is one solution to this problem; it leverages artificial intelligence and user profiling techniques to learn about the viewing preferences of individual users in order to compile personalized viewing guides that fit their individual preferences. Very often the limited availability of profiling information is a key limiting factor in such personalized recommender systems. For example, it is well known that collaborative filtering approaches suffer significantly from the sparsity problem, which exists because the expected item-overlap between profiles is usually very low. In this article we address the sparsity problem in the Digital TV domain. We propose the use of data mining techniques as a way of supplementing meagre ratings-based profile knowledge with additional item-similarity knowledge that can be automatically discovered by mining user profiles. We argue that this new similarity knowledge can significantly enhance the performance of a recommender system in even the sparsest of profile spaces. Moreover, we provide an extensive evaluation of our approach using two large-scale, state-of-the-art online systems—PTVPlus, a personalized TV listings portal and Físchlár, an online digital video library system
- …
