Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNetworks of Complements
55
0
0.0
(
0
)
Added by
Liad Blumrosen
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider a network of sellers, each selling a single product, where the graph structure represents pair-wise complementarities between products. We study how the network structure affects revenue and social welfare of equilibria of the pricing game between the sellers. We prove positive and negative results, both of Price of Anarchy and of Price of Stability type, for special families of graphs (paths, cycles) as well as more general ones (trees, graphs). We describe best-reply dynamics that converge to non-trivial equilibrium in several families of graphs, and we use these dynamics to prove the existence of approximately-efficient equilibria.
rate research
Read More
We consider a revenue-maximizing seller with $m$ heterogeneous items and a single buyer whose valuation $v$ for the items may exhibit both substitutes (i.e., for some $S, T$, $v(S cup T) < v(S) + v(T)$) and complements (i.e., for some $S, T$, $v(S cup T) > v(S) + v(T)$). We show that the mechanism first proposed by Babaioff et al. [2014] - the better of selling the items separately and bundling them together - guarantees a $Theta(d)$ fraction of the optimal revenue, where $d$ is a measure on the degree of complementarity. Note that this is the first approximately optimal mechanism for a buyer whose valuation exhibits any kind of complementarity, and extends the work of Rubinstein and Weinberg [2015], which proved that the same simple mechanisms achieve a constant factor approximation when buyer valuations are subadditive, the most general class of complement-free valuations. Our proof is enabled by the recent duality framework developed in Cai et al. [2016], which we use to obtain a bound on the optimal revenue in this setting. Our main technical contributions are specialized to handle the intricacies of settings with complements, and include an algorithm for partitioning edges in a hypergraph. Even nailing down the right model and notion of degree of complementarity to obtain meaningful results is of interest, as the natural extensions of previous definitions provably fail.
Let $Omega$ be the complement of a connected, essential hyperplane arrangement. We prove that every dominant endomorphism of $Omega$ extends to an endomorphism of the tropical compactification $X$ of $Omega$ associated to the Bergman fan structure on the tropicalization of $Omega$. This generalizes a previous result by Remy, Thuillier and the second author which states that every automorphism of Drinfelds half-space over a finite field $mathbb{F}_q$ extends to an automorphism of the successive blow-up of projective space at all $mathbb{F}_q$-rational linear subspaces. This successive blow-up is in fact the minimal wonderful compactification by de Concini and Procesi, which coincides with $X$ by results of Feichtner and Sturmfels. Whereas the previous proof is based on Berkovich analytic geometry over the trivially valued finite ground field, the generalization discussed in the present paper relies on matroids and tropical geometry.
Hempel has shown that the fundamental groups of knot complements are residually finite. This implies that every nontrivial knot must have a finite-sheeted, noncyclic cover. We give an explicit bound, $Phi (c)$, such that if $K$ is a nontrivial knot in the three-sphere with a diagram with $c$ crossings and a particularly simple JSJ decomposition then the complement of $K$ has a finite-sheeted, noncyclic cover with at most $Phi (c)$ sheets.
Supply chains are the backbone of the global economy. Disruptions to them can be costly. Centrally managed supply chains invest in ensuring their resilience. Decentralized supply chains, however, must rely upon the self-interest of their individual components to maintain the resilience of the entire chain. We examine the incentives that independent self-interested agents have in forming a resilient supply chain network in the face of production disruptions and competition. In our model, competing suppliers are subject to yield uncertainty (they deliver less than ordered) and congestion (lead time uncertainty or, soft supply caps). Competing retailers must decide which suppliers to link to based on both price and reliability. In the presence of yield uncertainty only, the resulting supply chain networks are sparse. Retailers concentrate their links on a single supplier, counter to the idea that they should mitigate yield uncertainty by diversifying their supply base. This happens because retailers benefit from supply variance. It suggests that competition will amplify output uncertainty. When congestion is included as well, the resulting networks are denser and resemble the bipartite expander graphs that have been proposed in the supply chain literature, thereby, providing the first example of endogenous formation of resilient supply chain networks, without resilience being explicitly encoded in payoffs. Finally, we show that a suppliers investments in improved yield can make it worse off. This happens because high production output saturates the market, which, in turn lowers prices and profits for participants.
We consider dynamic equilibria for flows over time under the fluid queuing model. In this model, queues on the links of a network take care of flow propagation. Flow enters the network at a single source and leaves at a single sink. In a dynamic equilibrium, every infinitesimally small flow particle reaches the sink as early as possible given the pattern of the rest of the flow. While this model has been examined for many decades, progress has been relatively recent. In particular, the derivatives of dynamic equilibria have been characterized as thin flows with resetting, which allowed for more structural results. Our two main results are based on the formulation of thin flows with resetting as linear complementarity problem and its analysis. We present a constructive proof of existence for dynamic equilibria if the inflow rate is right-monotone. The complexity of computing thin flows with resetting, which occurs as a subproblem in this method, is still open. We settle it for the class of two-terminal series-parallel networks by giving a recursive algorithm that solves the problem for all flow values simultaneously in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
