Publications

This paper axiomatically studies the equal split-off set (cf. Branzei et al. (Banach Center Publ 71:39–46, 2006)) as a solution for cooperative games with transferable utility which extends the well-known Dutta and Ray (Econometrica 57:615–635, 1989) solution for convex games. By deriving several characterizations, we explore consistency of the equal split-off set on the domains of exact partition games and arbitrary games.

Among the bryophytes, biological growth rhythms have not yet been identified due to a lack of long‐term precision observations. Here we carry out precision field monitoring of the growth of the peat moss Sphagnum riparium using the recent geotropic curvature method. For four years, using the observation intervals of 2‐5 days, we measured 116 469 shoots and received 4 493 estimates of growth rates. We found three rhythmic growth components. The seasonal rhythm of growth has a period of about 180 days, which coincides with the seasonal temperature cycle. The circalunar growth rhythm has a period of about 29.5 days and coincides with the synodic lunar cycle. There is an acceleration near the new moon, and a slowdown in growth near the full moon. The third rhythm has a period of 7‐16 days and is always synchronized with the circalunar growth rhythm. From the models of the sums of sinusoids, we found that the total contribution of all three rhythms to the growth rate is R2 = 0.51‐0.78, and without taking into account the seasonal rhythm, R2 = 0.36‐0.42. Thus, our study gives the first data on the biological rhythms and the contribution of these rhythms to the growth process of bryophytes. We attribute the unexpectedly high contribution of rhythms to the synchronous growth of the Sphagnum mat, which is necessary to reduce the loss of moisture.

We study voting rules with respect to how they allow or limit a majority from dominating minorities: whether a voting rule makes a majority powerful and whether minorities can veto the candidates they do not prefer. For a given voting rule, the minimal share of voters that guarantees a victory to one of the majority’s most preferred candidates is the measure of majority power; and the minimal share of voters that allows the minority to veto each of their least preferred candidates is the measure of veto power. We find tight bounds on such minimal shares for voting rules that are popular in the literature and used in real elections. We order the rules according to majority power and veto power. Instant-runoff voting has both the highest majority power and the highest veto power; plurality rule has the lowest. In general, the greater is the majority power of a voting rule, the greater its veto power. The three exceptions are: voting with proportional veto power, Black’s rule and Borda’s rule, which have relatively weak majority power and strong veto power, thus providing minority protection. Our results can shed light on how voting rules provide different incentives for voter participation and candidate nomination.

This paper studies bankruptcy problems with nontransferable utility as a generalization of bankruptcy problems with monetary estate and claims. Following the theory on TU-bankruptcy, we introduce a duality notion for NTU-bankruptcy rules and derive several axiomatic characterizations of the proportional rule and the constrained relative equal awards rule.

It follows from negative plant growth response that the solar UV-B wavelengths that penetrate the ozone layer (≥286 nm), in contrast to those absorbed (<286 nm), must leave growth inhibition fingerprints on plants. These fingerprints are expected from the growth of the Sphagnum genus, which are dominant in boreal and subarctic peatlands and have increased sensitivity to ambient UV-B. To test this hypothesis, we analysed the response of the daily growth rates of Sphagnum riparium measured over four years to solar UV radiation of 200–310 nm wavelengths recorded outside the Earth's atmosphere by SORCE satellite. We found that only wavelengths longer than 286 nm inhibit Sphagnum growth, while shorter wavelengths do not affect growth process. The data precisely correspond to the physical data on the specific wavelengths reaching the Earth’s surface. Based on the universal UVR8-dependent mechanism of UV-B perception in plants, we concluded that plants with increased UV sensitivity have indicator potential for the evaluation of the penetration of the shortest solar UV wavelengths through the ozone layer.

A tournament can be represented as a set of candidates and the results from pairwise comparisons of the candidates. In our setting, candidates may form coalitions. The candidates can choose to fix who wins the pairwise comparisons within their coalition. A coalition is winning if it can guarantee that a candidate from this coalition will win each pairwise comparison. This approach divides all coalitions into two groups and is, hence, a simple game. We show that each minimal winning coalition consists of a certain uncovered candidate and its dominators. We then apply solution concepts developed for simple games and consider the desirability relation and the power indices which preserve this relation. The tournament solution, defined as the maximal elements of the desirability relation, is a good way to select the strongest candidates. The Shapley–Shubik index, the Penrose–Banzhaf index, and the nucleolus are used to measure the power of the candidates. We also extend this approach to the case of weak tournaments.

We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by Bogomolnaia et al (2017). For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash Social Welfare on the Pareto frontier of the set of feasible utilities. The rule becomes multivalued and none of the standard methods can be applied to compute its outcome. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive allocation can be constructed via explicit formula; and a given allocation can be checked for being competitive using a maximum flow computation as in Devanur et al (2002). Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy (2018).

We give a criterion of positivity for the value of a matrix game. We use the criterion to investigate conditions of positivity of value for two classes of games: payoff matrices with all elements outside of the main diagonal having the same sign and symmetric payoff matrices.

We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. We point out that the result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.

This paper introduces and analyzes a procedural egalitarian solution for nontransferable utility games. This concept is based on an egalitarian procedure in which egalitarian opportunities of coalitions are explicitly taken into account. We formulate conditions under which the new solution prescribes a core element and derive a direct expression on the class of bargaining games and the class of bankruptcy games.

