Search

In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make betterinformed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations. For problems such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and Short Cycle Packing, we design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms. Our results extend to problems like k-Constrained Resource Allocation, General Graph k-Matching, and k-Clique Packing, when k is restricted to be any constant. [ABSTRACT FROM AUTHOR]

We revisit the discrete heterogeneous two-facility location problem, in which there is a set of agents that occupy nodes of a line graph and have private approval preferences over two facilities. When the facilities are located at some nodes of the line, each agent suffers a cost that is equal to her total distance from the facilities she approves. The goal is to decide where to locate the two facilities so as to (a) incentivize the agents to truthfully report their preferences and (b) achieve a good approximation of the minimum total (social) cost or the maximum cost among all agents. For both ob jectives, we design deterministic strategyproof mechanisms with approximation ratios that significantly outperform the state of the art and complement these results with (almost) tight lower bounds. [ABSTRACT FROM AUTHOR]

In this article we survey the main research topics of our group at the University of Essex. Our research interests lie at the intersection of theoretical computer science, artificial intelligence, and economic theory. In particular, we focus on the design and analysis of mechanisms for systems involving multiple strategic agents, both from a theoretical and an applied perspective. We present an overview of our group's activities, as well as its members, and then discuss in detail past, present, and future work in multi-agent systems. [ABSTRACT FROM AUTHOR]

We consider the One-Sided Matching problem, where n agents have preferences over n items, and these preferences are induced by underlying cardinal valuation functions. The goal is to match every agent to a single item so as to maximize the social welfare. Most of the related literature, however, assumes that the values of the agents are not a priori known, and only access to the ordinal preferences of the agents over the items is provided. Consequently, this incomplete information leads to loss of efficiency, which is measured by the notion of distortion. In this paper, we further assume that the agents can answer a small number of queries, allowing us partial access to their values. We study the interplay between elicited cardinal information (measured by the number of queries per agent) and distortion for One-Sided Matching, as well as a wide range of well-studied related problems. Qualitatively, our results show that with a limited number of queries, it is possible to obtain significant improvements over the classic setting, where only access to ordinal information is given. [ABSTRACT FROM AUTHOR]

Recent results have shown that algorithms for learning the optimal commitment in a Stackelberg game are susceptible to manipulation by the follower. These learning algorithms operate by querying the best responses of the follower, who consequently can deceive the algorithm by using fake best responses, typically by responding according to fake payoffs that are different from the actual ones. For this strategic behavior to be successful, the main challenge faced by the follower is to pinpoint the fake payoffs that would make the learning algorithm output a commitment that benefits them the most. While this problem has been considered before, the related literature has only focused on a simple setting where the follower can only choose from a finite set of payoff matrices, thus leaving the general version of the problem unanswered. In this paper, we fill this gap by showing that it is always possible for the follower to efficiently compute (near-)optimal fake payoffs, for various scenarios of learning interaction between the leader and the follower. Our results also establish an interesting connection between the follower's deception and the leader's maximin utility: through deception, the follower can induce almost any (fake) Stackelberg equilibrium if and only if the leader obtains at least their maximin utility in this equilibrium. [ABSTRACT FROM AUTHOR]

Schelling's model is an in uential model that reveals how individual perceptions and incentives can lead to residential segregation. Inspired by a recent stream of work, we study welfare guarantees and complexity in this model with respect to several welfare measures. First, we show that while maximizing the social welfare is NP-hard, computing an assignment of agents to the nodes of any topology graph with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality, introduce two new optimality notions based on it, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions as well as the complexity of computing such assignments. In addition, we show that for tree topologies, it is possible to decide whether there exists an assignment that gives every agent a positive utility in polynomial time; moreover, when every node in the topology has degree at least 2, such an assignment always exists and can be found efficiently. [ABSTRACT FROM AUTHOR]

