This report discusses the theory of fair division from its history to its uses in social sciences. Fair division goes beyond the envy free solution of the cake cutting problem to how people divide chores and rent and allocate assets in a divorce. Fair division can also potentially be used to solve social problems as with voting irregularities. / text

“Skills, Occupation Inequality and Development” is a theoretical study. There is no general agreement about how income inequality will affect development in the long run. Classic growth models show that income inequality is beneficial to development due to agent’s heterogeneity and marginal propensity to save increasing with wealth. Neoclassical growth models present that income distribution plays no significant role on development assuming representative agents and decreasing marginal returns in investment. New classical growth theory demonstrates that income inequality impedes growth due to credit constraints and indivisibility of investment in human capital. This paper studies income inequality through the channel of complementary skills and occupations in aggregate production. In a new classical model economy with two complementary occupations, CES production technology, skills in utility, and uncertainty of completing high-skilled occupations, we find a continuum of equilibria denoted by a correspondence between aggregate capital stock and the low-skilled population share regardless of the distribution in initial endowments. Aggregate capital stock and aggregate income per capita are non-monotonically related to the low-skilled population share. Aggregate income per capita will be maximized at a certain distribution of occupations on the continuum of equilibria. Therefore, the correlation between development and inequality of occupation distribution can be both positive and negative which depends on the position of occupation division on the continuum of equilibria. The correlation between low skills and occupation inequality is monotonic within a country, but the correlation is opposite between developed and developing economies. The low skills will move up on the continuum of equilibria if the occupation inequality is smaller (larger) in developed (developing) economies. The study also shows that inequality of the occupation distribution plays different effects in developed economies from those in developing economies due to the assumption that skills affect the completion of occupations. Developing economies also present two patterns of equilibria, in which one has higher optimum inequality of occupations, another one has lower optimum inequality of occupations. The cause of two patterns of equilibria for developing economies comes from the assumption of Cobb-Douglas production function. Shifts of equilibrium lead to new levels of development due to a change of inequality in other characteristics of the economy. “Fair Division of Income Distribution, Development and Growth: Evidence from a Panel of Countries” is an empirical exercise. I use an unbalanced panel data to explore the correlation between aggregate income per capita and income inequality. A lot of studies document controversial results using the Gini index or other summary measurements of income inequality. I measure income inequality by the two dimensions of a point on the Lorenz Curve, where the Lorenz curve has unit slope. It is called fair division point, which involves the fair population share and the fair income share. The difference between the fair population share and the fair income share approximates the Gini index of an income distribution. My analysis shows that a country’s low income population relatively decreases (the fair population share drops slightly) as the economy grows; and at the same time, those low income households are relatively worse off (the fair income share falls even though the GDP per capita increases). Inversely, as an economy becomes rich, there are more low income households (the fair population share increases), but those low income households are better off (the fair income share goes up and GDP per capita increases as well). Overall, both the Gini index and the difference between the fair population share and the fair income share have been increasing during the last half century in the panel of countries. Therefore, income inequality increases as an economy is getting richer. The analysis presents strong evidence for optimum income inequality regarding both the aggregate productivity and the growth rate of GDP, where income inequality is measured by either the Gini index or the fair division shares. But no evidence has been found for the Kuznets’ hypothesis. Both high and low inequality of income distribution could harm an economy as we compare with its potential optimum inequality. Also developed economies show different optimum inequality from that in developing economies, and there is the growth-worst fair population share that results in the lowest growth in developed economies. Measurement of income inequality matters on its economic effects for the subsamples of the panel data.

京都大学 / 新制・課程博士 / 博士(理学) / 甲第24394号 / 理博第4893号 / 新制||理||1699(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)准教授 小林 佑輔, 教授 牧野 和久, 教授 長谷川 真人 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DGAM

