Least manipulable Envy-free rules in economies with indivisibilities

We consider envy-free and budget-balanced allocation rules for problems where a number of indivisible objects and a fixed amount of money is allocated among a group of agents. In finite economies, we identify under classical preferences each agent’s maximal gain from manipulation. Using this result we find the envy-free and budget-balanced allocation rules which are least manipulable for each preference profile in terms of any agent’s maximal gain. If preferences are quasi-linear, then we can find an envy-free and budget-balanced allocation rule such that for any problem, the maximal utility gain from manipulation is equalized among all agents.     

Proportional pie-cutting

David Gale (Math Intell 15:48–52, 1993) was perhaps the first to suggest that there is a difference between cake and pie cutting. A cake can be viewed as a rectangle valued along its horizontal axis, and a pie as a disk valued along its circumference. We will use vertical, parallel cuts to divide a cake into pieces, and radial cuts from the center to divide a pie into wedge-shaped pieces. We restrict our attention to allocations that use the minimal number of cuts necessary to divide cakes or pies. In extending the definition of envy-freeness to unequal entitlements, we provide a counterexample to show that a cake cannot necessarily be divided into a proportional allocation of ratio p:1?p between two players where one player receives p of the cake according to her measure and the other receives 1?p of the cake according to his measure. In constrast, for pie, we prove that an efficient, envy-free, proportional allocation exists for two players. The former can be explained in terms of the Universal Chord Theorem, whereas the latter is proved by another result on chords. We provide procedures that induce two risk-averse players to reveal their preferences truthfully to achieve proportional allocations. We demonstrate that, in general, proportional, envy-free, and efficient allocations that use a minimal number of cuts may fail to exist for more than two players.     

Envy-free division of discrete cakes

We address the problem of existence of an envy-free distribution of pieces among two or more players in the cake-cutting setting with the minimum number of cuts. Our cakes are discrete in the sense that the playersʼ valuations are concentrated on atoms. These atoms are placed on an interval and no two players give positive value to atoms placed at the same position. We prove the existence of an envy-free allocation for any discrete cake and any number of players by resorting to Spernerʼs Lemma, a suitable triangulation, and moving-knife arguments. Our results also apply to pies, which are defined over circumferences instead of intervals.     

A moving-knife solution to the four-person envy-free cake-division problem

We present a moving-knife procedure, requiring only 11 cuts, that produces an envy-free allocation of a cake among four players and discuss possible extensions to five players.

     

Dynamic resource allocation in fuzzy coalitions: a game theoretic model

We introduce an efficient and dynamic resource allocation mechanism within the framework of a cooperative game with fuzzy coalitions (cooperative fuzzy game). A fuzzy coalition in a resource allocation problem can be so defined that membership grades of the players in it are proportional to the fractions of their total resources. We call any distribution of the resources possessed by the players, among a prescribed number of coalitions, a fuzzy coalition structure and every membership grade (equivalently fraction of the total resources), a resource investment. It is shown that this resource investment is influenced by the satisfaction of the players in regard to better performance under a cooperative setup. Our model is based on the real life situations, where possibly one or more players compromise on their resource investments in order to help forming coalitions.     

The positive consequence of strategic manipulation in indivisible good allocation

It is well known that any decision efficient, budget balanced, and envy-free mechanism for allocating a single object with transfers is vulnerable to manipulation. In this paper we examine whether the possible manipulations can have a serious impact on the outcome. Specifically, we examine which allocations are realized in the direct revelation game of any rule satisfying certain normative properties. For this class of rules we show that decision efficient, budget balanced, and envy-free allocations are the only ones realized through an ?-Nash equilibrium for any sufficiently small ? > 0.     

考虑边流量有限的网络路径博弈问题研究

考虑每条边有流量约束的网络路径博弈问题, 根据收益函数单调递增的特点分析其内在零和性质, 并建模为存在公共边的路径博弈模型。在寻找均衡解的过程中, 首先考虑非合作的情形, 在局中人风险中性的假设下, 给出了求Nash均衡流量分配的标号法并证明该均衡分配的唯一性。接着进一步考虑局中人合作的可能性, 给出模型求得所有局中人的整体最大收益, 并基于纳什谈判模型给出目标函数为凸函数的数学模型确定唯一收益分配方案。事实上, 该方案是对剩余价值的平均分配。最后给出一个算例, 验证本文理论和方法的可行性。关键词:流量约束; 均衡流量; 网络路径博弈; 收益分配     

Manipulation games in economies with indivisible goods

