We consider the problem of fair division of a two dimensional heterogeneous good among several agents. Applications include division of land as well as ad space in print and electronic media. Classical cake cutting protocols either consider a one-dimensional resource, or allocate each agent several disconnected pieces. In practice, however, the two dimensional shape of the allotted piece is of crucial importance in many applications, e.g., squares or bounded aspect-ratio rectangles are most useful for building houses as well as advertisements. We thus introduce and study the problem of envy-free two-dimensional division wherein the utility of the agents depends on the geometric shape of the allocated pieces (as well as the location and size). In addition to envy-freeness, we require that the fraction allocated to each agent be at least a certain constant that depends only on the shape of the cake and the number of agents. We focus on the case where the allotted pieces must be square and the cakes are either squares or the unbounded plane. We provide algorithms for the problem for settings with two and three agents.

The modern web critically depends on aggregation of information from self-interested agents, for example opinion polls, product ratings, or crowdsourcing. We consider a setting where multiple objects (questions, products, tasks) are evaluated by a group of agents. We first construct a minimal peer prediction mechanism that elicits honest evaluations from a homogeneous population of agents with different private beliefs. Second, we show that it is impossible to strictly elicit honest evaluations from a heterogeneous group of agents with different private beliefs. Nevertheless, we provide a modified version of a divergence-based Bayesian Truth Serum that incentivizes agents to report consistently, making truthful reporting a weak equilibrium of the mechanism.

Following recent studies of iterative voting and its effects on plurality vote outcomes, we provide characterisations and complexity results for three models of iterative voting under the plurality rule. Our focus is on providing a better understanding regarding the set of equilibria attainable by iterative voting processes. We start with the basic model of plurality voting. We first establish some useful properties of equilibria, reachable by iterative voting, which enable us to show that deciding whether a given profile is an iteratively reachable equilibrium is NP-complete. We then proceed to combine iterative voting with the concept of truth bias, a model where voters prefer to be truthful when they cannot affect the outcome. We fully characterise the set of attainable truth-biased equilibria, and show that it is possible to determine all such equilibria in polynomial time. Finally, we also examine the model of lazy voters, in which a voter may choose to abstain from the election. We establish convergence of the iterative process, albeit not necessarily to a Nash equilibrium. As in the case with truth bias, we also provide a polynomial time algorithm to find all the attainable equilibria.

We present the first model of optimal voting under adversarial noise. From this viewpoint, voting rules are seen as error-correcting codes: their goal is to correct errors in the input rankings and recover a ranking that is close to the ground truth. We derive worst-case bounds on the relation between the average accuracy of the input votes, and the accuracy of the output ranking. Empirical results from real data show that our approach produces significantly more accurate rankings than alternative approaches.

We put forward a new model of congestion games where agents have uncertainty over the routes used by other agents. We take a non-probabilistic approach, assuming that each agent knows that the number of agents using an edge is within a certain range. Given this uncertainty, we model agents who either minimize their worst-case cost (WCC) or their worst-case regret (WCR), and study implications on equilibrium existence, convergence through adaptive play, and efficiency. Under the WCC behavior the game reduces to a modified congestion game, and welfare improves when agents have moderate uncertainty. Under WCR behavior the game is not, in general, a congestion game, but we show convergence and efficiency bounds for a simple class of games.

We consider the situation in which an organizer is trying to convenean event, and needs to choose whom out of a given set of agents to invite.Agents have preferences over how many attendees should be at the eventand possibly also who the attendees should be.This induces a stability requirement: All invited agents should preferattending to not attending, and all the other agents should not regretbeing not invited.The organizer's objective is to find an invitation of maximum size,subject to the stability requirement. We investigate the computational complexity of finding such an invitation when agents are truthful, as well as the mechanism design problem when agents act strategically.

We consider the problem of repeatedly matching a set of alternatives to a set of agents with dynamic ordinal preferences. Despite a recent focus on designing one-shot matching mechanisms in the absence of monetary transfers, little study has been done on strategic behavior of agents in sequential assignment problems. We formulate a generic dynamic matching problem via a sequential stochastic matching process. We design a mechanism based on random serial dictatorship (RSD) that, given any history of preferences and matching decisions, guarantees global stochastic strategyproofness while satisfying desirable local properties. We further investigate the notion of envyfreeness in such sequential settings.

Coalition formation is a fundamental problem in the organization of many multi-agent systems. In large populations, the formation of coalitions is often restricted by structural visibility and locality constraints under which agents can reorganize. We capture and study this aspect using a novel network-based model for dynamic locality within the popular framework of hedonic coalition formation games. We analyze the effects of network-based visibility and structure on the convergence of coalition formation processes to stable states. Our main result is a tight characterization of the structures based on which dynamic coalition formation can stabilize quickly. Maybe surprisingly, polynomial-time convergence can be achieved if and only if coalition formation is based on complete or star graphs.

We present a credit-based matching mechanism for dynamic barter markets — and kidney exchange in particular — that is both strategy proof and efficient, that is, it guarantees truthful disclosure of donor-patient pairs from the transplant centers and results in the maximum global matching. Furthermore, the mechanism is individually rational in the sense that, in the long run, it guarantees each transplant center more matches than the center could have achieved alone. The mechanism does not require assumptions about the underlying distribution of compatibility graphs — a nuance that has previously produced conflicting results in other aspects of theoretical kidney exchange. Our results apply not only to matching via 2-cycles: the matchings can also include cycles of any length and altruist-initiated chains, which is important at least in kidney exchanges. The mechanism can also be adjusted to guarantee immediate individual rationality at the expense of economic efficiency, while preserving strategy proofness via the credits. This circumvents a well-known impossibility result in static kidney exchange concerning the existence of an individually rational, strategy-proof, and maximal mechanism. We show empirically that the mechanism results in significant gains on data from a national kidney exchange that includes 59% of all US transplant centers.

Stackelberg security games have been widely deployed in recent years to schedule security resources. An assumption in most existing security game models is that one security resource assigned to a target only protects that target. However, in many important real-world security scenarios, when a resource is assigned to a target, it exhibits protection externalities: that is, it also protects other “neighbouring” targets. We investigate such Security Games with Protection Externalities (SPEs). First, we demonstrate that computing a strong Stackelberg equilibrium for an SPE is NP-hard, in contrast with traditional Stackelberg security games which can be solved in polynomial time. On the positive side, we propose a novel column generation based approach—CLASPE—to solve SPEs. CLASPE features the following novelties: 1) a novel mixed-integer linear programming formulation for the slave problem; 2) an extended greedy approach with a constant-factor approximation ratio to speed up the slave problem; and 3) a linear-scale linear programming that efficiently calculates the upper bounds of target-defined subproblems for pruning. Our experimental evaluation demonstrates that CLASPE enable us to scale to realistic-sized SPE problem instances.