A pairwise-monotonic core selection for permutation games

In this article, a single-valued solution for permutation games is proposed. If we consider that each agent on the permutation game acts both as a buyer and as a seller, a related assignment game with the same reward matrix is defined. In this two-sided related market, the midpoint between the buyers-optimal core allocation and the sellers-optimal core allocation is considered. Then, each agent in the permutation game merges his payoff as a buyer and his payoff as a seller. This solution belongs to the core of the one-sided market and it is pairwise-monotonic.     

Manipulation via endowments in auctions with multiple goods

We study manipulation via endowments in a market in an auction setting with multiple goods. In the market, there are buyers whose valuations are their private information, and a seller whose set of endowments is her private information. A social planner, who wants to implement a socially desirable allocation, faces the seller’s manipulation via endowments, in addition to buyers’ manipulation of misreporting their valuations. We call a mechanism immune to the seller’s manipulation via endowments destruction-proof. In general, there exists no mechanism which is destruction-proof, together with strategy-proofness of the buyers, efficiency, and participation. Nevertheless, we find a restricted domain of the buyers’ valuation profiles satisfying a new condition called per-capita goods–buyer submodularity. We show that, in this domain, there exists a mechanism which is destruction-proof, together with the above properties. The restriction is likely to be met when each winner’s valuation is close to the next-highest valuation. We also provide a relation to monopoly theory, and argue that per-capita goods–buyer submodularity is independent of the standard elasticity argument.     

A condition for the strong regularity of matrices in the minimax algebra

Columns of a matrix A in the minimax algebra are called strongly linearly independent if for some b the system of equations A?x = b is uniquely solvable (cf. [3]). This paper presents a condition which is necessary and sufficient for the strong linear independence of columns of a given matrix in the minimax algebra based on a dense linearly ordered commutative group. In the case of square matrices an O(n³) method for checking this property as well as for finding at least one b such that A?x = b is uniquely solvable is derived. A connection with the classical assignment problem is formulated.     

A game theory approach in seller–buyer supply chain

In this paper, several seller–buyer supply chain models are proposed which incorporate both cost factors as well as elements of competition and cooperation between seller and buyer. We assume that unit marketing expenditure and unit price charged by the buyer influence the demand of the product being sold. The relationships between seller and buyer will be modeled by non-cooperative and cooperative games, respectively. The non-cooperative game is based on the Stackelberg strategy solution concept, where we consider separately the case when the seller is the leader (Seller-Stackelberg) and also when the buyer is the leader (Buyer-Stackelberg). Pareto efficient solutions will be provided for the cooperative game model. Numerical examples presented in this paper, including sensitivity analysis of some key parameters, will compare the results between different models considered.     

The valuation of options on capacity with cost and demand uncertainty

Options contracts can provide trading partners with enhanced flexibility to respond to uncertain market conditions and allow for superior capacity planning thanks to early information on future demand. We develop an analytical framework to value options on capacity for production of non-storable goods or dated services. The market consists of a sequence of contract and spot market. Reservations are made during the contract market session in period 0, where the buyer’s future demand, the seller’s future marginal costs as well as the future spot price are uncertain, the latter being impacted neither by the buyer nor the seller. During the spot market session in period 1, the buyer may execute his options or satisfy his entire or additional demand from a competing seller in the spot market. The seller allocates reserved capacity now being called and attempts to sell remaining capacity into the spot market. Analytical expressions for the buyer’s optimal reservation quantity and the seller’s tariff are derived, making explicit the risk-sharing benefits of options contracts. The combination of an options contract and a spot market is demonstrated to be Pareto improving as compared to alternative market schemes. An analysis of the determinants of the efficiency gain characterizes industries particularly suitable to the options approach.     

On competitiveness in uniform utility allocation markets

We call a market competitive if increasing the endowment of one buyer does not increase the equilibrium utility of another. We show that every competitive uniform utility allocation market is a submodular utility allocation market, answering a question of Jain and Vazirani [K. Jain, V.V. Vazirani, Eisenberg-Gale markets: Algorithms and structural properties, in: STOC, 2007]. Our proof proceeds via characterizing non-submodular fractionally sub-additive functions.     

CMV matrices with asymptotically constant coefficients. Szegö-Blaschke class, scattering theory

