Information market games

In this paper information markets with perfect patent protection and only one initial owner of the information are studied by means of cooperative game theory. To each information market of this type a cooperative game with sidepayments is constructed. These cooperative games are called information (market) games. The set of all information games with fixed player set is a cone in the set of all cooperative games with the same player set. Necessary and sufficient conditions are given in order that a cooperative game is an information game. The core of this kind of games is not empty and is also the minimal subsolution of the game. The core is the image of an (n-1)-dimensional hypercube under an affine transformation, (= hyperparallellopiped), the nucleolus and -value coincide with the center of the core. The Shapley value is computed and may lie inside or outside the core. The Shapley value coincides with the nucleolus and the -value if and only if the information game is convex. In this case the core is also a stable set.     

Bankruptcy games

Bankruptcy problems are considered from a game theoretic point of view. Solution concepts from cooperative game theory are studied for bankruptcy games. A necessary and sufficient condition for a division rule for bankruptcy problems to be a game theoretic rule is given. A new division rule which is an adjustment of the proportional rule is given. This rule coincides with theT-value for bankruptcy games. Properties of the new rule are treated and a set of characterizing properties is given.

---

Zusammenfassung In dieser Arbeit werden Bankrottprobleme von spieltheoretischer Warte aus behandelt; insbesondere werden Lösungskonzepte der kooperativen Spieltheorie für Bankrottspiele untersucht. Eine notwendige und hinreichende Bedingung wird angegeben dafür, Daß eine Aufteilungsregel für Bankrottprobleme spieltheoretischer Natur ist. Ferner wird eine neue Aufteilungsregel angegeben, welche eine passende Modellierung der Proportionalitätsregel ist. Diese Regel fällt mit dem-Wert für Bankrottspiele zusammen. Schließlich werden Eigenschaften dieser neuen Regel untersucht und eine Axiomatisierung angegeben.

     

Algorithms for non-convexS n -games

We considerS-games in which the setS is the parametric curve{(p ₁ (t),, p _n(t)): t [0, 1]} and thep _i(t) are real polynomials. These games will be referred to asS _n -games. Two iterative algorithms are given in the case ofn = 2. One gives linear convergence to an optimal of player I, and the other gives monotone convergence. In the case of arbitraryn we give an algorithm of the cutting plane family converging to the value. The principal features of this algorithm are that the hyperplanes arise intrinsically as tangents to an associated concave function which is not in general differentiable, and the linear subproblems arise as matrix games. Because of the latter property inactive constraints are in principle automatically dropped. We give a game theoretic convergence proof. This algorithm may be used multiply for bounding optimals of player I.     

On the rate of taxation in a cooperative bin packing game

We investigate a cooperative game with two types of players envolved: Every player of the first type owns a unit size bin, and every player of the second type owns an item of size at most one. The value of a coalition of players is defined to be the maximum overall size of packed items over all packings of the items owned by the coalition into the bins owned by the coalition.We prove that for=1/3 this cooperative bin packing game is-balanced in the taxation model of Faigle and Kern (1993).This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.     

A note on the 5-person traveling salesman game

LetN=1,2,...,n be a set of customers andG=(N {0},E) an undirected connected graph with non-negative edge lengths. 0 is the home location of a salesman who visits the customers inN. Each subset can invite the salesman to visit its members only. The costc(S) of coalitionS is the length of a shortest tour that starts in 0, visits each customer inS at least once and returns to 0. The cooperative cost game defined in this way is called a (symmetric) traveling salesman game (TSG).The core of a TSG can be empty when ¦N¦ 6 and it was proved that it always has a non-empty core when ¦N¦ 4. In this note we shall prove that a TSG always has a non-empty core when ¦N¦=5.     

Values and potential of games with cooperation structure

Games with cooperation structure are cooperative games with a family offeasible coalitions, that describes which coalitions can negotiate in the game. We study a model ofcooperation structure and the corresponding restricted game, in which the feasible coalitions are those belonging to apartition system. First, we study a recursive procedure for computing the Hart and Mas-Colell potential of these games and we develop the relation between the dividends of Harsanyi in the restricted game and the worths in the original game. The properties ofpartition convex geometries are used to obtain formulas for theShapley andBanzhaf values of the players in the restricted game in terms of the original gamev. Finally, we consider the Owen multilinear extension for the restricted game.The author is grateful to Paul Edelman, Ulrich Faigle and the referees for their comments and suggestions. The proof of Theorem 1 was proposed by the associate editor's referee.     

