Can noncooperative behaviour of merchants lead to a market allocation that <I>prima facie</I> seems anticompetitive? We introduce a model in which service providers aim at optimizing the number of customers who use their services, while customers aim at choosing service providers with minimal customer...</i>

The Gale-Shapely algorithm for the Stable Marriage Problem is known to take \Theta(n^2) steps to find a stable marriage in the worst case, but only \Theta(n log n) steps in the average case (with n women and n men). In 1976, Knuth asked whether the worst-case running time can be improved in a...

For a random permutation π on {1,2,…,n} for fixed n, and for M⊆{1,2,…,n}, we analyse the distribution of the combined length L=L(π,M) of all cycles of π that contain at least one element of M. We give a simple, explicit formula for the probability of every possible value for L (backed...

While the very first consensus protocols for the synchronous model were designed to match the <I>worst-case</I> lower bound, deciding in exactly t+1 rounds in all runs, it was soon realized that they could be strictly improved upon by <I>early stopping</I> protocols. These dominate the first ones, by always...</i></i>

Gale and Sotomayor (1985) have shown that in the Gale-Shapley matching algorithm (1962), the proposed-to side W (referred to as <i>women</i> there) can strategically force the W-optimal stable matching as the M-optimal one by truncating their preference lists, each woman possibly blacklisting <i>all but...</i>

We quantify the effect of Bayesian ignorance by comparing the social cost obtained in a Bayesian game by agents with local views to the expected social cost of agents having global views. Both benevolent agents, whose goal is to minimize the social cost, and selfish agents, aiming at minimizing...

We consider the problem of locating a facility on a network, represented by a graph. A set of strategic agents have different ideal locations for the facility; the cost of an agent is the distance between its ideal location and the facility. A mechanism maps the locations reported by the agents...