We study revenue maximization for agents with additive preferences, subject to downward-closed constraints on the set of feasible allocations. In seminal work,~\citet{alaei2014bayesian} introduced a powerful multi-to-single agent reduction based on an ex-ante relaxation of the multi-agent problem. This reduction employs a rounding procedure which is an online contention resolution scheme (OCRS) in disguise, a now widely-used method for rounding fractional solutions in online Bayesian and stochastic optimization problems. In this paper, we leverage our vantage point, 10 years after the work of Alaei, with a rich OCRS toolkit and modern approaches to analyzing multi-agent mechanisms; we introduce a general framework for designing non-sequential and sequential multi-agent, revenue-maximizing mechanisms, capturing a wide variety of problems Alaei's framework could not address. Our framework uses an \emph{interim} relaxation, that is rounded to a feasible mechanism using what we call a two-level OCRS, which allows for some structured dependence between the activation of its input elements. For a wide family of constraints, we can construct such schemes using existing OCRSs as a black box; for other constraints, such as knapsack, we construct such schemes from scratch. We demonstrate numerous applications of our framework, including a sequential mechanism that guarantees a $\frac{2e}{e-1} \approx 3.16$ approximation to the optimal revenue for the case of additive agents subject to matroid feasibility constraints. Finally, we show how our framework can be easily extended to multi-parameter procurement auctions, where we provide an OCRS for Stochastic Knapsack that might be of independent interest.

We consider the classic cake-cutting problem of producing fair allocations for $n$ agents, in the Robertson–Webb query model. In this model, it is known that: (i) proportional allocations can be computed using $O(n \log n)$ queries, and this is optimal for deterministic protocols; (ii) envy-free allocations (a subset of proportional allocations) can be computed using $O\left( n^{n^{n^{n^{n^{n}}}}} \right)$ queries, and the best known lower bound is $\Omega(n^2)$; (iii) perfect allocations (a subset of envy-free allocations) cannot be computed using a bounded (in $n$) number of queries. In this work, we introduce two hierarchies of new fairness notions: \newnotioninverse \,(\newnotioninverseabbrev) and \newnotionlinear \,(\newnotionlinearabbrev). An allocation is \newnotioninverseabbrev-$k$ if the allocation is complete and, for any subset of agents $S$ of size at most $k$, every agent $i \in S$ believes the value of all pieces allocated to agents in $S$ to be at least $\frac{1}{n-|S|+1}$, making the union of all pieces allocated to agents not in $S$ at most $\frac{n-|S|}{n-|S|+1}$; for \newnotionlinearabbrev-$k$ allocations, these bounds become $\frac{|S|}{n}$ and $\frac{n-|S|}{n}$, respectively. Intuitively, these notions of fairness ask that, for every agent $i$, the collective value (from the perspective of agent $i$) that a group of agents receives is limited. If the group includes $i$, its value is lower-bounded, and if the group excludes $i$, it is upper-bounded, thus providing the agent some protection against the formation of coalitions. Our hierarchies bridge the gap between proportionality, envy-freeness, and super envy-freeness. \newnotioninverseabbrev-$k$ and \newnotionlinearabbrev-$k$ coincide with proportionality for $k=1$. For all $k \leq n$, \newnotioninverseabbrev-$k$ allocations are a superset of envy-free allocations (i.e., easier to find). On the other hand, for $k \in [2, \lceil n/2 \rceil - 1]$, \newnotionlinearabbrev-$k$ allocations are incomparable to envy-free allocations. For $k \geq \lceil n/2 \rceil$, \newnotionlinearabbrev-$k$ allocations are a subset of envy-free allocations (i.e., harder to find), while \newnotionlinearabbrev-$n$ coincides with super envy-freeness: the value of each agent for their piece is at least $1/n$, and their value for the piece allocated to any other agent is at most $1/n$. We prove that \newnotioninverseabbrev-$n$ allocations can be computed using $O(n^4)$ queries in the Robertson–Webb model. On the flip side, finding \newnotioninverseabbrev-$2$ (and therefore all \newnotioninverseabbrev-$k$ for $k \geq 2$) allocations requires $\Omega(n^2)$ queries, while \newnotionlinearabbrev-$2$ (and therefore all \newnotionlinearabbrev-$k$ for $k \geq 2$) allocations cannot be computed using a bounded (in $n$) number of queries. Our results reveal that envy-free allocations occupy a curious middle ground, between a computationally impossible notion of fairness, \newnotionlinearabbrev-$\lceil n/2 \rceil$, and a computationally ``easy'' notion, \newnotioninverseabbrev-$n$.