The first chapter is based on a paper with Jin Li in fair division. It was recently discovered that on the domain of Leontief preferences, Hurwicz (1972)'s classic impossibility result does not hold; that is, one can find efficient, strategy-proof and individually rational rules to divide resources among agents. Here we consider the problem of dividing l divisible goods among n agents with the generalized Leontief preferences. We propose and characterize the class of generalized egalitarian rules which satisfy efficiency, group strategy-proofness, anonymity, resource monotonicity, population monotonicity, envy-freeness and consistency. On the Leontief domain, our rules generalize the egalitarian-equivalent rules with reference bundles. We also extend our rules to agent-specific and endowment-specific egalitarian rules. The former is a larger class of rules satisfying all the previous properties except anonymity and envy-freeness. The latter is a class of efficient, group strategy-proof, anonymous and individually rational rules when the resources are assumed to be privately owned. The second and third chapters are based on two working papers of mine in decision making under uncertainty. In the second chapter, I study the wealth effect under uncertainty --- how the wealth level impacts a decision maker's degree of uncertainty aversion. I axiomatize a class of preferences displaying decreasing absolute uncertainty aversion, which allows a decision maker to be more willing to take uncertainty-bearing behavior when he becomes wealthier. Three equivalent preference representations are obtained. The first is a variation on the constraint criterion of Hansen and Sargent (2001). The other two respectively generalize Gilboa and Schmeidler (1989)'s maxmin criterion and Maccheroni, Marinacci and Rustichini (2006)'s variational representation. This class, when restricted to preferences exhibiting constant absolute uncertainty aversion, is exactly Maccheroni, Marinacci and Rustichini (2006)'s ariational preferences. Thus, the results further enable us to establish relationships among the representations for several important classes within variational preferences. The three representations provide different decision rules to rationalize the same class of preferences. The three decision rules correspond to three ways which are proposed in the literature to identify a decision maker's perception about uncertainty and his attitude toward uncertainty. However, I give examples to show that these identifications conflict with each other. It means that there is much freedom in eliciting two unobservable and subjective factors, one's perception about and attitude toward uncertainty, from only his choice behavior. This exactly motivates the work in Chapter 3. In the third chapter, I introduce confidence orders in addition to preference orders. Axioms are imposed on both orders to reveal a decision maker's perception about uncertainty and to characterize the following decision rule. A decision maker evaluates an act based on his aspiration and his confidence in this aspiration. Each act corresponds to a trade-off line between the two criteria: The more he aspires, the less his confidence in achieving the aspiration level. The decision maker ranks an act by the optimal combination of aspiration and confidence on its trade-off line according to an aggregating preference of his over the two-criterion plane. The aggregating preference indicates his uncertainty attitude, while his perception about uncertainty is summarized by a generalized second-order belief over the prior space, and this belief is revealed by his confidence order.

Fair division is the problem of dividing one or several goods among a set of agents in a way that satisfies a suitable fairness criterion. Traditionally studied in economics, philosophy, and political science, fair division has drawn a lot of attention from the multiagent systems community, since this field is strongly concerned about how a surplus (or a cost) should be divided among a group of agents. Arguably, the Shapley value is the single most important contribution to the problem of fair division. It assigns to each agent a share of the resource equal to the expected marginal contribution of that agent. Thus, it is implicitly assumed that individual marginal contributions can be objectively computed. In this thesis, we propose a game-theoretic model for sharing a joint reward when the quality of individual contributions is subjective. In detail, we consider scenarios where a group has been formed and has accomplished a task for which it is granted a reward, which must be shared among the group members. After observing the contribution of the peers in accomplishing the task, each agent is asked to provide evaluations for the others. Mainly to facilitate the sharing process, agents can also be requested to provide predictions about how their peers are evaluated. These subjective opinions are elicited and aggregated by a central, trusted entity, called the mechanism, which is also responsible for sharing the reward based exclusively on the received opinions. Besides the formal game-theoretic model for sharing rewards based on subjective opinions, we propose three different mechanisms in this thesis. Our first mechanism, the peer-evaluation mechanism, divides the reward proportionally to the evaluations received by the agents. We show that this mechanism is fair, budget-balanced, individually rational, and strategy-proof, but that it can be collusion-prone. Our second mechanism, the peer-prediction mechanism, shares the reward by considering two aspects: the evaluations received by the agents and their truth-telling scores. To compute these scores, this mechanism uses a strictly proper scoring rule. Under the assumption that agents are Bayesian decision-makers, we show that this mechanism is weakly budget-balanced, individually rational, and incentive-compatible. Further, we present approaches that guarantee the mechanism to be collusion-resistant and fair. Our last mechanism, the BTS mechanism, is the only one to elicit both evaluations and predictions from the agents. It considers the evaluations received by the agents and their truth-telling scores when sharing the reward. For computing the scores, it uses the Bayesian truth serum method, a powerful scoring method based on the surprisingly common criterion. Under the assumptions that agents are Bayesian decision-makers, and that the population of agents is sufficiently large so that a single evaluation cannot significantly affect the empirical distribution of evaluations, we show that this mechanism is incentive-compatible, budget-balanced, individually rational, and fair.