Security investment and information sharing in the market of complementary firms: impact of complementarity degree and industry size

We study a differential game of information security investment and information sharing in a market consisting of n complementary firms. Two game approaches, the non-cooperative game and the totally cooperative game, are employed to investigate the steady state strategy of each firm. Under certain conditions, a unique steady state can be obtained for both games. We find that the steady state security investment and information sharing level are not always less in the non-cooperative game than that in the totally cooperative game. In addition, some theoretical analyses are made on the impacts of the complementarity degree and industry size on firms’ steady state strategies for both games. Finally, some numerical experiments are conducted to give some insights related to the instantaneous profit in the steady state. It can be found that a firm will obtain more instantaneous profit in the steady state of the totally cooperative game than that of the non-cooperative game, which emphasizes the importance of coordinating strategies. The effects of the complementarity degree and industry size on the instantaneous profits in the steady state are also obtained through the numerical experiment results.     

Utilization of mathematical programming for public systems: An application to effective formation of integrated regional information networks

This paper concerns a methodological reflection on the multiobjective approach to public systems which involve group decision processes. Particular attention is given to an integrated program of regional systems which include value trade-offs between multiple objectives. Our intention is to combine the judgmental processes with the optimization processes in the soft public systems. A two-layer approach is applied. At the first layer, each regional program is formulated in mathematical programming based on a utility assessment with different regional characteristics. Each subsystem independently reflects its particular concern as a single agent. The dual optimal solutions obtained for each subsystem are treated as an index, or the theoretical prices, representing the value trade-offs among the multiple objectives. At the second layer, an effective formation of interregional cooperation for compromising the conflicting regional interests is examined. Ann-person cooperative game in the characteristic function form is used to evaluate the effectiveness of the cooperation. The characteristic function for the game is derived on the incremental value of the regional benefit after the formation of a cooperation. The nucleolus and the augmented nucleolus as the solution concepts of the cooperative game are used for indicating the effectiveness of the cooperation. Finally using alternative criteria, the results in assessing the best decisions are examined comparatively.     

A game-theoretic analysis of information security investment for multiple firms in a network

The application of Internet of Things promotes the cooperation among firms, and it also introduces some information security issues. Due to the vulnerability of the communication network, firms need to invest in information security technologies to protect their confidential information. In this paper, considering the multiple-step propagation of a security breach in a fully connected network, an information security investment game among n firms is investigated. We make meticulous theoretic and experimental analyses on both the Nash equilibrium solution and the optimal solution. The results show that a larger network size (n) or a larger one-step propagation probability (q) has a negative effect on the Nash equilibrium investment. The optimal investment does not necessarily increase in n or q, and its variation trend depends on the concrete conditions. A compensation mechanism is proposed to encourage firms to coordinate their strategies and invest a higher amount equal to the optimal investment when they make decisions individually. At last, our model is extended by considering another direct breach probability function and another network structure, respectively. We find that a higher connection density of the network will result in a greater expected cost for each firm.     

The capture time of grids

We consider the game of cops and robber played on the Cartesian product of two trees. Assuming the players play perfectly, it is shown that if there are two cops in the game, then the length of the game (known as the 2-capture time of the graph) is equal to half the diameter of the graph. In particular, the 2-capture time of the m×n grid is proved to be .     

A game locating a needle in a square haystack

The following hider-seeker zero-sum game is considered. The hider hides a needle of length , in the closed unit square, and the seeker tries to locate it by shooting in a straight line across the square. The payoff to the seeker is 1 if he hits the needle and 0 otherwise.A solution of the game is obtained when or whena lies in either of the intervals and ; in addition, it is shown that, whenn is a positive integer anda=1/n, the value of the game is 1/2n. The properties of the solutions are in marked contrast to those for the analogous game over the closed unit disc, which the authors solved in a previous paper, and suggest that a complete solution may well be difficult. It is also shown that every member of a whole class of haystack games has a value.     

Regular simplices, symmetric polynomials and the mean value property

LetP be ann-dimensional regular simplex in ℝⁿ centered at the origin, and let P(k) be thek-skeleton ofP fork = 0, 1,…,n. Then the set of all continuous functions in ℝⁿ satisfying the mean value property with respect to P(k) forms a finite-dimensional linear space of harmonic polynomials. In this paper the function space is explicitly determined by group theoretic and combinatorial arguments for symmetric polynomials.     

Single-suit two-person card play II. Dominance