A panel satisfies *descriptive representation* when its composition reflects the population. We examine the role of descriptive representation in collective decision making through an optimization lens, asking whether representative panels make decisions that maximize social welfare for the underlying population. Our main results suggest that, in general, representation with respect to *intersections* of two or more features guarantees higher social welfare than that achieved by the status quo of proportionally representing individual features. Moreover, an analysis of real data suggests that representation with respect to pairs of features is feasible in practice. These results have significant implications for the design of *citizens' assemblies*, which are gaining prominence in AI governance.

We consider the fundamental problem of allocating T indivisible items that arrive over time to n agents with additive preferences, with the goal of minimizing envy. This problem is tightly connected to the online multicolor discrepancy problem: vectors v1,...,vT ∈ ℝd with ||vi||2 ≤ 1 arrive online and must be, immediately and irrevocably, assigned to one of n colors to minimize [EQUATION] at each step, where Sℓ is the set of vectors having color ℓ. The special case of n = 2 is called online vector balancing. It is known that envy minimization reduces to multicolor discrepancy minimization. For an adaptive adversary, both problems have the same optimal bound: [EQUATION]; it is not known, however, whether this matches for weaker adversaries. Against an oblivious adversary, Alweiss et al. [2021] give a bound of O (log T), with high probability, for online multicolor discrepancy. Recently, Kulkarni et al. [2024] improve this to a tight [EQUATION] bound for online vector balancing. However, it has remained an open problem whether a [EQUATION] bound is possible for multicolor discrepancy. Furthermore, these results imply the state-of-the-art upper bounds for online envy minimization (for an oblivious adversary) for n and two agents, respectively; it is open whether better bounds are possible. We resolve all the aforementioned open problems. We establish that online envy minimization is, in fact, equivalent to online multicolor discrepancy for oblivious adversary: we give an [EQUATION] bound, for multicolor discrepancy, and a lower bound of [EQUATION] for envy minimization, resolving both problems. For weaker adversaries we prove that the two problems are no longer equivalent. Against an i.i.d. adversary, for online vector balancing, we give a [EQUATION] lower bound, while for envy minimization, we give an algorithm that guarantees a constant upper bound. Full version: https://arxiv.org/abs/2502.14624.

We study the problem of fairly allocating m indivisible items among n agents. Envy-free allocations, in which each agent prefers her bundle to the bundle of every other agent, need not exist in the worst case. However when agents have additive preferences and the value By of agent i for item j is drawn independently from a distribution Di, envy-free allocations exist with high probability when m ∈ Ω(n log n/log log n).

Allocating items in a fair and economically efficient manner is a central problem in fair division. We study this problem for agents with additive preferences, when items are all goods or all chores, divisible or indivisible. The celebrated notion of Nash welfare is known to produce fair and efficient allocations for both divisible and indivisible goods; there is no known analogue for dividing chores. The Nash welfare objective belongs to a large, parameterized family of objectives called the p-mean welfare functions, which includes other notable members, like social welfare and egalitarian welfare. However, among the members of this family, only the Nash welfare produces fair allocations for goods. Incidentally, Nash welfare is also the only member that satisfies the axiom of scale invariance, which is crucially associated with its fairness properties.