In this paper we study the strategic aspects of the No-Envy solution for the problem of allocating a finite set of indivisible goods among a group of agents when monetary compensations are possible. In the first part of the paper we consider the case where each agent receives, at most, one indivisible good. We prove that the set of equilibrium allocations of any direct revelation game associated with a subsolution of the No-Envy solution coincides with the set of envy-free allocations for the true preferences. Under manipulation all the subsolutions of the No-Envy solution are equivalent. In the second part of the paper, we allow each agent to receive more than one indivisible good. In this situation the above characterization does not hold any more. We prove that any Equal Income Walrasian allocation for the true preferences can be supported as an equilibrium allocation of any direct revelation game associated with subsolutions of the No-Envy solution, but also non-efficient allocations can be supported.     

On the probability of existence of pure equilibria in matrix games

We examine the probability that a randomly chosen matrix game admits pure equilibria and its behavior as the number of actions of the players or the number of players increases. We show that, for zero-sum games, the probability of having pure equilibria goes to zero as the number of actions goes to infinity, but it goes to a nonzero constant for a two-player game. For many-player games, if the number of players goes to infinity, the probability of existence of pure equilibria goes to zero even if the number of actions does not go to infinity.This research was supported in part by NSF Grant CCR-92-22734.     

Government formation in a two dimensional policy space

Given any allocation of parliament seats among parties, we characterize all the stable government configurations (supported by at least a majority of the parliament) in terms of winning coalitions and policy outcomes. We consider a two dimensional policy space and we assume that there are four parties that care mainly about holding office, and only instrumentally about policy. We find that for any distribution of seats in the parliament only two scenarios are possible: either there is a party that is a member of almost all equilibrium coalitions (dominant party scenario) or there is a party that is never a member of an equilibrium coalition (dominated party scenario). We characterize the key party for each possible scenario and we show that it is sufficient that the key party has intense preferences over one the issues to guarantee the formation of a stable government coalition.     

Relations between capacity utilization,minimal bin size and bin number

We consider the two-dimensional bin packing problem given a set of rectangular items, find the minimal number of rectangular bins needed to pack all items. Rotation of the items is not permitted. We show for any integer \({k} \ge 3\) that at most \({k}-1\) bins are needed to pack all items if every item fits into a bin and if the total area of items does not exceed \({k}/4\) -times the bin area. Moreover, this bound is tight. Furthermore, we show that only two bins are necessary to pack all items if the total area of items is not larger than the bin area, and if the height of each item is not larger than a third of the bin height and the width of every item does not exceed half of the bin width.     

Stochastic processes determined by a general success-breeds-success principle

The general “success-breeds-success” (SBS) principle as introduced in a previous paper extends the classical SBS principle in that the allocation of items over sources is determined by a more general rule than in the classical case. In this article we study the time evolution of the total number of sources, the average number of items per source and the number of sources with n items at time t, in the general SBS framework. Conditional as well as absolute expectations are calculated. Moreover, we investigate if and when these processes are martingales, supermartingales or submartingales. Stability results for the stochastic processes are obtained in the sense that we are able to determine when these processes converge. The article also studies the evolution of the expected average number of items per source.     

Congestion games with failures

We introduce a new class of games, congestion games with failures (CGFs), which allows for resource failures in congestion games. In a CGF, players share a common set of resources (service providers), where each service provider (SP) may fail with some known probability (that may be constant or depend on the congestion on the resource). For reliability reasons, a player may choose a subset of the SPs in order to try and perform his task. The cost of a player for utilizing any SP is a function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. We show that although CGFs do not, in general, admit a (generalized ordinal) potential function and the finite improvement property (and thus are not isomorphic to congestion games), they always possess a pure strategy Nash equilibrium. Moreover, every best reply dynamics converges to an equilibrium in any given CGF, and the SPs’ congestion experienced in different equilibria is (almost) unique. Furthermore, we provide an efficient procedure for computing a pure strategy equilibrium in CGFs and show that every best equilibrium (one minimizing the sum of the players’ disutilities) is semi-strong. Finally, for the subclass of symmetric CGFs we give a constructive characterization of best and worst equilibria.     

Location game on disjoint line segments

Two players are endowed with resources for setting up N locations on K line segments of identical length, with N > K ≥ 1. The players alternately choose these locations (possibly in batches of more than one in each round) in order to secure the area closer to their locations than that of their rival’s. The player with the highest secured area wins the game and otherwise the game ends in a tie. Earlier research has shown that, if an analogous game is played on disjoint circles, the second mover advantage is in place only if K = 1, while for K > 1 both players have a tying strategy. It was also shown that these results hold for line segments of identical length when rules of the game additionally require players to take exactly one location in the first round. In this paper we show that the second mover advantage is still in place for K ≥ 1 and 2K − 1 ≤ N, even if the additional restriction is dropped, while K ≤ N < 2K − 1 results in the first mover advantage. Our results allow us to draw conclusions about a natural variant of the game, where the resource mobility constraint is more stringent so that in each round each player chooses a single location and we show that the second mover advantage re-appears for K ≤ N < 2K − 1 if K is an even number. In all the cases the losing player has a strategy guaranteeing him arbitrarily small loss.     