Using a simplified multistage bidding model with asymmetrically informed agents, De Meyer and Saley [17] demonstrated an idea of endogenous origin of the Brownian component in the evolution of prices on stock markets: random price fluctuations may be caused by strategic randomization of “insiders.” The model is reduced to a repeated game with incomplete information. This paper presents a survey of numerous researches inspired by the pioneering publication of De Meyer and Saley.

We investigate how prescriptive and descriptive norms affect the development of corruption over time. In particular, we are interested in whether the extent of corruption converges. If it does, we study how the level at which it converges depends on the prescriptive norms in the environment in which it takes place and on the information individuals have about others’ corrupt choices, that is, on descriptive norms. In a laboratory experiment implemented in Italy, China and the Netherlands, a Gneezy-type corruption task is used, with a real-effort task. We use a Krupka-Weber elicitation method to obtain information about existing prescriptive norms with respect to corrupt behavior. To induce natural variation in descriptive norms, we vary the type of information about others’ choices. Our results show that corruption is highly contagious everywhere, that is, descriptive norms affect choices. Nevertheless, differences in the effects of descriptive norms are evident across countries. Prescriptive norms concerning bribers’ and judges’ behaviors are observed to differ across the considered subject pools. While in China and the Netherlands it is highly socially inappropriate to bribe and, if you are a decision maker, to treat unfavorably people with high efforts and low bribes, in Italy the norms are the opposite.

Positive-Unlabeled Learning is an analog of supervised binary classification for the case when the Negative (N) sample in the training set is contaminated with latent instances of the Positive (P) class and hence is Unlabeled (U). We develop DEDPUL1 , a method able to solve two problems: first, to estimate the proportions of the mixing components (P and N) in U, and then, to classify U. The main steps are to reduce dimensionality of the data using Non-Traditional Classifier [11], to estimate densities of the reduced data in both P and U samples, and to apply the Bayes rule to density ratio. We experimentally show that DEDPUL outperforms current state-of-the-art methods for both problems. Additionally, we improve current state-of-the-art method for PU Classification [16].

We compare the Egalitarian rule (aka Egalitarian Equivalent) and the Competitive rule (aka Competitive Equilibrium with Equal Incomes) to divide bads (chores). They are both welfarist: the competitive disutility profile(s) are the critical points of their Nash product on the set of efficient feasible profiles. The C rule is Envy Free, Maskin Monotonic, and has better incentives properties than the E rule. But, unlike the E rule, it can be wildly multivalued, admits no selection continuous in the utility and endowment parameters, and is harder to compute. Thus in the division of bads, unlike that of goods, no rule normatively dominates the other.

We consider the problem of electing a committee of k candidates, subject to some constraints as to what this committee is supposed to look like. In our framework, the candidates are given labels as an abstraction of gender, religion, ethnicity, and other attributes, and the election outcome is constrained by interval 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”. While in general this problem would require us to rethink how we determine which election outcomes are good, in the case of a committee scoring rule this becomes a constrained optimisation problem – simply find a valid committee with the highest score. In the case of weakly separable rules 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, which is otherwise NP-hard

Fair division, a key concern in the design of many social institutions, has for 70 years been the subject of interdisciplinary research at the interface of mathematics, economics, and game theory. Motivated by the proliferation of moneyless transactions on the internet, the computer science community has recently taken a deep interest in fairness principles and practical division rules. The resulting literature brings a fresh concern for computational simplicity (scalable rules) and realistic implementation. In this review of the most salient fair division results of the past 30 years, I concentrate on division rules with the best potential for practical implementation. The critical design parameter is the message space that the agents must use to report their individual preferences. A simple preference domain is key both to realistic implementation and to the existence of division rules with strong normative and incentive properties. I discuss successively the one-dimensional single-peaked domain, Leontief utilities, ordinal ranking, dichotomous preferences, and additive utilities. Some of the theoretical results in the latter domain are already implemented in the user-friendly SPLIDDIT platform

A set of objects, some goods and some bads, is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then fair division may not exist. What is the smallest number of objects that must be shared between two or more agents in order to attain a fair division? We focus on Pareto-optimal, envy-free and/or proportional allocations. We show that, for a generic instance of the problem --- all instances except of a zero-measure set of degenerate problems --- a fair and Pareto-optimal division with the smallest possible number of shared objects can be found in polynomial time, assuming that the number of agents is fixed. The problem becomes computationally hard for degenerate instances, where the agents' valuations are aligned for many objects.

We consider a setting in which agents vote to choose a fair mixture of public outcomes. The agents have dichotomous preferences: each outcome is liked or disliked by an agent. We discuss three outstanding voting rules. The Conditional Utilitarian rule, a variant of the random dictator, is strategyproof and guarantees to any group of like-minded agents an influence proportional to its size. It is easier to compute and more efficient than the familiar Random Priority rule. Its worst case (resp. average) inefficiency is provably (resp. in numerical experiments) low if the number of agents is low. The efficient Egalitarian rule protects individual agents but not coalitions. It is excludable strategyproof: I do not want to lie if I cannot consume outcomes I claim to dislike. The efficient Nash Max Product rule offers the strongest welfare guarantees to coalitions, who can force any outcome with a probability proportional to their size. But it even fails the excludable form of strategyproofness.

This research is motivated by the global warming problem, which is likely influenced by human activity. Fast-growing oil palm plantations in the tropical belt of Africa, Southeast Asia and parts of Brazil lead to significant loss of rainforest and contribute to the global warming by the corresponding decrease of carbon dioxide absorption. We propose a novel approach to monitoring of the development of such plantations based on an application of state-of-the-art Fully Convolutional Neural Networks (FCNs) to solve Semantic Segmentation Problem for Landsat imagery.