Fair and efficient allocation of indivisible goods without the use of money often requires randomization. However, existing mechanisms in combinatorial assignment settings only ensure desirable properties either ex ante or ex post, but not both. To address this, we introduce a class of mechanisms in which agents face a single competitive price vector that exactly clears the ex-ante economy while approximately clearing every ex-post economy. Our Competitive Equilibrium from Random Incomes (CERI) assigns each agent a random budget of tokens, determines a profile of optimal lotteries, and sets prices that exactly clear the ex-ante economy. A CERI exists for any continuous distribution of token budgets. We establish that an allocation is ordinally efficient if and only if it is a CERI allocation and any CERI allocation can be implemented as a lottery over ex-post efficient near-feasible allocations. When token budget distributions are identical, the CERI allocation is ordinally envy-free, and when they have sufficiently small support, then every realization of the CERI allocation is ex-post envy-free up to one good. Moreover, by leveraging the single market-clearing price property, we design a CERI-based mechanism that is uniformly strategyproof, i.e., in which, with probability arbitrarily close to 1 in a large market, truthtelling strategies are weakly dominant for all agents at once. As a result, in addition to efficiency and envy-freeness properties, our CERI-based mechanism offers significantly stronger incentive-compatibility guarantees compared to existing asymptotic strategyproofness properties, which only limit deviation incentives on an agent-by-agent basis. Therefore, CERI captures difficult tradeoffs between efficiency, envy and incentive compatibility in combinatorial assignment, offers new price-theoretic foundations for several existing mechanisms, and can be practically used for a variety of applications including course allocation, allocation of food donations to food banks, and refugee resettlement.

New business models help sellers make better decisions by communicating information about market prices. However, sellers' inability to coordinate greatly reduces the efficacy of this information and can lead to market failures. We study the feasibility and benefits of providing equilibria as recommendations in economies where sellers face price uncertainty, information scarcity, and an inability to coordinate.

We introduce the notion of exploitability in cut-and-choose protocols for repeated cake cutting. If a cut-and-choose protocol is repeated, the cutter can possibly gain information about the chooser from her previous actions, and exploit this information for her own gain, at the expense of the chooser. We define a generalization of cut-and-choose protocols - forced-cut protocols - in which some cuts are made exogenously while others are made by the cutter, and show that there exist non-exploitable forced-cut protocols that use a small number of cuts per day: When the cake has at least as many dimensions as days, we show a protocol that uses a single cut per day. When the cake is 1-dimensional, we show an adaptive non-exploitable protocol that uses 3 cuts per day, and a non-adaptive protocol that uses n cuts per day (where n is the number of days). In contrast, we show that no non-adaptive non-exploitable forced-cut protocol can use a constant number of cuts per day. Finally, we show that if the cake is at least 2-dimensional, there is a non-adaptive non-exploitable protocol that uses 3 cuts per day.

We consider the problem of sampling a proper k-coloring of a graph of maximal degree Delta uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of logarithmically bounded pathwidth if k >=(1+epsilon)Delta, for any epsilon>0, using a hybrid paths argument.

In the Local Computation Algorithms (LCA) model, the algorithm is asked to compute a part of the output by reading as little as possible from the input. For example, an LCA for coloring a graph is given a vertex name (as a "query"), and it should output the color assigned to that vertex after inquiring about some part of the graph topology using "probes"; all outputs must be consistent with the same coloring. LCAs are useful when the input is huge, and the output as a whole is not needed simultaneously. Most previous work on LCAs was limited to bounded-degree graphs, which seems inevitable because probes are of the form "what vertex is at the other end of edge i of vertex v?". In this work we study LCAs for unbounded-degree graphs. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. We show that there are problems that have very efficient LCAs on any graph - specifically, we show that there is an LCA for the weak coloring problem (where a coloring is legal if every vertex has a neighbor with a different color) that uses log^* n+O(1) probes to reply to any query. As another way of dealing with large degrees, we propose a more powerful type of probe which we call a strong probe: given a vertex name, it returns a list of its neighbors. Lower bounds for strong probes are stronger than ones in the edge probe model (which we call weak probes). Our main result in this model is that roughly Omega(sqrt{n}) strong probes are required to compute a maximal matching. Our findings include interesting separations between closely related problems. For weak probes, we show that while weak 3-coloring can be done with probe complexity log^* n+O(1), weak 2-coloring has probe complexity Omega(log n/log log n). For strong probes, our negative result for maximal matching is complemented by an LCA for (1-epsilon)-approximate maximum matching on regular graphs that uses O(1) strong probes, for any constant epsilon>0.