Multi-item inventory control with full truckloads: A comparison of aggregate and individual order triggering

In this paper, we consider the stochastic joint replenishment problem in an environment where transportation costs are dominant and full truckloads or full container loads are required. One replenishment policy, taking into account capacity restrictions of the total order volume, is the so-called QS policy, where replenishment orders are placed to raise the individual inventory positions of all items to their order-up-to levels, whenever the aggregate inventory position drops below the reorder level. We first provide a method to compute the policy parameters of a QS policy such that item target service levels can be met, under the assumption that demand can be modeled as a compound renewal process. The approximation formulas are based on renewal theory and are tested in a simulation study which reveals good performance. Second, we compare the QS policy with a simple allocation policy where replenishment orders are triggered by the individual inventory positions of the items. At the moment when an individual inventory position drops below its item reorder level, a replenishment order is triggered and the total vehicle capacity is allocated to all items such that the expected elapsed time before the next replenishment order is maximized. In an extensive simulation study it is illustrated that the QS policy outperforms this allocation policy since it results in lower inventory levels for the same service level. Although both policies lead to similar performance if items are identical, it can differ substantially if the item characteristics vary.     

A note on a selfish bin packing problem

In this paper, we consider a selfish bin packing problem, where each item is a selfish player and wants to minimize its cost. In our new model, if there are k items packed in the same bin, then each item pays a cost 1/k, where k ≥ 1. First we find a Nash Equilibrium (NE) in time O(n log n) within a social cost at most 1.69103OPT + 3, where OPT is the social cost of an optimal packing; where n is the number of items or players; then we give tight bounds for the worst NE on the social cost; finally we show that any feasible packing can be converged to a Nash Equilibrium in O(n ²) steps without increasing the social cost.     

Highway games on weakly cyclic graphs

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera (2007) introduce highway problems and the corresponding cooperative cost games called highway games to address the problem of fair allocation of the construction costs in case the underlying graph is a tree. In this paper, we study the concavity and the balancedness of highway games on weakly cyclic graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. We show that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we prove that highway games on weakly cyclic graphs are balanced.     

On finding an envy-free Pareto-optimal division

This paper describes an algorithm to find an (α-)envy-free Pareto-optimal division in the case of a finite number of homogeneous infinitely divisible goods and linear utility functions. It is used to find an allocation in the classical cake division problem that is almost Pareto-optimal and α-envy-free.     

Distress among disaster-affected populations: delay in relief provision

Central to humanitarian logistics is the minimization of distress among impacted populations in the aftermath of a disaster. In this paper, we characterize two levels of distress, termed criticality and destitution, with respect to the delay provision of relief items. Delay in provision of a relief item will lead to destitution for a tolerable number of days, beyond which it will lead to criticality. We develop a mixed-integer goal program that quantifies these two metrics with respect to the number of days without provision of each of a set of relief items. The model determines the allocation of resources and the distribution of available relief items in a manner that minimizes criticality and destitution in affected population segments. The use of the model is demonstrated for the aftermath of a catastrophic earthquake in Istanbul, expected to occur by 2030.     

Fixed cost and resource allocation based on DEA cross-efficiency

In many managerial applications, situations frequently occur when a fixed cost is used in constructing the common platform of an organization, and needs to be shared by all related entities, or decision making units (DMUs). It is of vital importance to allocate such a cost across DMUs where there is competition for resources. Data envelopment analysis (DEA) has been successfully used in cost and resource allocation problems. Whether it is a cost or resource allocation issue, one needs to consider both the competitive and cooperative situation existing among DMUs in addition to maintaining or improving efficiency. The current paper uses the cross-efficiency concept in DEA to approach cost and resource allocation problems. Because DEA cross-efficiency uses the concept of peer appraisal, it is a very reasonable and appropriate mechanism for allocating a shared resource/cost. It is shown that our proposed iterative approach is always feasible, and ensures that all DMUs become efficient after the fixed cost is allocated as an additional input measure. The cross-efficiency DEA-based iterative method is further extended into a resource-allocation setting to achieve maximization in the aggregated output change by distributing available resources. Such allocations for fixed costs and resources are more acceptable to the players involved, because the allocation results are jointly determined by all DMUs rather than a specific one. The proposed approaches are demonstrated using an existing data set that has been applied in similar studies.