Food waste and food insecurity are two closely related pressing global issues. Food rescue organizations worldwide run programs aimed at addressing the two problems. In this paper, we partner with a non-profit organization in the state of Indiana that leads Food Drop, a program that is designed to redirect rejected truckloads of food away from landfills and into food banks. The truckload to food bank matching decisions are currently made by an employee of our partner organization. In addition to this being a very time-consuming task, as perhaps expected from human-based matching decisions, the allocations are often skewed: a small percentage of the possible recipients receives the majority of donations. Our goal in this partnership is to completely automate Food Drop. In doing so, we need a matching algorithm for making real-time decisions that strikes a balance between ensuring fairness for the food banks that receive the food and optimizing efficiency for the truck drivers. In this paper, we describe the theoretical guarantees and experiments that dictated our choice of algorithm in the platform we built and deployed for our partner organization. We develop a new model for dynamic fair division with two-sided preferences. There is an undirected, weighted graph, whose nodes represent counties, a subset of which have food banks that can receive donations, edge weights represent distance, and node weights represent the food-insecure population. Drivers appear over time, one in each step, and need to be matched, immediately and irrevocably, to a food bank. Drivers have a random origin node, a random final destination node, and a donation of random value. Our goal is to balance driver efficiency (drivers should not have to drive a lot) with fairness (every food bank should receive value proportionately to the food-insecure individuals it serves). We give matching upper and lower bounds that completely characterize this trade-off. Our work also makes contributions to the literature on load balancing and balls-into-bins games, that might be of independent interest. Specifically, we study the allocation of m weighted balls into n weighted bins, where each ball has two non-uniformly sampled random bin choices, and prove upper bounds, that hold with high probability, on the maximum load of any bin.

A long line of research on secure computation has confirmed that anything that can be computed, can be computed securely using a set of non-colluding parties. Indeed, this non-collusion assumption makes a number of problems solvable, as well as reduces overheads and bypasses computational hardness results, and it is pervasive across different privacy-enhancing technologies. However, it remains highly susceptible to covert, undetectable collusion among computing parties. This work stems from an observation that if the number of available computing parties is much higher than the number of parties required to perform a secure computation task, collusion attempts in privacy-preserving computations could be deterred.We focus on the prominent privacy-preserving computation task of multi-server 1-private information retrieval (PIR) that inherently assumes no pair-wise collusion. For PIR application scenarios, such as those for blockchain light clients, where the available servers can be plentiful, a single server’s deviating action is not tremendously beneficial to itself. We can make deviations undesired via small amounts of rewards and penalties, thus significantly raising the bar for collusion resistance. We design and implement a collusion mitigation mechanism on a public bulletin board with payment execution functions, considering only rational and malicious parties with no honest non-colluding servers. Privacy protection is offered for an extended period after the query executions.

An information escrow (IE) service allows its users to encrypt a message such that the message is unlocked only when a user-specified condition is satisfied. Its instantiations include timed-release encryption and allegation escrows with applications ranging from e-auctions to the #metoo movement. The proposed IE systems typically employ threshold cryptography towards mitigating the single-point-of-failure problem. Here, a set of escrow agents securely realize the IE functionality as long as a threshold or more agents behave honestly. Nevertheless, these threshold information escrow (TIE) protocols are vulnerable to premature and undetectable unlocking of messages through collusion among rational agents offering the IE service. This work presents a provably secure TIE scheme in the mixed-behavior model consisting of rational and malicious escrow agents.; any collusion attempt among the agents towards premature decryption results in penalization through a loss of (crypto-)currency and getting banned from the system. The proposed collusion-deterrent escrow (CDE) scheme introduces a novel incentive-penalty mechanism among the agents to stay honest until the user-specified decryption condition is met. In particular, each agent makes a cryptocurrency deposit before the start of the protocol instance such that the deposit amount is returned to the agent when the user-specified condition is met or can be transferred by anyone who holds a secret key corresponding to a public key associated with the instance. Using a novel combination of oblivious transfer, robust bit watermarking, and secure multi-party computation, CDE ensures that whenever the agents collude to decrypt the user data prematurely, one or more whistle-blower agents can withdraw/transfer the deposits of all other agents, thereby penalizing them. We model collusion as a game induced among rational agents offering the CDE service and show that the agents do not collude at equilibrium in game-theoretic terms. We also present a prototype implementation of the CDE protocol and demonstrate its efficiency towards use in practice. While this work does not aim to solve the collusion problem fully, it significantly raises the bar for collusion. It offers an important step towards weakening the strong non-collusion assumption pervasive across multi-party computation applications.

