A fixed set of n agents share a random object: the distribution μ of the profile of utilities is IID across periods, but arbitrary across agents. We consider a class of online division rules that learn the realized utility profile, and only know from μ the individual expected utilities. They have no record from past realized utilities, and do not know either if and how many new objects will appear in the future. We call such rules prior-independent.
A rule is fair if each agent, ex ante, expects at least 1/n-th of his utility for the object if it is a good, at most 1/n-th of his disutility for it if it is a bad. Among fair prior-independent rules to divide goods (bads) we uncover those collecting the largest (lowest) total expected (dis)utility. There is exactly one fair rule for bads that is optimal in this sense. But for goods, the set of optimal fair rules is one dimensional. Both in the worst case and in the asymptotic sense, our optimal rules perform much better than the natural Proportional rule (for goods or for bads), and not much worse than the optimal fair prior-dependent rule that knows the full distribution μ in addition to realized utilities.
Positive-Unlabeled Classification is an analog of 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 DEDPUL, a novel method that simultaneously solves two problems concerning U: estimates the proportions of the mixing components (P and N) in U and classifies U. We conduct experiments on synthetic and real-world data and show that DEDPUL outperforms current state-of-the-art methods for both problems. We suggest an automatic procedure for the objective choice of DEDPUL hyperparameters. Additionally, we improve two methods from the literature.
We propose a novel machine-learning-based approach to detect bid leakage in first-price sealed-bid auctions. We extract and analyze the data on more than 1.4 million Russian procurement auctions between 2014 and 2018. As bid leakage in each particular auction is tacit, the direct classification is impossible. Instead, we reduce the problem of bid leakage detection to Positive-Unlabeled Classification. The key idea is to regard the losing participants as fair and the winners as possibly corrupted. This allows us to estimate the prior probability of bid leakage in the sample, as well as the posterior probability of bid leakage for each specific auction. We find that at least 16% of auctions are exposed to bid leakage. Bid leakage is more likely in auctions with a higher reserve price, lower number of bidders and lower price fall, and where the winning bid is received in the last hour before the deadline.
The Gibbard–Satterthwaite theorem is a cornerstone of social choice theory, stating that an onto social choice function cannot be both strategy-proof and non-dictatorial if the number of alternatives is at least three. The Duggan–Schwartz theorem proves an analogue in the case of set-valued elections: if the function is onto with respect to singletons, and can be manipulated by neither an optimist nor a pessimist, it must have a weak dictator. However, the assumption that the function is onto with respect to singletons makes the Duggan–Schwartz theorem inapplicable to elections which necessarily select multiple winners. In this paper we make a start on this problem by considering rules which always elect exactly two winners (such as the consulship of ancient Rome). We establish that if such a consular election rule cannot be expressed as the union of two disjoint social choice functions, then strategy-proofness implies the existence of a dictator. Although we suspect that a similar result holds for k-winner rules for k>2k>2, there appear to be many obstacles to proving it, which we discuss in detail.
Global gridded crop models (GGCMs) are essential tools for estimating agricultural crop yields and externalities at large scales, typically at coarse spatial resolutions. Higher resolution estimates are required for robust agricultural assessments at regional and local scales, where the applicability of GGCMs is often limited by low data availability and high computational demand. An approach to bridge this gap is the application of meta-models trained on GGCM output data to covariates of high spatial resolution. In this study, we explore two machine learning approaches – extreme gradient boosting and random forests - to develop meta-models for the prediction of crop model outputs at fine spatial resolutions. Machine learning algorithms are trained on global scale maize simulations of a GGCM and exemplary applied to the extent of Mexico at a finer spatial resolution. Results show very high accuracy with R2>0.96 for predictions of maize yields as well as the hydrologic externalities evapotranspiration and crop available water with also low mean bias in all cases. While limited sets of covariates such as annual climate data alone provide satisfactory results already, a comprehensive set of predictors covering annual, growing season, and monthly climate data is required to obtain high performance in reproducing climate-driven inter-annual crop yield variability. The findings presented herein provide a first proof of concept that machine learning methods are highly suitable for building crop meta-models for spatio-temporal downscaling and indicate potential for further developments towards scalable crop model emulators.
This research is motivated by sustainability problems of oil palm expansion. Fast-growing industrial Oil Palm Plantations (OPPs) 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 expansion of OPPs based on an application of state-of-the-art Fully Convolutional Neural Networks (FCNs) to solve Semantic Segmentation Problem for Landsat imagery. The proposed approach significantly outperforms per-pixel classification methods based on Random Forest using texture features, NDVI, and all Landsat bands. Moreover, the trained FCN is robust to spatial and temporal shifts of input data. The paper provides a proof of concept that FCNs as semi-automated methods enable OPPs mapping of entire countries and may serve for yearly detection of oil palm expansion.
This paper analyzes bankruptcy games with nontransferable utility as a generalization of bankruptcy games with monetary payoffs. Following the game theoretic approach to NTU-bankruptcy problems, we study some appropriate properties and the core of NTU-bankruptcy games. Generalizing the core cover and the reasonable set to the class of NTU-games, we show that NTU-bankruptcy games are compromise stable and reasonable stable. Moreover, we derive a necessary and sufficient condition for an NTU-bankruptcy rule to be game theoretic.
This paper takes an axiomatic bargaining approach to bankruptcy problems with nontransferable utility by characterizing bankruptcy rules in terms of properties from bargaining theory. In particular, we derive new axiomatic characterizations of the proportional rule, the truncated proportional rule, and the constrained relative equal awards rule using properties which concern changes in the estate or the claims.
This work is devoted to study cooperative solutions in the games with Looking Forward Approach. LFA is used for constructing game theoretical models and defining solutions for conflict-controlled processes where information about the process updates dynamically. We suppose that during the game players lack certain information about the motion equation and payoff function. At each instant players possess only the truncated information about the game structure. At a given instants information about the game updates, players receive new updated information and adapt. Described model cannot be formulized using classical differential game technics. The new resulting cooperative solution for LFA models is presented and studied
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 random public signals on the state of two-person zero-sum game with incomplete information on both sides (both players do not know the state of the game). To learn the state, each player chooses a finite automaton which receives the public signal; the player only sees the output of the automaton chosen. Supposing that the size of automata available to Player 1 is essentially bigger than that available to Player 2, we give an example of public signal with random length of output strings where the posterior belief of Player 1 is the state and the posterior belief of Player 2 is close to his original belief. Thus, we demonstrate that asymmetric information about the state of a game may appear not only due to a private signal but as a result of a public signal and asymmetric computational resources of players.Besides, for a class of random signals with fixed length of output strings, we estimate the fraction of signals such that some automaton of given size may help Player 2 to significantly reestimate prior probability of the state. We show that this fraction is negligible if the size of automata of Player 2 is sufficiently smaller than length of output strings.
The theory of tropical series, that we develop here, firstly appeared in the study of the growth of pluriharmonic functions. Motivated by waves in sandpile models we introduce a dynamic on the set of tropical series, and it is experimentally observed that this dynamic obeys a power law. So, this paper serves as a compilation of results we need for other articles and also introduces several objects interesting by themselves.
We prove that the number o fLegendrian rational cubics in CP^3 through three generic points and a line is three. Also, we classify all Legendrian curves on a quadric surface. Additionally, several computations are verified using Macaulay2 computer algebra system.
The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting dense subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach is based on hedonic games. Both approaches allow to detect clusters with various resolutions. However, the tuning of the resolution parameter in the hedonic games approach is particularly intuitive. Furthermore, the modularity-based approach and its generalizations as well as ratio cut and normalized cut methods can be viewed as particular cases of the hedonic games. Finally, for approaches based on potential hedonic games we suggest a very efficient computational scheme using Gibbs sampling.
The paper applies Looking Forward Approach to analyze the world oil market with the framework of a differential game model of quantity competition oligopoly. Namely Looking Forward Approach is used to take into account dynami- cally updating information. Under the information we understand the forecast of the oil demand dynamics. We focus on the period from December 2015 to November 2016 and suppose that during this time interval countries did not cooperate offi- cially on the amounts of oil to be produced. Therefore, their behavior can be mod- eled using the non-cooperative game model. As a solution concept for this conflict- controlled process we use feedback Nash equilibrium. In order to define the pa- rameters of model open source data is used, results of numerical simulations and comparison with the historical data are presented.
We consider repeated zero-sum games with incomplete information on the side of Player 2 with the total payoff given by the non-normalized sum of stage gains. In the classical examples the value of such an N-stage game is of the order of N or of square root of N, as N tends to infinity. Our aim is to find what is causing another type of asymptotic behavior of the value observed for the discrete version of the financial market model introduced by De Meyer and Saley. For this game Domansky and independently De Meyer with Marino found that the value remains bounded, as N tends to infinity, and converges to the limit value. This game is almost-fair, i.e., if Player 1 forgets his private information the value becomes zero. We describe a class of almost-fair games having bounded values in terms of an easy-checkable property of the auxiliary non-revealing game. We call this property the piecewise property, and it says that there exists an optimal strategy of Player 2 that is piecewise-constant as a function of a prior distribution. Discrete market models have the piecewise property. We show that for non-piecewise almost-fair games with an additional non-degeneracy condition the value is of the order of square root of N.
We describe the configuration space S of polygons with prescribed edge slopes, and study the perimeter P as a Morse function on S. We characterize critical points of P (these are tangential polygons) and compute their Morse indices. This setup is motivated by a number of results about critical points and Morse indices of the oriented area function defined on the configuration space of polygons with prescribed edge lengths (flexible polygons). As a by-product, we present an independent computation of the Morse index of the area function (obtained earlier by Panina and Zhukova).