We study the efficiency of mechanisms for allocating a divisible resource. Given scalar signals submitted by all users, such a mechanism decides the fraction of the resource that each user will receive and a payment that will be collected from her. Users are self-interested and aim to maximize their utility (defined as their value for the resource fraction they receive minus their payment). Starting with the seminal work of Johari and Tsitsiklis, a long list of papers studied the price of anarchy (in terms of the social welfare—the total users' value) of resource allocation mechanisms for a variety of allocation and payment rules. Here, we further assume that each user has a budget constraint that invalidates strategies that yield a payment that is higher than the user's budget. This subtle assumption, which is arguably more realistic, constitutes the traditional price of anarchy analysis meaningless as the set of equilibria may change drastically and their social welfare can be arbitrarily far from optimal. Instead, we study the price of anarchy using the liquid welfare benchmark that measures efficiency taking budget constraints into account. We show a tight bound of 2 on the liquid price of anarchy of the well-known Kelly mechanism and prove that this result is essentially best possible among all multiuser resource allocation mechanisms. This comes in sharp contrast to the no-budget setting where there are mechanisms that considerably outperform Kelly in terms of social welfare and even achieve full efficiency. In our proofs, we exploit the particular structure of worst-case games and equilibria, which also allows us to design (nearly) optimal two-player mechanisms by solving simple differential equations. [ABSTRACT FROM AUTHOR]

We study the efficiency of simple combinatorial auctions for the allocation of a set of items to a set of agents, with private subadditive valuation functions and budget constraints. The class we consider includes all auctions that allocate each item independently to the agent that submits the highest bid for it, and requests a payment that depends on the bids of all agents only for this item. Two well-known examples of this class are the simultaneous first and second price auctions. We focus on the pure equilibria of the induced strategic games, and using the liquid welfare as our efficiency benchmark, we show an upper bound of 2 on the price of anarchy for any auction in this class, as well as a tight corresponding lower bound on the price of stability for all auctions whose payment rules are convex combinations of the bids. This implies a tight bound of 2 on the price of stability of the well-known simultaneous first and second price auctions, which are members of the class. Additionally, we show lower bounds for the whole class, for more complex auctions (like VCG), and for settings where the budgets are assumed to be common knowledge rather than private information. [ABSTRACT FROM AUTHOR]

We study the asymmetric binary matrix partition problem that was recently introduced by Alon et al. (Proceedings of the 9th Conference on Web and Internet Economics (WINE), pp 1-14, 2013). Instances of the problem consist of an $$n \times m$$ binary matrix A and a probability distribution over its columns. A partition scheme $$B=(B_1,\ldots ,B_n)$$ consists of a partition $$B_i$$ for each row i of A. The partition $$B_i$$ acts as a smoothing operator on row i that distributes the expected value of each partition subset proportionally to all its entries. Given a scheme B that induces a smooth matrix $$A^B$$ , the partition value is the expected maximum column entry of $$A^B$$ . The objective is to find a partition scheme such that the resulting partition value is maximized. We present a 9/10-approximation algorithm for the case where the probability distribution is uniform and a $$(1-1/e)$$ -approximation algorithm for non-uniform distributions, significantly improving results of Alon et al. Although our first algorithm is combinatorial (and very simple), the analysis is based on linear programming and duality arguments. In our second result we exploit a nice relation of the problem to submodular welfare maximization. [ABSTRACT FROM AUTHOR]

We introduce the class of modified Schelling games in which there are different types of agents who occupy the nodes of a location graph; agents of the same type are friends, and agents of different types are enemies. Every agent is strategic and jumps to empty nodes of the graph aiming to maximize her utility, defined as the ratio of her friends in her neighborhood over the neighborhood size including herself. This is in contrast to the related literature on Schelling games which typically assumes that an agent is excluded from her neighborhood whilst computing its size. Our model enables the utility function to capture likely cases where agents would rather be around a lot of friends instead of just a few, an aspect that was partially ignored in previous work. We provide a thorough analysis of the (in)efficiency of equilibria that arise in such modified Schelling games, by bounding the price of anarchy and price of stability for both general graphs and interesting special cases. Most of our results are tight and exploit the structure of equilibria as well as sophisticated constructions. [ABSTRACT FROM AUTHOR]

We study the problem of fairly allocating indivisible goods between groups of agents using the recently introduced relaxations of envy-freeness. We consider the existence of fair allocations under different assumptions on the valuations of the agents. In particular, our results cover cases of arbitrary monotonic, responsive, and additive valuations, while for the case of binary valuations we fully characterize the cardinalities of two groups of agents for which a fair allocation can be guaranteed with respect to both envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX). Moreover, we introduce a new model where the agents are not partitioned into groups in advance, but instead the partition can be chosen in conjunction with the allocation of the goods. In this model, we show that for agents with arbitrary monotonic valuations, there is always a partition of the agents into two groups of any given sizes along with an EF1 allocation of the goods. We also provide an extension of this result to any number of groups. [ABSTRACT FROM AUTHOR]

We consider the classic problem of fairly allocating indivisible goods among agents with additive valuation functions and explore the connection between two prominent fairness notions: maximum Nash welfare (MNW) and envy-freeness up to any good (EFX). We establish that an MNW allocation is always EFX as long as there are at most two possible values for the goods, whereas this implication is no longer true for three or more distinct values. As a notable consequence, this proves the existence of EFX allocations for these restricted valuation functions. While the efficient computation of an MNW allocation for two possible values remains an open problem, we present a novel algorithm for directly constructing EFX allocations in this setting. Finally, we study the question of whether an MNW allocation implies any EFX guarantee for general additive valuation functions under a natural new interpretation of approximate EFX allocations. [ABSTRACT FROM AUTHOR]