Fair division is the problem of dividing one or several goods among a set of agents in a way that satisfies a suitable fairness criterion. Traditionally studied in economics, philosophy, and political science, fair division has drawn a lot of attention from the multiagent systems community, since this field is strongly concerned about how a surplus (or a cost) should be divided among a group of agents. Arguably, the Shapley value is the single most important contribution to the problem of fair division. It assigns to each agent a share of the resource equal to the expected marginal contribution of that agent. Thus, it is implicitly assumed that individual marginal contributions can be objectively computed. In this thesis, we propose a game-theoretic model for sharing a joint reward when the quality of individual contributions is subjective. In detail, we consider scenarios where a group has been formed and has accomplished a task for which it is granted a reward, which must be shared among the group members. After observing the contribution of the peers in accomplishing the task, each agent is asked to provide evaluations for the others. Mainly to facilitate the sharing process, agents can also be requested to provide predictions about how their peers are evaluated. These subjective opinions are elicited and aggregated by a central, trusted entity, called the mechanism, which is also responsible for sharing the reward based exclusively on the received opinions. Besides the formal game-theoretic model for sharing rewards based on subjective opinions, we propose three different mechanisms in this thesis. Our first mechanism, the peer-evaluation mechanism, divides the reward proportionally to the evaluations received by the agents. We show that this mechanism is fair, budget-balanced, individually rational, and strategy-proof, but that it can be collusion-prone. Our second mechanism, the peer-prediction mechanism, shares the reward by considering two aspects: the evaluations received by the agents and their truth-telling scores. To compute these scores, this mechanism uses a strictly proper scoring rule. Under the assumption that agents are Bayesian decision-makers, we show that this mechanism is weakly budget-balanced, individually rational, and incentive-compatible. Further, we present approaches that guarantee the mechanism to be collusion-resistant and fair. Our last mechanism, the BTS mechanism, is the only one to elicit both evaluations and predictions from the agents. It considers the evaluations received by the agents and their truth-telling scores when sharing the reward. For computing the scores, it uses the Bayesian truth serum method, a powerful scoring method based on the surprisingly common criterion. Under the assumptions that agents are Bayesian decision-makers, and that the population of agents is sufficiently large so that a single evaluation cannot significantly affect the empirical distribution of evaluations, we show that this mechanism is incentive-compatible, budget-balanced, individually rational, and fair.

