We study a matching problem between agents and public goods, in settings without monetary transfers. Since goods are public, they have no capacity constraints. There is no exogenously defined budget of goods to be provided. Rather, each provided good must justify its cost by being utilized by sufficiently many agents, leading to strong complementarities in the "preferences" of goods. Furthermore, goods that are in high demand given other already-provided goods must also be provided. The question of the existence of a stable solution (a menu of public goods to be provided) exhibits a rich combinatorial structure. We uncover sufficient conditions and necessary conditions for guaranteeing the existence of a stable solution, and derive both positive and negative results for strategyproof stable matching.

We consider the menu size of auctions as a measure of auction complexity and study how it affects revenue. Our setting has a single revenue-maximizing seller selling two or more heterogeneous items to a single buyer whose private values for the items are drawn from a (possibly correlated) known distribution, and whose valuation is additive over the items. We show that the revenue may increase arbitrarily with menu size and that a bounded menu size can not ensure any positive fraction of the optimal revenue. The menu size turns out to "nail down" the revenue properties of deterministic auctions: their menu size may be at most exponential in the number of items and indeed their revenue may be larger than that achievable by the simplest types of auctions by a factor that is exponential in the number of items but no larger. Our model is related to a previously studied "unit-demand" model and our results also answer an open problem in that model.

Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible multi-item setting: two items and a single buyer who has independently distributed values for the items, and an additive valuation. In general, the revenue achievable from selling two independent items may be strictly higher than the sum of the revenues obtainable by selling each of them separately. In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two items even in this simple setting is not understood.

We study the question of how long it takes players to reach a Nashequilibrium in uncoupled setups, where each player initially knowsonly his own payoff function. We derive lower bounds on the communication complexity of reaching a Nash equilibrium, i.e., on thenumber of bits that need to be transmitted, and thus also on the requirednumber of steps. Specifically, we show lower bounds that are exponential inthe number of players in each one of the following cases: (1) reaching apure Nash equilibrium; (2) reaching a pure Nash equilibrium in a Bayesiansetting; and (3) reaching a mixed Nash equilibrium. We then show that, incontrast, the communication complexity of reaching a correlated equilibriumis polynomial in the number of players.

Consider a finite set of processes, such that each one may use randomizations in its course of execution; these processes are running concurrently, under a fair interleaving schedule. We analyze the worst-case probability of termination, i.e., program convergence to a specified set of goal states. Several methods for computing this probability are presented, and characterizations of the special case where it is identically 1 are derived. Specializations of these characterizations to the case of deterministic and nondeterministic programs, and to the case of programs with finite state spaces, are also discussed.

Davenport-Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We show that the maximal length of a Davenport-Schinzel sequence composed of n symbols is (n /spl alpha/(n)), where /spl alpha/ (n) is the functional inverse of Ackermann's function, and is thus very slow growing. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes.

We present two (closely-related) propositional probabilistic temporal logics based on temporal logics of branching time as introduced by Ben-Ari, Pnueli and Manna and by Clarke and Emerson. The first logic, PTLf, is interpreted over finite models, while the second logic, PTLb, which is an extension of the first one, is interpreted over infinite models with transition probabilities bounded away from 0. The logic PTLf allows us to reason about finite-state sequential probabilistic programs, and the logic PTLb allows us to reason about (finite-state) concurrent probabilistic programs, without any explicit reference to the actual values of their state-transition probabilities. A generalization of the tableau method yields exponential-time decision procedures for our logics, and complete axiomatizations of them are given. Several meta-results, including the absence of a finite-model property for PTLb, and the connection between satisfiable formulae of PTLb and finite state concurrent probabilistic programs, are also discussed.

A general method for proving properties of probabilistic programs is presented. This method generalizes the intermediate assertion method in that it extends a given assertion on the output distribution into an invariant assertion on all intermediate distributions, too. The proof method is shown to be sound and complete for programs which terminate with probability 1. A dual approach, based on the expected number of visits in each intermediate state, is also presented. All the methods are presented under the uniform framework which considers a probabilistic program as a discrete Markov process.

The asynchronous execution behavior of several concurrent processes, which may use randomization, is studied.Viewing each process as a discrete Markov chain over the set of common execution states, necessary and sufficient conditions are given for the processes to converge almost surely to a given set of goal states under any fair, but otherwise arbitrary, schedule, provided that the state space is finite.(These conditions can be checked mechanically.)An interesting feature of the proof method is that it depends only on the topology of the transitions and not on the actual values of the probabilities.It is also shown that in this model synchronization protocols that use randomization are in certain cases no more powerful than deterministic protocols.This is demonstrated by (1) establishing lower bounds, similar to those known for deterministic protocols, on the size of a shared variable necessary to ensure mutual exclusion and lockout-free behavior of a "randomized" protocol and ( 2) showing that no fully symmetric "randomized" protocol can ensure mutual exclusion and freedom from lockout.

The asynchronous execution behavior of several concurrent processes, which may use randomization, is studied. Viewing each process as a discrete Markov chain over the set of common execution states, we give necessary and sufficient conditions for the processes to converge almost surely to a given set of goal states, under any fair, but otherwise arbitrary schedule, provided that the state space is finite. (These conditions can be checked mechanically.) An interesting feature of the proof method is that it depends only on the topology of the transitions and not on the actual values of the probabilities. We also show that in our model synchronization protocols that use randomization are in certain cases no more powerful than deterministic protocols. This is demonstrated by (a) Proving lower bounds on the size of a shared variable necessary to ensure mutual exlusion and lockout-free behavior of the protocol; and (b) Showing that no fully symmetric 'randomized' protocol can ensure mutual exclusion and freedom from lockout.