Publications

We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances, while the best known achievable approximations (PROP1) are much weaker. We introduce the notion of proportionality up to the maximin item (PROPm) and show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations. PROPm provides a well-motivated middle-ground between PROP1 and PROPx, while also capturing some elements of the well-studied maximin share (MMS) benchmark: another relaxation of proportionality that has attracted a lot of attention.

Recent reinforcement learning studies extensively explore the interplay between cooperative and competitive behaviour in mixed environments. Unlike cooperative environments where agents strive towards a common goal, mixed environments are notorious for the conflicts of selfish and social interests. As a consequence, purely rational agents often struggle to maintain cooperation. A prevalent approach to induce cooperative behaviour is to assign additional rewards based on other agents' well-being. However, this approach suffers from the issue of multi-agent credit assignment, which can hinder performance. This issue is efficiently alleviated in cooperative setting with such state-of-the-art algorithms as QMIX and COMA. Still, when applied to mixed environments, these algorithms may result in unfair allocation of rewards. We propose BAROCCO, an extension of these algorithms capable to balance individual and social incentives. The mechanism behind BAROCCO is to train two distinct but interwoven components that jointly affect agents' decisions. We experimentally confirm the advantages of BAROCCO.

Dozens of school districts and college admissions systems around the world have reformed their admissions rules in recent years. As the main motivation for these reforms, the policymakers cited the strategic flaws of the rules in place: students had incentives to game the system. However, after the reforms, almost none of the new rules became strategy-proof. We explain this puzzle. We show that the rules used after the reforms are less prone to gaming according to a criterion called “strategic accessibility”: each reform expands the set of schools wherein each student can never get admission by manipulation. We also show that the existing explanation of the puzzle due to Pathak and Sönmez (2013) is incomplete.

In social choice there often arises a conflict between the majority principle (the search for a candidate that is as good as possible for as many voters as possible), and the protection of minority rights (choosing a candidate that is not overly bad for particular individuals or groups). In a context where the latter is our main concern, veto-based rules -- giving individuals or groups the ability to strike off certain candidates from the list -- are a natural and effective way of ensuring that no minority is left with an outcome they find untenable. However, such rules often fail to be anonymous, or impose specific restrictions on the number of voters and candidates. These issues can be addressed by considering the proportional veto core -- the solution to a cooperative game where every coalition is given the power to veto a number of candidates proportional to its size. However, the naive algorithm for the veto core is exponential, and the only known rules for selecting from the veto core, with an arbitrary number of voters, violate either anonymity or neutrality. In this paper we present a polynomial time algorithm for computing the veto core and present a neutral and anonymous algorithm for selecting a candidate from it. We also show that a pessimist can manipulate the veto core in polynomial time.

This paper studies a model for cooperative congestion games. There is an array of cooperative games V and a player’s strategy is to choose a subset of the set V . The player gets a certain payoff from each chosen game. The paper demonstrates that if a payoff is the Shapley or the Banzhaf value, then the corresponding cooperative congestion game has a Nash equilibrium in pure strategies. The case is examined where each game in V has a coalition partition. The stability of the vector of coalition structures is determined, taking into account the transitions of players within a game and their migrations to other games. The potential function is defined for coalition partitions, and is used as a means of proving the existence of a stable vector of coalition structures for a certain class of cooperative game values.

In research and policy-making guidelines, the single-bidder rate is a commonly used proxy of corruption in public procurement used but ipso facto, this is not evidence of a corrupt auction, but an uncompetitive auction. And while an uncompetitive auction could arise due to a corrupt procurer attempting to conceal the transaction, but it could also be a result of geographic isolation, monopolist presence, or other structural factors. In this paper, we use positive-unlabelled classification to attempt to separate public procurement auctions in the Russian Federation into auctions that are probably fair and those that are suspicious.

Do individuals consider bribery as an acceptable behavior? We use a newly-designed game to study if—and under which conditions—bystanders are willing to express disapproval for bribing behavior through costly punishment. We manipulate two key dimensions: the benefits accrued by corrupt actors and the externality imposed on idle victims. We show that on average bystanders were unresponsive nearly half of the time they witnessed bribery. We also find that context specificity matters, as bystanders were more willing to punish when bribing caused them a disadvantageous inequity with respect to corrupt actors, even if bribing enhanced overall welfare. In an additional experiment testing whether social norms play any role in punishment decisions, we find that norms did not align with the observed bystanders’ behavior. This further supports our main result that bystanders did not react to bribery due to a concern for the social norm, but rather for their own comparative disadvantage relative to corrupt actors.