How should we divide a good or set of goods among a set of agents? There are various constraints that we can consider. We consider two particular constraints. The first is fairness - how can we find fair allocations? The second is truthfulness - what if we do not know agents valuations for the goods being allocated? What if these valuations need to be elicited, and agents will misreport their valuations if it is beneficial? Can we design procedures that elicit agents' true valuations while preserving the quality of the allocation? We consider truthful and fair resource allocation procedures through a computational lens. We first study fair division of a heterogeneous, divisible good, colloquially known as the cake cutting problem. We depart from the existing literature and assume that agents have restricted valuations that can be succinctly communicated. We consider the problems of welfare-maximization, expressiveness, and truthfulness in cake cutting under this model. In the second part of this dissertation we consider truthfulness in settings where payments can be used to incentivize agents to truthfully reveal their private information. A mechanism asks agents to report their private preference information and computes an allocation and payments based on these reports. The mechanism design problem is to find incentive compatible mechanisms which incentivize agents to truthfully reveal their private information and simultaneously compute allocations with desirable properties. The traditional approach to mechanism design specifies mechanisms by hand and proves that certain desirable properties are satisfied. This limits the design space to mechanisms that can be written down and analyzed. We take a computational approach, giving computational procedures that produce mechanisms with desirable properties. Our first contribution designs a procedure that modifies heuristic branch and bound search and makes it usable as the allocation algorithm in an incentive compatible mechanism. Our second contribution draws a novel connection between incentive compatible mechanisms and machine learning. We use this connection to learn payment rules to pair with provided allocation rules. Our payment rules are not exactly incentive compatibility, but they minimize a measure of how much agents can gain by misreporting. / Engineering and Applied Sciences