We consider the problem of a revenue-maximizing seller with a large number of items $m$ for sale to $n$ strategic bidders, whose valuations are drawn independently from high-dimensional, unknown prior distributions. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute, and, even when they can be found, are often rife with various counter-intuitive properties. In this paper, following a model introduced recently by Cai and Daskalakis [CD22], we consider the case that bidders' prior distributions can be well-approximated by a topic model. We design an active learning component, responsible for interacting with the bidders and outputting low-dimensional approximations of their types, and a mechanism design component, responsible for robustifying mechanisms for the low-dimensional model to work for the approximate types of the former component. On the active learning front, we cast our problem in the framework of Randomized Linear Algebra (RLA) for regression problems, allowing us to import several breakthrough results from that line of research, and adapt them to our setting. On the mechanism design front, we remove many restrictive assumptions of prior work on the type of access needed to the underlying distributions and the associated mechanisms. To the best of our knowledge, our work is the first to formulate connections between mechanism design, and RLA for active learning of regression problems, opening the door for further applications of randomized linear algebra primitives to mechanism design.

We study the problem of designing mechanisms when agents' valuation functions are drawn from unknown and correlated prior distributions. In particular, we are given a prior distribution $D$, and we are interested in designing a (truthful) mechanism that has good performance for all "true distributions" that are close to $D$ in Total Variation (TV) distance. We show that DSIC and BIC mechanisms in this setting are strongly robust with respect to TV distance, for any bounded objective function $\mathcal{O}$, extending a recent result of Brustle et al. ([BCD20], EC 2020). At the heart of our result is a fundamental duality property of total variation distance. As direct applications of our result, we (i) demonstrate how to find approximately revenue-optimal and approximately BIC mechanisms for weakly dependent prior distributions; (ii) show how to find correlation-robust mechanisms when only ``noisy'' versions of marginals are accessible, extending recent results of Bei et. al. ([BGLT19], SODA 2019); (iii) prove that prophet-inequality type guarantees are preserved for correlated priors, recovering a variant of a result of D{\"u}tting and Kesselheim ([DK19], EC 2019) as a special case; (iv) give a new necessary condition for a correlated distribution to witness an infinite separation in revenue between simple and optimal mechanisms, complementing recent results of Psomas et al. ([PSCW22], NeurIPS 2022); (v) give a new condition for simple mechanisms to approximate revenue-optimal mechanisms for the case of a single agent whose type is drawn from a correlated distribution that can be captured by a Markov Random Field, complementing recent results of Cai and Oikonomou ([CO21], EC 2021).

Searchable encryption (SE) provides cryptographic guarantees that a user can efficiently search over encrypted data while only disclosing patterns about the data, also known as leakage. Recently, the community has developed leakage-abuse attacks that shed light on what an attacker can infer about the underlying sensitive information using the aforementioned leakage. A glaring missing piece in this effort is the absence of a systematic and rigorous method that quantifies the privacy guarantees of SE.

