Kolmogorov's setting for probability theory is given an original generalization to account for probabilities arising from Quantum Mechanics. The sample space has a central role in this presentation and random variables, i.e., observables, are defined in a natural way. The mystery presented by the algebraic equations satisfied by (non-commuting) observables that cannot be observed in the same states is elucidated.

When a physicist performs a quantic measurement, new information about the system at hand is gathered. This article studies the logical properties of how this new information is combined with previous information. It presents Quantum Logic as a propositional logic under two connectives: negation and the and then operation that combines old and new information. The and then connective is neither commutative nor associative. Many properties of this logic are exhibited, and some small elegant subset is shown to imply all the properties considered. No independence or completeness result is claimed. Classical physical systems are exactly characterized by the commutativity, the associativity, or the monotonicity of the and then connective. Entailment is defined in this logic and can be proved to be a partial order. In orthomodular lattices, the operation proposed by Finch in [3] satisfies all the properties studied in this article. All properties satisfied by Finch's; operation in modular lattices are valid in Quantum Logic. It is not known whether all properties of Quantum Logic are satisfied by Finch's; operation in modular lattices. Non-commutative, non-associative algebraic structures generalizing Boolean algebras are defined, ideals are characterized and a homomorphism theorem is proved.

In almost every procurement situation, non-price attributes of the items to be purchased play a crucial role. Procurement protocols which take these attributes into account are called multi-attribute auctions.We study the following problem called optimal multi-attribute auction design: A buyer wants to procure an item which can be supplied in many possible configurations. The buyer has a value v(x) for each possible configuration x. Every seller i has a privately known cost ci(x) of supplying each possible configuration. Given a probability distribution on the cost functions, our goal is to design an auction which maximizes the expected utility of the buyer.This paper offers a generic method for the construction of nearly optimal multi-attribute auctions. The computational time of our mechanisms equals the time required for computing (or approximating) the optimal mechanism on a small number of agents. Our method can be successfully applied to many variants of multi-attribute auction design.

We propose two different methods for presenting substitutes (a.k.a. gross-substitutes) valuations. Each provides short descriptions for a family of substitutes valuations. We also show that substitutes valuation are closed under k-satiation.

We consider the two-fold problem of representing collective beliefs and aggregating these beliefs. We propose a novel representation for collective beliefs that uses modular, transitive relations over possible worlds. They allow us to represent conflicting opinions and they have a clear semantics, thus improving upon the quasi-transitive relations often used in social choice. We then describe a way to construct the belief state of an agent informed by a set of sources of varying degrees of reliability. This construction circumvents Arrow's Impossibility Theorem in a satisfactory manner by accounting for the explicitly encoded conflicts. We give a simple set-theory-based operator for combining the information of multiple agents. We show that this operator satisfies the desirable invariants of idempotence, commutativity, and associativity, and, thus, is well-behaved when iterated, and we describe a computationally effective way of computing the resulting belief state. Finally, we extend our framework to incorporate voting.

Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms---in particular, their truth revelation properties---assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.

Certain services may be provided in a continuous, one-dimensional, ordered range of different qualities and a customer requiring a service of quality q can only be offered a quality superior or equal to q. Only a discrete set of different qualities will be offered, and a service provider will provide the same service (of fixed quality b) to all customers requesting qualities of service inferior or equal to b. Assuming all services (of quality b) are priced identically, a monopolist will choose the qualities of service and the prices that maximize profit but, under perfect competition, a service provider will choose the (inferior) quality of service that can be priced at the lowest price. Assuming significant economies of scale, two fundamentally different regimes are possible: either a number of different classes of service are offered (DC regime), or a unique class of service offers an unbounded quality of service (UC regime). The DC regime appears in one of two sub-regimes: one, BDC, in which a finite number of classes is offered, the qualities of service offered are bounded and requests for high-quality services are not met, or UDC in which an infinite number of classes of service are offered and every request is met. The types of the demand curve and of the economies of scale, and not the pace of technological change, determine the regime and the class boundaries. The price structure in the DC regime obeys very general laws.

In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. While we show that the allocation problem among valuations with decreasing marginal utilities is NP-hard, we present an efficient greedy 2-approximation algorithm for this case. No such approximation algorithm exists in a setting allowing for complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.

Abstract A vast and interesting family of natural semantics lor belief revision is defined. Suppose one is given a distance d between any two models. One may then define the revision of a theory K by a formula α as the theory defined by the set of all those models of α that are closest, by d. to the set of models of K. This family is characterized by a set of rationality postulates that extends the AGM postulates. The new postulates describe properties of iterated revisions.