Το πρόβλημα της δίκαιης κατανομής είναι ένα πολύ σημαντικό πρόβλημα που έχει ανακύψει στον τομέα της επιστήμης των υπολογιστών και όχι μόνο. Κάποιες από τις μορφές που έχει εμφανιστεί είναι π.χ. στην κατανομή πόρων σε δίκτυα υπολογιστών, στο διακανονισμό συνόρων σε διεθνείς διαφωνίες, στο οικογενειακό δίκαιο και ως πρόβλημα της μείωσης των εκπομπών αερίων του θερμοκηπίου. Θεωρούμε προβλήματα αναθέσεων στα οποία ένα σύνολο αγαθών είτε αγγαρειών πρέπει να ανατεθεί σε κάποιους παίκτες. Κάθε παίκτης έχει μία συνάρτηση κέρδους (κόστους) που δείχνει πόσο εκτιμά κάθε αγαθό (αγγαρεία, αντίστοιχα) και το κέρδος (κόστος) του παίκτη για κάθε πιθανό σύνολο αντικειμένων προκύπτει αθροιστικά. Στόχος του προβλήματος είναι, φυσικά, η αποδοτικότητα και η δικαιοσύνη της ανάθεσης, περιορισμοί όμως, όπως η εγωιστική συμπεριφορά των παικτών οδηγούν σε πολύ ενδιαφέρουσες παραλλαγές του προβλήματος. Το πρώτο αποτέλεσμα της εργασίας προκύπτει από τη μελέτη του προβλήματος ανάθεσης ενός συνόλου αδιαίρετων αγαθών σε παίκτες όταν μας ενδιαφέρει να μην υπάρχει μεγάλη ζήλεια μεταξύ των παικτών. Αδιαίρετα λέγονται τα αντικείμενα που δεν μπορούν να κοπούν σε κομμάτια και πρέπει να ανατεθούν ακέραια σε κάποιο παίκτη, ενώ ζήλεια, διαισθητικά, είναι η προτίμηση που έχει κάποιος παίκτης για το σύνολο αγαθών που ανατέθηκαν σε κάποιον άλλον σε σχέση με τα αγαθά που ανατέθηκαν στον ίδιο. Όπως έχουμε αναφέρει, στην πράξη οι παίκτες έχουν εγωιστική συμπεριφορά, υπό την έννοια ότι προσπαθούν να μεγιστοποιήσουν το κέρδος τους. Για αυτό το λόγο, μπορεί να αναφέρουν εσφαλμένες συναρτήσεις κέρδους για να πετύχουν μία καλύτερη ανάθεση. Ως ειλικρινής χαρακτηρίζεται ένας μηχανισμός ανάθεσης ο οποίος εγγυάται ότι η ανάθεση των αντικειμένων βασίζεται στις σωστές συναρτήσεις κέρδους των παικτών. Υπό μία έννοια, ένας ειλικρινής μηχανισμός ανάθεσης αναγκάζει τους παίκτες να πουν την αλήθεια για τις συναρτήσεις κέρδους τους, ή αλλιώς, εγγυάται πως το κέρδος ενός παίκτη από την ανάθεση που βασίζεται σε εσφαλμένη συνάρτηση κέρδους δεν είναι μεγαλύτερο από το κέρδος που θα είχε αν η ανάθεση είχε βασιστεί στην πραγματική συνάρτηση κέρδους του, δεδομένου του ότι οι υπόλοιποι παίκτες λένε την αλήθεια. Παρουσιάζουμε μία απλή απόδειξη ότι ειλικρινείς ντετερμινιστικοί μηχανισμοί ανάθεσης δεν ελαχιστοποιούν τη ζήλεια, χαρακτηρίζοντας τέτοιους μηχανισμούς για δύο παίκτες και δύο αντικείμενα. Συγκεκριμένα, στην απόδειξη μας φαίνεται ότι για κάθε τέτοιο ειλικρινή μηχανισμό υπάρχουν στιγμιότυπα για τα οποία η ζήλεια σχεδόν μεγιστοποιείται. Επίσης, παρουσιάζουμε μία ανάλυση για ομοιόμορφα τυχαίες αναθέσεις οι οποίες είναι ειλικρινείς μηχανισμοί κατά μέσο όρο. Τα αποτελέσματα αυτά απλοποιούν και βελτιώνουν προηγούμενα αποτελέσματα των Lipton, Markakis, Mossel και Saberi. Συγκεκριμένα, δείχνουμε ότι η ζήλεια φράσσεται εκ των άνω από την ποσότητα O(a√(m ln n)) με μεγάλη πιθανότητα, όπου a είναι το μέγιστο κέρδος για κάθε αντικείμενο για κάθε παίκτη, n είναι ο αριθμός των παικτών και m ο αριθμός των αντικειμένων. Για την περίπτωση που το κέρδος κάθε παίκτη στο σύνολο των αντικειμένων είναι 1, το φράγμα γίνεται O(√(a ln n)). Στη συνέχεια μελετούμε την επίπτωση της δικαιοσύνης στην αποδοτικότητα των αναθέσεων. Στα ακόλουθα θα θεωρούμε ότι όντως είναι γνωστές οι πραγματικές συναρτήσεις κέρδους των παικτών. Επίσης, θεωρούμε και αναθέσεις αγγαρειών εκτός από αγαθών, καθώς επίσης και αναθέσεις διαιρετών εκτός από αδιαίρετων αντικειμένων. Ασχολούμαστε με τρείς διαφορετικές έννοιες δικαιοσύνης ανάμεσα στους παίκτες, συγκεκριμένα την αναλογικότητα, τη μη ύπαρξη ζήλειας και την ισοτιμία για αναθέσεις διαιρετών και αδιαίρετων αγαθών και αγγαρειών. Γενικά, μία ανάθεση αντικειμένων σε n παίκτες είναι αναλογική εάν σε κάθε παίκτη δίνεται η εντύπωση ότι παίρνει ένα σύνολο αντικειμένων “καλύτερο” από ποσοστό 1/n του συνόλου των αντικειμένων προς ανάθεση. Μία ανάθεση είναι χωρίς-ζήλεια εάν κάε παίκτης προτιμά όσα του έχουν ανατεθεί σε σύγκριση με το τι έχει πάρει οποιοσδήποτε άλλος παίκτης, ενώ μία ανάθεση είναι ισότιμη όταν όλοι οι παίκτες είναι εξ'ίσου ικανοποιημένοι με αυτά που τους έχουν ανατεθεί. Τέλος, μία ανάθεση είναι βέλτιστη εάν μεγιστοποιεί το κέρδος (ελαχιστοποιεί το κόστος, αντίστοιχα) του συνόλου των παικτών, δηλ. κάθε αντικείμενο ανατίθεται σε εκείνον τον παίκτη που το εκτιμά περισσότερο (του κοστίζει λιγότερο, αντίστοιχα). Παρουσιάζουμε μία σειρά αποτελεσμάτων για το κόστος της δικαιοσύνης όσον αφορά σε κάθε μία από τις τρείς έννοιες δικαιοσύνης που αναφέρθηκαν παραπάνω, πάνω σε διαιρετά και αδιαίρετα αντικείμενα αγαθών και αγγαρειών και ποσοτικοποιούμε την απώλεια αποδοτικότητας σε δίκαιες αναθέσεις σε σύγκριση με τις βέλτιστες. Παρουσιάζουμε άνω και κάτω φράγματα για κάθε περίπτωση, τα περισσότερα από τα οποία είτε συμπίπτουν είτε απέχουν κατά σταθερούς πολλαπλασιαστικούς παράγοντες. / Fair division (or fair allocation) dates back to the ancient times and has found applications such as border settlement in international disputes, greenhouse gas emissions reduction, allocation of mineral riches in the ocean bed, inheritance, divorces, etc. In the era of the Internet, it appears regularly in distributed resource allocation and cost sharing in communication networks. We consider allocation problems in which a set of goods or chores has to be allocated among several players. Each player has a utility (disutility) function indicating the happiness (regret) of the player if she is allocated the particular good (chore, respectively); this function is non-negative and additive. The objective of the problem is the efficiency and the fairness of the allocation, but restrictions like the selfish nature of the players lead to very interesting variants of the problem. Our first result stems from the study of the problem where a set of indivisible items has to be allocated to some players and where allocations in which no player envies the bundle of items allocated to the other players too much are considered. Indivisibility implies that an item cannot be broken into parts and must be allocated to a single player, and envy, intuitively implies the preference of a player for the bundle of items allocated to another player compared to that of the items allocated to her. As we stated above, in practice, players are usually selfish in the sense that they aim to increase their benefit, i.e., their total utility on the bundle of items the algorithm allocates to them. In order to do so, they may report false valuations of items to the algorithm (i.e., different than their true utilities). Truthful allocation functions guarantee that the allocation is based on the true utilities of the players. In a sense, a truthful allocation function motivates the players to be truthful, or, put differently, guarantees that the benefit obtained by a player when reporting false valuations on the items is not greater than the benefit she would have obtained by telling the truth, given that the rest of the players are truthful. We present a simple proof that deterministic truthful allocations do not minimize envy by characterizing the truthful mechanisms for two players and two items. Our proof actually shows that for any truthful allocation function, there are instances in which the envy is almost maximized. We also present an improved analysis of uniformly random allocations of m items over n players, which are truthful in expectation. We show that the envy is at most O(a√(mln n)) with high probability, where a is the maximum utility per item over all players and items. For the case where the sum of utilities of each player is 1, we prove a bound of O(√(aln n)). This improves the previous bound of O(√a n^{1/2+e}) for any e>0. We also study the impact of fairness on the efficiency of allocations. For this part of the paper, we assume that the true utility functions of the players are public knowledge. We consider both goods and chores, as well as divisible and indivisible items. Furthermore, we consider three different notions of fairness, namely proportionality, envy-freeness, and equitability. Informally, an allocation among n players is proportional if each player has the impression that she gets a better share than a fraction of 1/n of the items to be allocated. An allocation is envy-free if no player envies some other player, whereas an allocation is equitable when all players are equally happy with their shares. Finally, an allocation is optimal when it maximizes the total utility (minimizes the total disutility, respectively) of the set of players, i.e., each item is allocated to the player that values it the most (costs her the least). We present a series of results on the price of fairness under the three aforementioned different notions of fairness, for the cases of divisible and indivisible goods and chores, and quantify the efficiency loss in fair allocations compared to optimal ones. We present upper and lower bounds on each case, most of which are either exact or tight within constant factors.