We consider the fundamental problem of allocating a set of indivisible goods among strategic agents with additive valuation functions. It is well known that, in the absence of monetary transfers, Pareto efficient and truthful rules are dictatorial, while there is no deterministic truthful mechanism that allocates all items and achieves envy-freeness up to one item (EF1), even for the case of two agents. In this paper, we investigate the interplay of fairness and efficiency under a relaxation of truthfulness called non-obvious manipulability (NOM), recently proposed by~\citep{troyan2020obvious}. We show that this relaxation allows us to bypass the aforementioned negative results in a very strong sense. Specifically, we prove that there are deterministic and EF1 algorithms that are not obviously manipulable, and the algorithm that maximizes utilitarian social welfare (the sum of agents' utilities), which is Pareto efficient but not dictatorial, is not obviously manipulable for $n \geq 3$ agents (but obviously manipulable for $n=2$ agents). At the same time, maximizing the egalitarian social welfare (the minimum of agents' utilities) or the Nash social welfare (the product of agents' utilities) is obviously manipulable for any number of agents and items. Our main result is an approximation preserving black-box reduction from the problem of designing EF1 and NOM mechanisms to the problem of designing EF1 algorithms. En route, we prove an interesting structural result about EF1 allocations, as well as new ``best-of-both-worlds'' results (for the problem without incentives), that might be of independent interest.

Internet ad auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amounts of space, and an advertiser can provide multiple formats, only one of which can be shown.The seller is now faced with a multi-parameter mechanism design problem.Computing an efficient allocation is computationally intractable, and therefore the standard Vickrey-Clarke-Groves (VCG) auction, while truthful and welfare-optimal, is impractical. In this paper, we tackle a fundamental problem in the design of modern ad auctions. We adopt a ``Myersonian'' approach and study allocation rules that are monotone both in the bid and set of rich ads. We show that such rules can be paired with a payment function to give a truthful auction. Our main technical challenge is designing a monotone rule that yields a good approximation to the optimal welfare. Monotonicity doesn't hold for standard algorithms, e.g. the incremental bang-per-buck order, that give good approximations to ``knapsack-like'' problems such as ours. In fact, we show that no deterministic monotone rule can approximate the optimal welfare within a factor better than $2$ (while there is a non-monotone FPTAS). Our main result is a new, simple, greedy and monotone allocation rule that guarantees a $3$ approximation. In ad auctions in practice, monotone allocation rules are often paired with the so-called \emph{Generalized Second Price (GSP)} payment rule, which charges the minimum threshold price below which the allocation changes. We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) is bounded. Under standard no-overbidding assumptions, we prove bounds on the a pure and Bayes-Nash PoA. Finally, we experimentally test our algorithms on real-world data.

We consider the fundamental problem of fairly and efficiently allocating $T$ indivisible items among $n$ agents with additive preferences. The items become available over a sequence of rounds, and every item must be allocated immediately and irrevocably before the next one arrives. Previous work shows that when the agents' valuations for the items are drawn from known distributions, it is possible (under mild technical assumptions) to find allocations that are envy-free with high probability and Pareto efficient ex-post. We study a \emph{partial-information} setting, where it is possible to elicit ordinal but not cardinal information. When a new item arrives, the algorithm can query each agent for the relative rank of this item with respect to a subset of the past items. When values are drawn from i.i.d.\ distributions, we give an algorithm that is envy-free and $(1-\epsilon)$-welfare-maximizing with high probability. We provide similar guarantees (envy-freeness and a constant approximation to welfare with high probability) even with minimally expressive queries that ask for a comparison to a single previous item. For independent but non-identical agents, we obtain envy-freeness and a constant approximation to Pareto efficiency with high probability. We prove that all our results are asymptotically tight.

We consider a revenue-maximizing seller with $k$ heterogeneous items for sale to a single additive buyer, whose values are drawn from a known, possibly correlated prior $\mathcal{D}$. It is known that there exist priors $\mathcal{D}$ such that simple mechanisms --- those with bounded menu complexity --- extract an arbitrarily small fraction of the optimal revenue~(Briest et al. 2015, Hart and Nisan 2019). This paper considers the opposite direction: given a correlated distribution $\mathcal{D}$ witnessing an infinite separation between simple and optimal mechanisms, what can be said about $\mathcal{D}$?\citet{hart2019selling} provides a framework for constructing such $\mathcal{D}$: it takes as input a sequence of $k$-dimensional vectors satisfying some geometric property, and produces a $\mathcal{D}$ witnessing an infinite gap. Our first main result establishes that this framework is without loss: every $\mathcal{D}$ witnessing an infinite separation could have resulted from this framework. An earlier version of their work provided a more streamlined framework (Hart and Nisan 2013). Our second main result establishes that this restrictive framework is not tight. That is, we provide an instance $\mathcal{D}$ witnessing an infinite gap, but which provably could not have resulted from the restrictive framework. As a corollary, we discover a new kind of mechanism which can witness these infinite separations on instances where the previous ``aligned'' mechanisms do not.

A set of divisible resources becomes available over a sequence of rounds and needs to be allocated immediately and irrevocably. Our goal is to distribute these resources to maximize fairness and efficiency. Achieving any non-trivial guarantees in an adversarial setting is impossible. However, we show that normalizing the agent values, a very common assumption in fair division, allows us to escape this impossibility. Our main result is an online algorithm for the case of two agents that ensures the outcome is fair while guaranteeing 91.6% of the optimal social welfare. We also show that this is near-optimal: there is no fair algorithm that guarantees more than 93.3% of the optimal social welfare.

In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action (e.g., hire a job candidate, or convict a defendant). The sender's utility depends solely on whether or not the receiver takes the action. The receiver's utility depends on both the action and the sender's private information. We study three natural variations. First, we consider the problem of computing an equilibrium of the game without commitment power. Second, we consider a persuasion variant, where the sender commits to a signaling scheme and the receiver, after seeing the evidence, takes the action or not. Third, we study a delegation variant, where the receiver first commits to taking the action if being presented certain evidence, and the sender presents evidence to maximize the probability the action is taken. We study these variants through the computational lens, and give hardness results, optimal approximation algorithms, and polynomial-time algorithms for special cases. Among our results is an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm in algorithmic economics.

We consider the fundamental problem of selecting $k$ out of $n$ random variables in a way that the expected highest or second-highest value is maximized. This question captures several applications where we have uncertainty about the quality of candidates (e.g. auction bids, search results) and have the capacity to explore only a small subset due to an exogenous constraint. For example, consider a second price auction where system constraints (e.g., costly retrieval or model computation) allow the participation of only $k$ out of $n$ bidders, and the goal is to optimize the expected efficiency (highest bid) or expected revenue (second highest bid). We study the case where we are given an explicit description of each random variable. We give a PTAS for the problem of maximizing the expected highest value. For the second-highest value, we prove a hardness result: assuming the Planted Clique Hypothesis, there is no constant factor approximation algorithm that runs in polynomial time. Surprisingly, under the assumption that each random variable has monotone hazard rate (MHR), a simple score-based algorithm, namely picking the $k$ random variables with the largest $1/\sqrt{k}$ top quantile value, is a constant approximation to the expected highest and second highest value, \emph{simultaneously}.

The design of voting rules is traditionally guided by desirable axioms. Recent work shows that, surprisingly, the axiomatic approach can also support the generation of explanations for voting outcomes. However, no bounds on the size of these explanations is given; for all we know, they may be unbearably tedious. We prove, however, that outcomes of the important Borda rule can be explained using $O(m^2)$ steps, where $m$ is the number of alternatives. Our main technical result is a general lower bound that, in particular, implies that the foregoing bound is asymptotically tight. We discuss the significance of our results for AI and machine learning, including their potential to bolster an emerging paradigm of automated decision making called virtual democracy.

A set of T indivisible goods has to be allocated to a set of n agents with additive utilities, in a way that is fair and efficient. A standard fairness concept is envy-freeness, which requires that each agent prefers her own allocation over the allocation of any other agent. Even though envy is clearly unavoidable in this context - consider the case of a single indivisible good and two agents - providing approximately envy-free solutions is possible [3, 6]. Specifically, an allocation is envy-free up to one item (EF1) if for every pair of agents i and j, any envy i has for j can be eliminated by removing at most one good from j's bundle. Recently, Caragiannis et al. [3] show that the allocation that maximizes the product of the agents' utilities (with ties broken based on the number of agents with positive utility) is EF1 and Pareto efficient. The majority of the literature to date has focused on the case where the items are available to the algorithm upfront. In many situations of interest, however, items arrive online. A paradigmatic example is that of food banks [1, 5]. Food banks across the world receive food donations they must allocate; these donations are often perishable, and thus allocation decisions must be made quickly, and donations are typically leftovers, leading to uncertainty about items that will arrive in the future. Benadè et al. [2] study this problem, but focus only on fairness. They show that there exists a deterministic algorithm with vanishing envy, that is, the maximum pairwise envy (after all T items have been allocated) is sublinear in T , when the value vit of agent i for the t-th item is normalized to be in [0, 1]. Specifically, the envy is guaranteed to be at most O(√p T logT /n), and this guarantee is tight up to polylogarithmic factors. The same guarantee can also be achieved by the simple randomized algorithm that allocates each item to a uniformly random agent. These results hold even against an adaptive adversary that selects the value vit after seeing the allocation of the first t - 1 items. On the other hand, if we focus only on efficiency, our task is much easier. For example, we could simply allocate each item to the agent with the highest value. But, and this brings us to our interest here, the question remains: How should we make allocation decisions online in a way that is fair to the donation recipients, but also as efficient as possible?

A cache memory unit needs to be shared among n strategic agents. Each agent has different preferences over the files to be brought into memory. The goal is to design a mechanism that elicits these preferences in a truthful manner and outputs a fair and efficient memory allocation. A trivially truthful and fair solution would isolate each agent to a 1/n fraction of the memory. However, this could be very inefficient if the agents have similar preferences and, thus, there is room for cooperation. On the other hand, if the agents are not isolated, unless the mechanism is carefully designed, they have incentives to misreport their preferences and free ride on the files that others bring into memory. In this paper we explore the power and limitations of truthful mechanisms in this setting. We demonstrate that mechanisms blocking agents from accessing parts of the memory can achieve improved efficiency guarantees, despite the inherent inefficiencies of blocking.

Virtual democracy is an approach to automating decisions, by learning models of the preferences of individual people, and, at runtime, aggregating the predicted preferences of those people on the dilemma at hand. One of the key questions is which aggregation method – or voting rule – to use; we offer a novel statistical viewpoint that provides guidance. Specifically, we seek voting rules that are robust to prediction errors, in that their output on people’s true preferences is likely to coincide with their output on noisy estimates thereof. We prove that the classic Borda count rule is robust in this sense, whereas any voting rule belonging to the wide family of pairwise-majority consistent rules is not. Our empirical results further support, and more precisely measure, the robustness of Borda count.

We study the problem of allocating T indivisible items that arrive online to agents with additive valuations. The allocation must satisfy a prominent fairness notion, envy-freeness up to one item (EF1), at each round. To make this possible, we allow the reallocation of previously allocated items, but aim to minimize these so-called adjustments. For the case of two agents, we show that algorithms that are informed about the values of future items can get by without any adjustments, whereas uninformed algorithms require Theta(T) adjustments. For the general case of three or more agents, we prove that even informed algorithms must use Omega(T) adjustments, and design an uninformed algorithm that requires only O(T^(3/2)).

Algorithms increasingly govern societal functions, impacting multiple stakeholders and social groups. How can we design these algorithms to balance varying interests in a moral, legitimate way? As one answer to this question, we present WeBuildAI, a collective participatory framework that enables people to build algorithmic policy for their communities. The key idea of the framework is to enable stakeholders to construct a computational model that represents their views and to have those models vote on their behalf to create algorithmic policy. As a case study, we applied this framework to a matching algorithm that operates an on-demand food donation transportation service in order to adjudicate equity and efficiency trade-offs. The service's stakeholders--donors, volunteers, recipient organizations, and nonprofit employees--used the framework to design the algorithm through a series of studies in which we researched their experiences. Our findings suggest that the framework successfully enabled participants to build models that they felt confident represented their own beliefs. Participatory algorithm design also improved both procedural fairness and the distributive outcomes of the algorithm, raised participants' algorithmic awareness, and helped identify inconsistencies in human decision-making in the governing organization. Our work demonstrates the feasibility, potential and challenges of community involvement in algorithm design.

We study the dynamic fair division of indivisible goods. Suppose T items arrive online and must be allocated upon arrival to one of n agents, each of whom has a value in [0,1] for the current item. Our goal is to design allocation algorithms that minimize the maximum envy at time T , ENVYT, defined as the maximum difference between any agent's overall value for items allocated to another agent and to herself. We say that an algorithm has vanishing envy if the ratio of envy over time, ENVYT/T, goes to zero as T goes to infinity. We design a polynomial-time, deterministic algorithm that achieves ENVYT ın ~O ( √T/n ), and show that this guarantee is asymptotically optimal. We also derive tight (in T ) bounds for a more general setting where items arrive in batches.

The Competition Complexity of an auction measures how much competition is needed for the revenue of a simple auction to surpass the optimal revenue. A classic result from auction theory by Bulow and Klemperer [11], states that the Competition Complexity of VCG, in the case of n i.i.d. buyers and a single item, is 1. In other words, it is better to invest in recruiting one extra buyer and run a second price auction than to invest in learning exactly the buyers’ underlying distribution and run the revenue-maximizing auction tailored to this distribution. In this paper we study the Competition Complexity of dynamic auctions. Consider the following problem: a monopolist is auctioning off m items in m consecutive stages to n interested buyers. A buyer realizes her value for item k in the beginning of stage k. How many additional buyers are necessary and sufficient for a second price auction at each stage to extract revenue at least that of the optimal dynamic auction? We prove that the Competition Complexity of dynamic auctions is at most 3n - and at least linear in n - even when the buyers’ values are correlated across stages, under a monotone hazard rate assumption on the stage (marginal) distributions. This assumption can be relaxed if one settles for independent stages. We also prove results on the number of additional buyers necessary for VCG at every stage to be an α-approximation of the optimal revenue; we term this number the α-approximate Competition Complexity. For example, under the same mild assumptions on the stage distributions we prove that one extra buyer suffices for a -approximation. As a corollary we provide the first results on prior-independent dynamic auctions. This is, to the best of our knowledge, the first nontrivial positive guarantees for simple ex-post IR dynamic auctions for correlated stages. A key step towards proving bounds on the Competition Complexity is getting a good benchmark/upper bound to the optimal revenue. To this end, we extend the recent duality framework of [14] to dynamic settings. As an aside to our approach we obtain a revenue non-monotonicity lemma for dynamic auctions, which may be of independent interest.

We study a pricing problem that is motivated by the following examples. A cloud computing platform such as Amazon EC2 sells virtual machines to clients, each of who needs a different number of virtual machine hours. Similarly, cloud storage providers such as Dropbox have customers that require different amounts of storage. Software companies such as Microsoft sell software subscriptions that can have different levels of service. The levels could be the number of different documents you are allowed to create, or the number of hours you are allowed to use the software. Companies like Google and Microsoft sell API calls to artificial intelligence software such as face recognition, to other software developers. Video and mobile games are increasingly designed in such a way that one can pay for better access to certain features. Spotify and iTunes sell music subscription, and different people listen to different number of songs in a month. Cellphone service providers like AT&T and Verizon offer cellular phone call minutes and data. People have widely varying amounts of data consumption.

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 introduce a dynamic mechanism design problem in which the designer wants to offer for sale an item to an agent, and another item to the same agent at some point in the future. The agent's joint distribution of valuations for the two items is known, and the agent knows the valuation for the current item (but not for the one in the future). The designer seeks to maximize expected revenue, and the auction must be deterministic, truthful, and ex post individually rational. The optimum mechanism involves a protocol whereby the seller elicits the buyer's current valuation, and based on the bid makes two take-it-or-leave-it offers, one for now and one for the future. We show that finding the optimum deterministic mechanism in this situation — arguably the simplest meaningful dynamic mechanism design problem imaginable — is NP-hard. We also prove several positive results, among them a polynomial linear programming-based algorithm for the optimum randomized auction (even for many bidders and periods), and we show strong separations in revenue between non-adaptive, adaptive, and randomized auctions, even when the valuations in the two periods are uncorrelated. Finally, for the same problem in an environment in which contracts cannot be enforced, and thus perfection of equilibrium is necessary, we show that the optimum randomized mechanism requires multiple rounds of cheap talk-like interactions.

Traditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai et al. and Cole and Roughgarden to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden for the non-identical but independent value distribution case.

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.

We present a model for fair strategyproof allocations in a realistic model of cloud computing centers. This model has the standard Leontief preferences but also captures a key property of virtualization, the use of containers to isolate jobs. We first present several impossibility results for deterministic mechanisms in this setting. We then construct an extension of the well known dominant resource fairness mechanism (DRF), which somewhat surprisingly does not involve the notion of a dominant resource. Our mechanism relies on the connection between the DRF mechanism and the Kalai-Smorodinsky bargaining solution; by computing a weighted max-min over the convex hull of the feasible region we can obtain an ex-ante fair, efficient and strategyproof randomized allocation. This randomized mechanism can be used to construct other mechanisms which do not rely on users' being expected (ex-ante) utility maximizers, in several ways. First, for the case of $m$ identical machines one can use the convex structure of the mechanism to get a simple mechanism which is approximately ex-post fair, efficient and strategyproof. Second, we present a more subtle construction for an arbitrary set of machines, using the Shapley-Folkman-Starr theorem to show the existence of an allocation which is approximately ex-post fair, efficient and strategyproof. This paper provides both a rigorous foundation for developing protocols that explicitly utilize the detailed structure of the modern cloud computing hardware and software, and a general method for extending the dominant resource fairness mechanism to more complex settings.

This paper presents a probabilistic extension of Allen's relations that enables reasoning with intervals whose boundaries are uncertain. Building on an earlier work on an hourglass model that depicts the geometry of interval relations, we first provide further evidence that support its qualitative properties. We then specify two orthogonal axes, which quantitatively describe respectively the relative position and relative size of intervals. The quantitative hourglass model is then used to define a consistent probabilistic set of all thirteen Allen's relations. Probabilistic relations between intervals and points are also accounted for in the developed framework.