Tarski gave a general semantics for deductive reasoning: a formula α may be deduced from a set A of formulas iff α holds in all models in which each of the elements of A holds. A more liberal semantics has been considered: a formula α may be deduced from a set A of formulas iff α holds in all of the preferred models in which all the elements of A hold. Shoham proposed that the notion of preferred models be defined by a partial ordering on the models of the underlying language. A more general semantics is described in this paper, based on a set of natural properties of choice functions. This semantics is here shown to be equivalent to a semantics based on comparing the relative importance of sets of models, by what amounts to a qualitative probability measure. The consequence operations defined by the equivalent semantics are then characterized by a weakening of Tarski's properties in which the monotonicity requirement is replaced by three weaker conditions. Classical propositional connectives are characterized by natural introduction‐elimination rules in a nonmonotonic setting. Even in the nonmonotonic setting, one obtains classical propositional logic, thus showing that monotonicity is not required to justify classical propositional connectives.

Article Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics Share on Authors: Rica Gonen School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, IsraelView Profile , Daniel Lehmann School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, IsraelView Profile Authors Info & Claims EC '00: Proceedings of the 2nd ACM conference on Electronic commerceOctober 2000 Pages 13–20https://doi.org/10.1145/352871.352873Online:17 October 2000Publication History 102citation538DownloadsMetricsTotal Citations102Total Downloads538Last 12 Months18Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem.This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA).Traditional analysis of these mechanisms -in particular, their truth revelation properties -assumes that the optimization problems are solved precisely.In reality, these optimization problems can usually be solved only in an approximate fashion.We investigate the impact on such mechanisms of replacing exact solutions by approximate ones.Specifically, we look at a particular greedy optimization method, which has empirically been shown to perform well.We show that the GVA payment scheme does not provide for a truth revealing mechanism.We introduce another scheme that does guarantee truthfulness for a restricted class of players.We demonstrate the latter property by identifying sufficient conditions for a combinatorial auction to be truth-revealing, conditions which have applicability beyond the specific auction studied here.

We give a semantics to iterated update by a preference relation on possible developments. An iterated update is a sequence of formulas, giving (incomplete) information about successive states of the world. A development is a sequence of models, describing a possible trajectory through time. We assume a principle of inertia and prefer those developments which are compatible with the information and avoid unnecessary changes. The logical properties of the updates defined in this way are considered, and a representation result is proved.

In this paper we study negation rationality, an important property for non-monotonic inference relations. We show that the preferential relations that satisfy negation rationality and admit an injective model are exactly the preferential relations that satisfy the property of disjunctive rationality. We also propose a semantic-type characterization for relations that satisfy negation rationality.

Negotiations are very important in a multiagenl environment, particularly, in an environment where there are conflicts between the agents, and cooperation would be beneficial. We have developed a general structure for a Negotiating Automated Agent that consists of five modules: a Prime Minister, a Ministry of Defense, a Foreign Office, a Headquarters and Intelligence. These modules are implemented using a dynamic set of local agents belonging to the different modules. We used this structure to develop a Diplomacy player. Diplomat. Playing Diplomacy involves a certain amount of technical skills as in other board games, but the capacity to negotiate, explain, convince, promise, keep promises or break them, is an essential ingredient in good play. Diplomat was evaluated and consistently played better than human players.

Abstract We provide a characterization of those nonmonotonic inference operations C for which C(X) may be described as the set of all logical consequences of X together with some set of additional assumptions S(X) that depends anti-monotonically on X (i.e. X ⊆ Y implies S(Y) ⊆ S(X)). The operations represented are exactly characterized in terms of properties most of which have been studied by Freund and Lehmann. Similar characterizations of right-absorbing and cumulative operations are also provided. For cumulative operations, our results fit in closely with those of Freund. We then discuss extending finitary operations to infinitary operations in a canonical way and discuss co-compactness properties. Our results provide a satisfactory notion of pseudo-compactness, generalizing to deductive nonmonotonic operations the notion of compactness for monotonic operations. They also provide an alternative, more elegant and more general, proof of the existence of an infinitary deductive extension for any finitary deductive operation.

The area of automated negotiation has been of particular interest in artificial intelligence due to the important role negotiation plays in facilitating understanding and achieving co-operation among entities with differing interests. These entities may be individuals, organizations, governments, or automated agents. This paper presents methods for solving different aspects of automated negotiation: with whom to negotiate, evaluation of suggestions and the way to offer suggestions. These methods were successfully used to develop the system Diplomat, that may be one of the players in a board game, Diplomacy. This game is characterized by intense negotiation, a very large set of possible strategies and the absence of a trusted intermediary. Although Diplomacy players may break their promises, close co-operation is needed for a success.

