Publications
Despite several rounds of institutional reform starting from 2005, the public procurement process in Russia remains marred by low competitiveness and inefficiency. In the years 2014–2018, almost half of the studied auctions failed to attract more than a single-bidder. But are single-bidder auctions necessarily uncompetitive? The auction format we study is a sealed-bid auction, where a bidder is unaware of who else is participating. If they were to submit a bid with the expectation of competition that fails to materialise, for all means and purposes the auction can be said to be competitive. More importantly, the presence of many bidders does not guarantee competition – we could be facing a cartel, or the restriction of competition via a corrupt procurer, such as the case of bid-leakage. We assume that bids in multi-bidder auctions are predominantly competitive while bids in single-bidder auctions are not, and apply generalized confident learning, a method for classification in the presence of noisy labels, to attempt to separate competitive and uncompetitive bids. This allows us to identify behaviour patterns resembling monopolists and cartels.
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.
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.
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 cover of a transport, social, or communication network is a computationally complex problem. To deal with it, this paper introduces a special class of simple games in which the set of minimal winning coalitions coincides with the set of least covers. A distinctive feature of such a game is that it has a weighted form, in which weights and quota are sets rather than real numbers. This game class is termed set-weighted games. A real-life network has a large number of least covers, therefore this paper develops methods for analyzing set-weighted games in which the weighted form is taken into account. The necessary and sufficient conditions for a simple game to be a set-weighted game were found. The vertex cover game (Gusev, 2020) was shown to belong to the set-weighted game class, and its weighted form was found. The set-weighted game class has proven to be closed under operations of union and intersection, which is not the case for weighted games. The sample object is the transport network of a district in Petrozavodsk, Russia. A method is suggested for efficiently deploying surveillance cameras at crossroads so that all transport network covers are taken into account.
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.
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.
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.
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.
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.