We develop a modern extended scattering theory for CMV matrices with asymptotically constant Verblunsky coefficients. We show that the traditional (Faddeev-Marchenko) condition is too restrictive to define the class of CMV matrices for which there exists a unique scattering representation. The main results are: (1) the class of twosided CMV matrices acting in l², whose spectral density satisfies the Szegö condition and whose point spectrum the Blaschke condition, corresponds precisely to the class where the scattering problem can be posed and solved. That is, to a given CMV matrix of this class, one can associate the scattering data and the FM space. The CMV matrix corresponds to the multiplication operator in this space, and the orthonormal basis in it (corresponding to the standard basis in l²) behaves asymptotically as the basis associated with the free system. (2) From the point of view of the scattering problem, the most natural class of CMV matrices is that one in which (a) the scattering data determine the matrix uniquely and (b) the associated Gelfand-Levitan-Marchenko transformation operators are bounded. Necessary and sufficient conditions for this class can be given in terms of an A₂ kind condition for the density of the absolutely continuous spectrum and a Carleson kind condition for the discrete spectrum. Similar conditions close to the optimal ones are given directly in terms of the scattering data.     

Realizability and inscribability for simplicial polytopes via nonlinear optimization

We consider the problem of screening where a seller puts up for sale an indivisible good, and a buyer with a valuation unknown to the seller wishes to acquire the good. We assume that the buyer valuations are represented as discrete types drawn from some distribution, which is also unknown to the seller. The seller is averse to possible mis-specification of types distribution, and considers the unknown type density as member of an ambiguity set and seeks an optimal pricing mechanism in a worst case sense. We specify four choices for the ambiguity set and derive the optimal mechanism in each case.     

Submatrices of non-tree-realizable distance matrices

We deal with distance matrices of real (this means, not necessarily integer) numbers. It is known that a distance matrix D of order n is tree-realizable if and only if all its principal submatrices of order 4 are tree-realizable. We discuss bounds for the number, denoted Q_i(D), of non-tree-realizable principal submatrices of order i ? 4 of a non-tree-realizable distance matrix D of order n?i, and we construct some distance matrices which meet extremal conditions on Q_i(D). Our starting point is a proof that a non-tree-realizable distance matrix of order 5 has at least two non-tree-realizable principal submatrices of order 4. Optimal realizations (by graphs with circuits) of distance matrices which are not tree-realizable are not yet as well known as optimal realizations which are trees. Using as starting point the optimal realization of the (arbitrary) distance matrix of order 4, we investigate optimal realizations of non-tree-realizable distance matrices with the minimum number of non-tree-realizable principal submatrices of order 4.     

Classification of Bott towers by matrix

A criterion for the classification of Bott towers is presented, i.e., two Bott towers B _*(A) and B _*(A′) are isomorphic if and only if the matrices A and A′ are equivalent. The equivalence relation is defined by two operations on matrices. And it is based on the observation that any Bott tower B _*(A) is uniquely determined by its structure matrix A, which is a strictly upper triangular integer matrix. The classification of Bott towers is closely related to the cohomological rigidity problem for both Bott towers and Bott manifolds.     

The sign matrix and the separation of matrix eigenvalues

The sign matrices uniquely associated with the matrices (M ? ζ_jI)², where ζ_j are the corners of a rectangle oriented at π/4 to the axes of a Cartesian coordinate system, may be used to compute the number of eigenvalues of the arbitrarily chosen matrix M which lie within the rectangle, and to determine the left and right invariant subspaces of M associated with these eigenvalues. This paper is concerned with the proof of this statement, and with the details of the computation of the required sign matrices.     

Designing win-win financial loan products for consumers and businesses

With the many possible designs that a financial company can offer to a consumer (eg terms, price, quality, features), a company can identify win-win products for both the consumer and the company. A key to identifying win-win products is to explicitly integrate the consumer's preferences for price and quality with the company's preferences for profit and market share. This paper builds a model that identifies the set of win-win products by integrating the preferences of buyer and seller. For any product not in this set, there is at least one product in the set that is better for both buyer and seller. The company's preferences are then used to select the optimal offer from the win-win set. Our development logically derives the results by focusing on financial products (eg loans, mortgages, credit cards) to consumers in the multitrillion dollar retail credit business.     

Clusters of point matrices

Along with classical orthogonal polynomials, we consider orthogonal polynomials of degree n ? 1 at n points. These arise naturally from interpolation polynomials. The name “point matrices” is justified by the fact that we deal, not with a class of similar or congruent matrices that play a key role in a linear space and are related to its bases, but with matrices with a fixed set of nodes (or points) x ₁, …, x _n . A certain matrix cluster corresponds to each set of nodes. It is stated that there exists a simple connection between eigenproblems of a Hankel matrix H and a symmetric Jacobi matrix T.     

The assignment game I: The core