We consider the problem of electing a committee of k candidates, subject to constraints as to which committees are admissible for constitutional, conventional, or practical reasons. In our framework, the candidates are given labels as an abstraction of a politician’s religion, a film’s genre, a song’s language, or other attribute, and the election outcome is constrained by interval constraints (constraints of the form “Between 3 and 5 candidates with label X”) and dominance constraints (“At least as many candidates with label X as with label Y”). The goal is to select a committee that is as good as possible among those that satisfy the constraints. The difficulty is that in the standard social choice framework we do not have a quantifiable notion of “goodness”, only a voting rule that tells us which committee is the best. In this paper we argue how the logic underlying separable and best-k rules can be extended into an ordering of committees from best to worst, and study the question of how to select the best valid committee with respect to this order. The problem is NP-hard, but we show the existence of a polynomial time solution in the case of tree-like constraints, and a fixed-parameter tractable algorithm for the general case.

The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP). The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur, for example the breakdown of a vehicle. While solving the VRSP in various settings has been an active area in operations research (OR) for decades, the ever-growing complexity of modern railway networks makes dynamic real-time scheduling of traffic virtually impossible. Recently, multi-agent reinforcement learning (MARL) has successfully tackled challenging tasks where many agents need to be coordinated, such as multiplayer video games. However, the coordination of hundreds of agents in a real-life setting like a railway network remains challenging and the Flatland environment used for the competition models these real-world properties in a simplified manner. Submissions had to bring as many trains (agents) to their target stations in as little time as possible. While the best submissions were in the OR category, participants found many promising MARL approaches. Using both centralized and decentralized learning based approaches, top submissions used graph representations of the environment to construct tree-based observations. Further, different coordination mechanisms were implemented, such as communication and prioritization between agents. This paper presents the competition setup, four outstanding solutions to the competition, and a cross-comparison between

Vulnerability to manipulation is a threat to successful matching market design. However, some manipulation is often inevitable and the mechanism designer wants to compare manipulable mechanisms and pick the best. Real-life examples include reforms in the entry-level medical labor market in the US (1998), school admissions systems in New York (2004), Chicago (2009-2010), Denver (2012), some cities in Ghana (2007-2008), and England (2005-2010). We provide a useful criterion for these design decisions: we count the number of agents with an incentive to manipulate each mechanism under consideration during these reforms, and show that this number decreased as a result of the reforms. Our conclusion is robust to further additional strategic assumptions.

Based on micro-level data on reported household earnings, expenditures and assets, provided by the Russian Longitudinal Monitoring Survey (RLMS) for the period 2000–2013, it is found that households with workers in the public sector receive lower earnings than households with members employed in the private sector but enjoy the same level of consumption. Controlling for the reported level of earnings, private households do not show a significantly higher probability of possessing summer cottages (dachas), cars and computers, or living in better housing conditions, or having a higher level of monetary savings. The differences in assets cannot be reconciled with the sizeable expenditure-income gap found. The precautionary motives of workers are not able to reconcile these discrepancies either: neither attitude to risk, nor risk itself, differ between individuals employed in the private and public sectors. It is hypothesized that employees continue working in the public sector despite their low rate of official pay, because of unreported income they receive, or bribes.

We study ex-post fairness and efficiency in the object allocation problem. A matching is individually fair if it minimizes the number of envying agents, we call it minimal envy matching, and conditional on being minimal envy also minimizes the number of envying agents in a reduced problem, we call it minimal envy-2 matching. A matching is socially fair if supported by the majority of agents against any other matching – popular matching. We observe that when a popular matching exists it is equivalent to a minimal envy-2 matching. We show the equivalence between global and local popularity: a matching is popular if and only if in no group of size up to 3 agents a majority can benefit by exchanging objects, keeping the remaining matching fixed. We algorithmically show that an arbitrary matching is path-connected with a popular matching by locally-popular exchanges in small groups. Thus a corresponding market converges to a popular matching. Popular matchings often do not exist. We define most popular matching as a matching that is popular among the largest (by cardinality) subset of agents. We show that a matching is minimal envy-2 if and only if it is minimal envy and most popular, and propose a polynomial-time algorithm to find a Pareto efficient minimal envy-2 matching.