Many distributed systems, as well as many real life situations, are best described as involving changes in the partial knowledge that components may have about the real state of the whole system. Examples include synchronization and cooperation protocols, cryptographic systems, games, economics and intelligent programs. In such situations the notion of common knowledge has been recognized as of fundamental importance by Lewis [Le] and Aumann [A]. An event is common knowledge if everybody knows it, everybody knows that everybody knows it, and so on. A method for the formal description of such systems and the rigorous proof of certain of their properties is presented. Its limitations are analyzed. As examples, a well-known puzzle and a logical paradox are treated. A propositional language in which one may describe knowledge, common knowledge and their changes with time is defined. In particular one may describe the knowledge that agents may have of the present state of the world, future states of the world and the knowledge that others may or may not have about the present and future states of the world. The language is interpreted in models a la Kripke, where knowledge is interpreted by a binary relation. An axiomatization is given and shown sound and complete with respect to the models. A doubly-exponential deterministic time decision procedure is described.

Decision procedures are provided for checking the satisfiability of a formula in each of the three systems TCg. TCb and TCf defined in [LS]. The procedures for TCg and TCf run in non-deterministic time 22on where n is the size of the formula and c is a constant. The procedure for TCb runs in non-deterministic time 22on2. A deterministic exponential lower bound is proved for the three systems. All three systems are also shown to be PSPACE-hard using results of [SC]. Those decision procedures are not as efficient as the deterministic (one or two)- exponential time procedures proposed in [BMP] and [EH1] for different logics of branching time that are weaker than ours in expressive power. No elementary decision procedure is known for a logic of branching time that is as expressive as ours. The decision procedures of the probabilistic logics of [HS] run in deterministic exponential time but their language is essentially less expressive than ours.

This paper describes a new model for dynamic distributed systems, where new processes are added and terminated at execution time. It is an extension of the static model underlying CSP. The model uses CSP I/O commands as the basic means of communications among processes, unlike the model underlying ADA, we insist that each process knows with whom it can communicate. We actually view communication as a fully symmetric operation in which values are exchanged between two processes.A problem of distributed termination arises sometimes in a distributed system. We present a new algorithm to detect distributed termination in a dynamic system. It is better than previously published solutions.

Whether an odd number m is prime can be decided on the knowledge of the image of the function $a \mapsto a^{(m - 1)/2} (m)$. As a consequence, an algorithm for testing primality is proposed (under the extended Riemann hypothesis) which is more efficient than ones proposed by Miller [Pros. 7th ACM Symp. Theory of Computing, 1975, pp. 234–239] and Vélu [SIGACT News, 10 (1978), pp. 58–59]. A probabilistic version is compared with the algorithm of Solovay and Strassen [SIAM J. Comput., 6 (1977), pp. 84–85; erratum, 7 (1978), p. 118].

It is shown that distributed systems of probabilistic processors are essentially more powerful than distributed systems of deterministic processors, i.e., there are certain useful behaviors that can be realized only by the former. This is demonstrated on the dining philosophers problem. It is shown that, under certain natural hypotheses, there is no way the philosophers can be programmed (in a deterministic fashion) so as to guarantee the absence of deadlock (general starvation). On the other hand, if the philosophers are given some freedom of choice one may program them to guarantee that every hungry philosopher will eat (with probability one) under any circumstances (even an adversary scheduling). The solution proposed here is fully distributed and does not involve any central memory or any process with which every philosopher can communicate.

A denotational semantics is given for a distributed language based on communication (CSP). The semantics uses linear sequences of communications to record computations; for any well formed program segment the semantics is a relation between attainable states and the communication sequences needed to attain these states. In binding two or more processes we match and merge the communication sequences assumed by each process to obtain a sequence and State of the combined process. The approach taken here is distinguished by relatively simple semantic domains and ordering.

Algebras whose carriers are partially ordered sets and operations are monotone and algebras whose carriers are complete partial orders and operations are continuous are studied. A quotient construction is provided for both types of algebras. The notion of a variety of algebras is defined and it is shown that the analogue of Birkhoff variety theorem holds for ordered algebras but not for continuous algebras. The results presented are a good first step towards a theory of ordered data types and a study of families of interpretations of schemas.

A precise meaning is given to general recursive definitions \nof functionals of arbitrarily high type, including non-deterministic \ndefinitions. Domain equations involving products, sums, powers and \nfunctor domains are solved. \nThe use of categories with ω-colimits as semantic domains is \ninvestigated and it is shown that such categories provide a general \nconstruction for power-domains and that no such construction can be \nobtained with partial orders. \nInitial fixpoints of continuous functors on such categories are \ndefined and studied. They provide a meaning for recursive definitions \nof the type x:=f(x). \nThe category of domains is defined and shown to possess ω-colimits. \nInitial fixpoints of continuous functors on the category of domains \nprovide the solution to domain equations. \nThe product, sum, power and functor domain of domains are defined and \nstudied. Product, sum, power and functor domain are proved to be \ncontinuous functors in the category of domains.