In the single-resource dynamic fair division framework there is a homogeneous resource that is shared between agents dynamically arriving and departing over time. When n agents are present, there is only one truly ``fair'' allocation: each agent receives 1/n of the resource. Implementing this static solution in the dynamic world is notoriously impractical; there are too many disruptions to existing allocations: for a new agent to get her fair share, all other agents must give up a small piece.

We study the problem of constructing an order over a set of elements given noisy samples. We consider two models for generating the noisy samples; in both, the distribution of samples is induced by an unknown state of nature: a permutation ρ. In Mallow's model, r permutations ni are generated independently from p, each with probability proportional to e−ßdK(ρ,πί), where dK (p, πi) is the Kemeny distance between ρ and ni - the number of pairs they order differently. In the noisy comparisons model, we are given a tournament, generated from ρ as follows: if i is before j in p, then with probability 1/2 + γ, the edge between them is oriented from i to j. Both of these problems were studied by Braverman and Mossel [7]; they showed how to construct a maximum-likelihood permutation when the noise parameter (ß or γ, respectively) is constant. In this work, we obtain algorithms that work in the presence of stronger noise or respectively). In Mallow's model, our algorithm works for a relaxed solution concept: likelier than nature. That is, rather than requiring that our output maximizes the likelihood over the entire domain, we guarantee that the likelihood of our output is, w.h.p., greater than or equal to that of the true state of nature (p). An interesting feature of our algorithm is that it handles noise by adding more noise.

In this paper we present an analysis of dynamic fair division of a divisible resource, with arrivals and departures of agents. Our key requirement is that we wish to disrupt the allocation of at most a small number of existing agents whenever a new agent arrives. We construct optimal recursive mechanisms to compute the allocations and provide tight analytic bounds. Our analysis relies on a linear programming formulation and a reduction of the feasible region of the LP into a class of "harmonic allocations", which play a key role in the trade-off between the fairness of current allocations and the fairness of potential future allocations. We show that there exist mechanisms that are optimal with respect to fairness and are also Pareto efficient, which is of fundamental importance in computing applications, as system designers loathe to waste resources. In addition, our mechanisms satisfy a number of other desirable game theoretic properties.

In the online random-arrival model, an algorithm receives a sequence of $n$ requests that arrive in a random order. The algorithm is expected to make an irrevocable decision with regard to each request based only on the observed history. We consider the following natural extension of this model: each request arrives k times, and the arrival order is a random permutation of the kn arrivals; the algorithm is expected to make a decision regarding each request only upon its last arrival. We focus primarily on the case when k=2, which can also be interpreted as each request arriving at, and departing from the system, at a random time. We examine the secretary problem: the problem of selecting the best secretary when the secretaries are presented online according to a random permutation. We show that when each secretary arrives twice, we can achieve a competitive ratio of 0.767974... (compared to 1/e in the classical secretary problem), and that it is optimal. We also show that without any knowledge about the number of secretaries or their arrival times, we can still hire the best secretary with probability at least 2/3, in contrast to the impossibility of achieving a constant success probability in the classical setting. We extend our results to the matroid secretary problem, introduced by Babaioff et al. [3], and show a simple algorithm that achieves a 2-approximation to the maximal weighted basis in the new model (for k=2). We show that this approximation factor can be improved in special cases of the matroid secretary problem; in particular, we give a 16/9-competitive algorithm for the returning edge-weighted bipartite matching problem.

We introduce the notion of local computation mechanism design - designing game theoretic mechanisms that run in polylogarithmic time and space. Local computation mechanisms reply to each query in polylogarithmic time and space, and the replies to different queries are consistent with the same global feasible solution. When the mechanism employs payments, the computation of the payments is also done in polylogarithmic time and space. Furthermore, the mechanism needs to maintain incentive compatibility with respect to the allocation and payments.

Recently Rubinfeld et al. (ICS 2011, pp. 223–238) proposed a new model of sublinear algorithms called local computation algorithms. In this model, a computation problem F may have more than one legal solution and each of them consists of many bits. The local computation algorithm for F should answer in an online fashion, for any index i, the ith bit of some legal solution of F. Further, all the answers given by the algorithm should be consistent with at least one solution of F. In this work, we continue the study of local computation algorithms. In particular, we develop a technique which under certain conditions can be applied to construct local computation algorithms that run not only in polylogarithmic time but also in polylogarithmic space. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. Our main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.