This paper studies a two-person constant sum perfect information game, the End Play Game, arising from an abstraction of end play in bridge. This game was described by Emanuel Lasker who called it whistette. The game uses a deck of cards consisting of a single totally ordered suit of 2n cards. The deck is divided into two hands A and B of n cards each, held by players Left and Right, and one player is designated as having the lead. The player on lead chooses one of his cards, and the other player after seeing this card selects one of his own to play. The player with the higher card wins a trick and obtains the lead. The cards in the trick are removed from each hand, and play then continues until all cards are exhausted. Each player strives to maximize his trick total, and the value of the game to each player is the number of tricks he takes. The strategy of this game seems to be quite complicated, despite its simple appearance. This paper studies partial orderings on hands. One partial order recognizes regularities in the value function that persist when extra cards are added to hands. A pair of hands (A ^* , B ^* ) dominates a pair of hands (A, B) for Left, if for any set of extra cards (C ₁, C ₂) added to the deck such that A B (which equals A ^* B ^* ) is a block of consecutive cards in the expanded deck A B {C ₁ , C ₂} the value of (A C ₁, B C ₂) to Left always is at least as much as the value to Left of (A ^* C ₁, B ^* C ₂) both when Left has the lead in both games and when Right has the lead in both games. The main result is that ({4, 1}, {3, 2}) dominates ({3, 2}, {4, 1}). Note that with just four cards the hands {4, 1} and {3, 2} are of identical value — they both take one trick independent of the lead or how the hands are played. The dominance result shows that {4, 1} is preferable to {3, 2} when other cards are present. We show that the dominance relation gives a partial order that is not a total order on hands of 3 or more cards. We also study the total point count ordering, which gives a rough estimate for the value of a hand. We derive upper and lower bounds for the value of a hand with given point count.     

Invariant equations defining coincident root loci

Let F(x) = xⁿ+₁ x^n-1+₂ x^n-2+ ··· +_n be a polynomial with complex coefficients, and suppose we are given a partition (₁,...,_r) of n. It is a classical problem to determine explicit algebraic conditions on the _i so that F may have roots with multiplicities ₁,...,_r. We give an invariant theoretic solution to this problem, to wit, we exhibit a set of covariants of F whose vanishing is a necessary and sufficient condition. The construction of such covariants is combinatorial, and involves associating a set of graphs on n vertices (called decisive graphs) to each .Received: 28 September 2003     

Games of Chains and Cutsets in the Boolean Lattice II

Let 2 ^[n] denote the poset of all subsets of [n]={1,2,...,n} ordered by inclusion. Following Gutterman and Shahriari (Order 14, 1998, 321–325) we consider a game G _n (a,b,c). This is a game for two players. First, Player I constructs a independent maximal chains in 2 ^[n]. Player II will extend the collection to a+b independent maximal chains by finding another b independent maximal chains in 2 ^[n]. Finally, Player I will attempt to extend the collection further to a+b+c such chains. The last Player who is able to complete her move wins. In this paper, we complete the analysis of G _n (a,b,c) by considering its most difficult instance: when c=2 and a+b+2=n. We prove, the rather surprising result, that, for n7, Player I wins G _n (a,n–a–2,2) if and only if a3. As a consequence we get results about extending collections of independent maximal chains, and about cutsets (collections of subsets that intersect every maximal chain) of minimum possible width (the size of largest anti-chain).     

Asymptotic near optimality of the bisection method

Summary We seek a approximation to a zero of an infinitely differentiable functionf: [0, 1] such thatf(0)0 andf(1)0. It is known that the error of the bisection method usingn function evaluations is 2^–(n+1). If the information used are function values, then it is known that bisection information and the bisection algorithm are optimal. Traub and Woniakowski conjectured in [5] that the bisection information and algorithm are optimal even if far more general information is permitted. They permit adaptive (sequential) evaluations of arbitrary linear functionals and arbitrary transformations of this information as algorithms. This conjecture was established in [2]. That is forn fixed, the bisection information and algorithm are optimal in the worst case setting. Thus nothing is lost by restricting oneself to function values.One may then ask whether bisection is nearly optimal in theasymptotic worst case sense, that is,possesses asymptotically nearly the best rate of convergence. Methods converging fast asymptotically, like Newton or secant type, are of course, widely used in scientific computation. We prove that the answer to this question is positive for the classF of functions having zeros ofinfinite multiplicity and information consisting of evaluations of continuous linear functionals. Assuming that everyf inF has zeroes withbounded multiplicity, there are known hybrid methods which have at least quadratic rate of convergence asn tends to infinity, see e.g., Brent [1], Traub [4] and Sect. 1.