This work proves the existence of a coalition structure that is both Nash-stable and strongly permutation-stable for classes of coalition partition games. Among them are games where player’s payoff are Aumann-Drze value or the weighted value. These results are obtained by adapting the definition of a potential function for coalition partition games.

Recent experimental evidence reveals that information is often avoided by decision makers in order to create and exploit a so-called ‘moral wiggle room’, which reduces the psychological and moral costs associated with selfish behavior. Despite the relevance of this phenomenon for corrupt practices from both a legal and a moral point of view, it has hitherto never been examined in a corruption context. We test for information avoidance in a framed public procurement experiment, in which a public official receives bribes from two competing firms and often faces a tradeoff between maximizing bribes and citizen welfare. In a treatment where officials have the option to remain ignorant about the implications of their actions for citizens, we find practically no evidence of information avoidance. We discuss possible reasons for the absence of willful ignorance in our experiment.

It is well understood that the structure of a social network is critical to whether or not agents can aggregate information correctly. In this paper, we study social networks that support information aggregation when rational agents act sequentially and irrevocably. Whether or not the information is aggregated depends, inter alia, on the order in which agents decide. Thus, to decouple the order and the topology, our model studies a random arrival order. Unlike the case of a fixed arrival order, in our model, the decision of an agent is unlikely to be affected by those who are far from him in the network. This observation allows us to identify a local learning requirement, a natural condition on the agent's neighborhood that guarantees that this agent makes the correct decision (with high probability) no matter how well other agents perform. Roughly speaking, the agent should belong to a multitude of mutually exclusive social circles. We illustrate the power of the local learning requirement by constructing a family of social networks that guarantee information aggregation despite that no agent is a social hub (in other words, there are no opinion leaders). Although the common wisdom of the social learning literature suggests that information aggregation is very fragile, another application of the local learning requirement demonstrates the existence of networks where learning prevails even if a substantial fraction of the agents are not involved in the learning process. On a technical level, the networks we construct rely on the theory of expander graphs, i.e., highly connected sparse graphs with a wide range of applications from pure mathematics to error-correcting codes.

Ann likes oranges much more than apples; Bob likes apples much more than oranges. Tomorrow they will receive one fruit that will be an orange or an apple with equal probability. Giving one half to each agent is fair for each realization of the fruit. However, agreeing that whatever fruit appears will go to the agent who likes it more gives a higher expected utility to each agent and is fair in the average sense: in expectation, each agent prefers the allocation to the equal division of the fruit; that is, the agent gets a fair share. We turn this familiar observation into an economic design problem: upon drawing a random object (the fruit), we learn the realized utility of each agent and can compare it to the mean of the agent’s distribution of utilities; no other statistical information about the distribution is available. We fully characterize the division rules using only this sparse information in the most efficient possible way while giving everyone a fair share. Although the probability distribution of individual utilities is arbitrary and mostly unknown to the manager, these rules perform in the same range as the best rule when the manager has full access to this distribution.

The remaining carbon budget for limiting global warming to 1.5 degrees Celsius will probably be exhausted within this decade. Carbon debt generated thereafter will need to be compensated by net-negative emissions. However, economic policy instruments to guarantee potentially very costly net carbon dioxide removal (CDR) have not yet been devised. Here we propose intertemporal instruments to provide the basis for widely applied carbon taxes and emission trading systems to finance a net-negative carbon economy. We investigate an idealized market approach to incentivize the repayment of previously accrued carbon debt by establishing the responsibility of emitters for the net removal of carbon dioxide through ‘carbon removal obligations’ (CROs). Inherent risks, such as the risk of default by carbon debtors, are addressed by pricing atmospheric CO2 storage through interest on carbon debt. In contrast to the prevailing literature on emission pathways, we find that interest payments for CROs induce substantially more-ambitious near-term decarbonization that is complemented by earlier and less-aggressive deployment of CDR. We conclude that CROs will need to become an integral part of the global climate policy mix if we are to ensure the viability of ambitious climate targets and an equitable distribution of mitigation efforts across generations.

This paper is devoted to the study of multicriteria cooperative games with vector payoffs and coalition partition. An imputation based on the concept of the Owen value is proposed. The definition of a stable coalition partition for bi-criteria games is formulated. A three-player cooperative game with the 0-1 characteristic function is considered and stability conditions of a coalition partition are established.

We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.