The assignment game is a model for a two-sided market in which a product that comes in large, indivisible units (e.g., houses, cars, etc.) is exchanged for money, and in which each participant either supplies or demands exactly one unit. The units need not be alike, and the same unit may have different values to different participants. It is shown here that the outcomes in thecore of such a game — i.e., those that cannot be improved upon by any subset of players — are the solutions of a certain linear programming problem dual to the optimal assignment problem, and that these outcomes correspond exactly to the price-lists that competitively balance supply and demand. The geometric structure of the core is then described and interpreted in economic terms, with explicit attention given to the special case (familiar in the classic literature) in which there is no product differentiation — i.e., in which the units are interchangeable. Finally, a critique of the core solution reveals an insensitivity to some of the bargaining possibilities inherent in the situation, and indicates that further analysis would be desirable using other game-theoretic solution concepts.     

A matrix pencil approach computing the elementary divisors of a matrix: Numerical aspects and applications

In the present paper is presented a new matrix pencil-based numerical approach achieving the computation of the elementary divisors of a given matrixA ∈ C ^{n × n}. This computation is attained without performing similarity transformations and the whole procedure is based on the construction of the Piecewise Arithmetic Progression Sequence (PAPS) of the associated pencil λI _n - A of matrix A, for all the appropriate values of λ belonging to the set of eigenvalues of A. This technique produces a stable and accurate numerical algorithm working satisfactorily for matrices with a well defined eigenstructure. The whole technique can be applied for the computation of the first, second and Jordan canonical form of a given matrixA ∈ C ^{n × n}. The results are accurate for matrices possessing a well defined canonical form. In case of defective matrices, indications of the most appropriately computed canonical form are given.     

A double-sided multiunit combinatorial auction for substitutes: Theory and algorithms

Combinatorial exchanges have existed for a long time in securities markets. In these auctions buyers and sellers can place orders on combinations, or bundles of different securities. These orders are conjunctive: they are matched only if the full bundle is available. On business-to-business (B2B) exchanges, buyers have the choice to receive the same product with different attributes; for instance the same product can be produced by different sellers. A buyer indicates his preference by submitting a disjunctive order, where he specifies the quantity he wants of each particular good and what limit price he is willing to pay for each good, thus providing a subjective valuation of each attribute. Only the goods with the best prices will be traded. This article considers a doubled-sided multiunit combinatorial auction for substitutes, that is, a uniform price auction where buyers and sellers place both types of orders, conjunctive (AND orders) and disjunctive (XOR orders). We show that linear competitive prices exist. We also propose an algorithm to clear the market, which is particularly efficient when the number of traders is large, and the goods are divisible.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

Bargaining order and delays in multilateral bargaining with heterogeneous sellers

We consider a complete-information multilateral bargaining game in which a single buyer negotiates with two heterogeneous sellers selling perfect complementary units. While bilateral negotiations take place through a sequence of offers and counteroffers, the bargaining order is exogenously given. We solve for the conditions under which (a) the buyer prefers to negotiate with the lower-valuation seller first and (b) efficient (inefficient) outcomes emerge for the two bargaining orders. We find that the buyer prefers to negotiate with the lower-valuation seller first whenever the players are relatively impatient or the sellers are sufficiently heterogeneous. We show that there exists a unique efficient outcome when the buyer negotiates first with the lower-valuation seller and the sellers are sufficiently heterogeneous; however, significant delay in reaching agreements may arise when they are not. In case the buyer bargains with the higher-valuation seller first, an inefficient outcome is shown to exist even when players are extremely impatient.     

Buyer-seller exactness in the assignment game

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a “45^o-lattice” by means of the core of an assignment game can now be answered. Received: March 2002/Revised version: January 2003 RID="*" ID="*"  Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged RID="**" ID="**"  The authors thank the referees for their comments     

Buyer behavior adaptation based on a fuzzy logic controller and prediction techniques

The current form of Web provides numerous product resources available to users. Users can rely on intelligent agents for purchase actions. These actions are taken in specific environments such as Electronic Markets (EMs). In this paper, we study the interaction process between buyers and sellers and focus on the buyer side. Each buyer has the opportunity to interact with a number of sellers trying to buy the most appropriate products. This interaction can be modeled as a finite horizon Bargaining Game (BG). In this game, players have opposite goals concerning the product price. We adopt a number of techniques in the buyer side trying to give the appropriate level of efficiency in the buyer decision process. The buyer uses a prediction mechanism in combination with the use of Fuzzy Logic (FL) theory in order to be able to predict the upcoming seller proposal and, thus, understand the seller pricing policy. Based on this, he/she can adapt his/her behavior when trying to purchase products. The buyer adaptation mechanism produces the belief that the buyer has about the seller pricing policy and a parameter that indicates his/her own pricing policy which yields the buyer offers in the upcoming rounds. Moreover, the buyer is based on FL system that derives the appropriate actions at every round of the BG. Our results show that the combination of Fuzzy Logic (FL) with the above-mentioned techniques provides an efficient decision mechanism in the buyer side that in specific scenarios outperforms an optimal stopping model.