Publications

This note shows that the egalitarian Dutta and Ray (1989) solution for transferable utility games is self-antidual on the class of exact partition games. By applying a careful antiduality analysis, we derive several new axiomatic characterizations. Moreover, we point out an error in earlier work on antiduality and repair and strengthen several related characterizations on the class of convex games.

We consider fair allocation of indivisible items under additive utilities. 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. The result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.

Moulin (1981) has argued in favour of electing an alternative by giving each coalition the ability to veto a number of alternatives roughly proportional to the size of the coalition and considering the core of the resulting cooperative game. This core is guaranteed to be non-empty, and offers a large measure of protection for minorities (Kondratev and Nesterov, 2020). However, as is the norm for cooperative game theory the formulation of the concept involves considering all possible coalitions of voters, so the naive algorithm would run in exponential time, limiting the application of the rule to trivial cases only. In this work we present a polynomial time algorithm to compute the proportional veto core.

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.

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.

Given the final ranking of a competition, how should the total prize endowment be allocated among the competitors? We study consistent prize allocation rules satisfying elementary solidarity and fairness principles. In particular, we axiomatically characterize two families of rules satisfying anonymity, order preservation, and endowment monotonicity, which all fall between the Equal Division rule and the Winner-Takes-All rule. Specific characterizations of rules and subfamilies are directly obtained.

We study the set of possible joint posterior belief distributions of a group of agents who share a common prior regarding a binary state and who observe some information structure. Our main result is that, for the two-agent case, a quantitative version of Aumann's Agreement Theorem provides a necessary and sufficient condition for feasibility. For any number of agents, a related "no-trade" condition likewise provides a characterization of feasibility. We use our characterization to construct joint belief distributions in which agents are informed regarding the state, and yet receive no information regarding the other's posterior. We study a related class of Bayesian persuasion problems with a single sender and multiple receivers, and explore the extreme points of the set of feasible distributions.

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.

Recently, many matching systems around the world have been reformed. These reforms responded to objections that the matching mechanisms in use were unfair and manipulable. Surprisingly, the mechanisms remained unfair even after there forms: the new mechanisms may induce an out come with a blocking student who desires and deserves a school which she did not receive. However,as we show in this paper, the reforms introduced matching mechanisms which are more fair compared to the counterfactuals. First, most of there forms introduced mechanisms that are more fair by stability: when ever the old mechanism does not have a blocking student, the new mechanism does not have a blocking student either. Second,some reforms introduced mechanisms that are more fair by counting: the old mechanism always has at least as many blocking students as the new mechanism. These findings give a novel rationale to there forms and complement there cent literature showing that the same reforms have introduced less manipulable matching mechanisms.We furthers how that the fairness and manipulability of the mechanisms are strongly logically related.

Let F: Z^2→Z be the pointwise minimum of several linear functions. The theory of smoothing allows us to prove that under certain conditions there exists the pointwise minimal function among all integer-valued superharmonic functions coinciding with F “at infinity”. We develop such a theory to prove existence of so-called solitons (or strings) in a sandpile model, studied by S. Caracciolo, G. Paoletti, and A. Sportiello. Thus we made a step towards understanding the phenomena of the identity in the sandpile group for planar domains where solitons appear according to experiments. We prove that sandpile states, defined using our smoothing procedure, move changeless when we apply the wave operator (that is why we call them solitons), and can interact, forming triads and nodes.

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.

Satellites launched by independent spacefaring agencies and firms create space congestion and collision risk. Taking as benchmark the cost of a marginal reduction of the congestion rate, we discuss tax mechanisms financing a debris removal effort. We compare the non-cooperative equilibrium traffic when there is a tax on each new launch to recover cleanup costs, with the welfare optimal traffic under a centralized tax. We find that under the latter it is twice as easy to recover cleanup costs and increase traffic than under the former. We also show that a linear tax is twice as effective as a quadratic one.

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.