| 1. |
- Acemoglu, Daron, et al.
(författare)
-
Opinion fluctuations and disagreement in social networks
- 2013
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 38:1, s. 1-27
-
Tidskriftsartikel (refereegranskat)abstract
- We study a tractable opinion dynamics model that generates long-run disagreements and persistent opinion fluctuations. Our model involves an inhomogeneous stochastic gossip process of continuous opinion dynamics in a society consisting of two types of agents: (1) regular agents who update their beliefs according to information that they receive from their social neighbors and (2) stubborn agents who never update their opinions and might represent leaders, political parties, or media sources attempting to influence the beliefs in the rest of the society. When the society contains stubborn agents with different opinions, the belief dynamics never lead to a consensus (among the regular agents). Instead, beliefs in the society fail to converge almost surely, the belief profile keeps on fluctuating in an ergodic fashion, and it converges in law to a nondegenerate random vector. The structure of the graph describing the social network and the location of the stubborn agents within it shape the opinion dynamics. The expected belief vector is proved to evolve according to an ordinary differential equation coinciding with the Kolmogorov backward equation of a continuous-time Markov chain on the graph with absorbing states corresponding to the stubborn agents, and hence to converge to a harmonic vector, with every regular agent's value being the weighted average of its neighbors' values, and boundary conditions corresponding to the stubborn agents' beliefs. Expected cross products of the agents' beliefs allow for a similar characterization in terms of coupled Markov chains on the graph describing the social network. We prove that, in large-scale societies, which are highly fluid, meaning that the product of the mixing time of the Markov chain on the graph describing the social network and the relative size of the linkages to stubborn agents vanishes as the population size grows large, a condition of homogeneous influence emerges, whereby the stationary beliefs' marginal distributions of most of the regular agents have approximately equal first and second moments.
|
|
| 2. |
- Andersson, Tommy, et al.
(författare)
-
Gale's Fixed Tax for Exchanging Houses
- 2022
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 47:4, s. 3110-3128
-
Tidskriftsartikel (refereegranskat)abstract
- We consider taxation of exchanges among a set of agents in which each agent owns one object. Agents may have different valuations for the objects, and they need to pay taxes for exchanges. We show that, if a rule satisfies individual rationality, strategy-proofness, constrained efficiency, weak anonymity, and weak consistency, then it is either the no-trade rule or a fixed-tax core rule. For the latter rules, whenever any agent exchanges an object, the agent pays the same fixed tax (a lump sum payment that is identical for all agents) independently of which object the agent consumes. Gale’s top trading cycles algorithm finds the final assignment using the agents’ valuations adjusted with the fixed tax if the induced preferences are strict.
|
|
| 3. |
- Asmussen, Sören, et al.
(författare)
-
Loss rates for Lévy processes with two reflecting barriers
- 2007
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 32:2, s. 308-321
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- Let {Xt} be a Lévy process which is reflected at 0 and K>0. The reflected process {VtK} is constructed as VtK = V0K + Xt + Lt0 - LtK where{Lt0} and {LtK} are the local times at 0 and K, respectively. We consider the loss rate lK, defined by lK=E KL1K where E K is the expectation under the stationary measure K. The main result of the paper is the identification of lK in terms of K and the characteristic triplet of {Xt}. We also derive asymptotics of lK as K when EXt <0 and the Lévy measure of {Xt} is light-tailed.
|
|
| 4. |
- Bhaskar, U., et al.
(författare)
-
On the uniqueness of equilibrium in atomic splittable routing games
- 2015
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 40:3, s. 634-654
-
Tidskriftsartikel (refereegranskat)abstract
- In routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique. In routing games with atomic players with splittable flow, equilibria exist, but uniqueness of equilibria has been demonstrated only in limited cases: in two-terminal nearly parallel graphs, when all players control the same amount of flow, and when latency functions are polynomials of degree at most three. There are no known examples of multiple equilibria in these games. In this work, we show that in contrast to routing games with infinitesimal players, atomic splittable routing games admit multiple equilibria. We demonstrate this multiplicity via two specific examples. In addition, we show that our examples are topologically minimal by giving a complete characterization of the class of network topologies for which multiple equilibria exist. Our proofs and examples are based on a novel characterization of these topologies in terms of sets of circulations.
|
|
| 5. |
- De Angelis, Tiziano, et al.
(författare)
-
Dynkin Games with Incomplete and Asymmetric Information
- 2022
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 47:1, s. 560-586
-
Tidskriftsartikel (refereegranskat)abstract
- We study the value and the optimal strategies for a two-player zero-sum optimal stopping game with incomplete and asymmetric information. In our Bayesian setup, the drift of the underlying diffusion process is unknown to one player (incomplete information feature), but known to the other one (asymmetric information feature). We formulate the problem and reduce it to a fully Markovian setup where the uninformed player optimises over stopping times and the informed one uses randomised stopping times in order to hide their informational advantage. Then we provide a general verification result that allows us to find the value of the game and players' optimal strategies by solving suitable quasi-variational inequalities with some nonstandard constraints. Finally, we study an example with linear payoffs, in which an explicit solution of the corresponding quasi-variational inequalities can be obtained.
|
|
| 6. |
- Djehiche, Boualem, 1962-, et al.
(författare)
-
Infinite Horizon Stochastic Impulse Control with Delay and Random Coefficients
- 2022
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 47:1, s. 665-689
-
Tidskriftsartikel (refereegranskat)abstract
- We study a class of infinite horizon impulse control problems with execution delay when the dynamics of the system is described by a general stochastic process adapted to the Brownian filtration. The problem is solved by means of probabilistic tools relying on the notion of Snell envelope and infinite horizon reflected backward stochastic differential equations. This allows us to establish the existence of an optimal strategy over all admissible strategies.
|
|
| 7. |
- Haasler, Isabel, et al.
(författare)
-
Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport
- 2024
-
Ingår i: Mathematics of Operations Research. - 0364-765X .- 1526-5471. ; 49:2, s. 986-1011
-
Tidskriftsartikel (refereegranskat)abstract
- In this work, we develop a new framework for dynamic network flow pro-blems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are asso-ciated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropy -regularized optimal transport problems. In particular, the graph structure is utilized to efficiently compute the projections needed in the corresponding Sinkhorn iterations, and we arrive at a scheme that is both highly computationally efficient and easy to implement. To illustrate the performance of our algorithm, we compare it with a state-of-the-art linear programming (LP) solver. We achieve good approximations to the solution at least one order of magnitude faster than the LP solver. Finally, we showcase the methodology on a traffic routing problem with a large number of commodities.
|
|
| 8. |
- Haasler, Isabel, et al.
(författare)
-
Scalable Computation of Dynamic Flow Problems via Multimarginal Graph-Structured Optimal Transport
- 2024
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 49:2, s. 986-1011
-
Tidskriftsartikel (refereegranskat)abstract
- In this work, we develop a new framework for dynamic network flow problems based on optimal transport theory. We show that the dynamic multicommodity minimum-cost network flow problem can be formulated as a multimarginal optimal transport problem, where the cost function and the constraints on the marginals are associated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropy regularized optimal transport problems. In particular, the graph structure is utilized to efficiently compute the projections needed in the corresponding Sinkhorn iterations, and we arrive at a scheme that is both highly computationally efficient and easy to implement. To illustrate the performance of our algorithm, we compare it with a state-of-the-art linear programming (LP) solver. We achieve good approximations to the solution at least one order of magnitude faster than the LP solver. Finally, we showcase the methodology on a traffic routing problem with a large number of commodities.
|
|
| 9. |
- Huang, Chien-Chung, 1976, et al.
(författare)
-
New algorithms for maximum weight matching and a decomposition theorem
- 2017
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 42:2, s. 411-426
-
Tidskriftsartikel (refereegranskat)abstract
- We revisit the classical maximum weight matching problem in general graphs with nonnegative integral edge weights. We present an algorithm that operates by decomposing the problem into W unweighted versions of the problem, where W is the largest edge weight. Our algorithm has running time as good as the current fastest algorithms for the maximum weight matching problem when W is small. One of the highlights of our algorithm is that it also produces an integral optimal dual solution; thus our algorithm also returns an integral certificate corresponding to the maximum weight matching that was computed. Our algorithm yields a new proof to the total dual integrality of Edmonds' matching polytope and it also gives rise to a decomposition theorem for the maximum weight of a matching in terms of the maximum size of a matching in certain subgraphs. We also consider the maximum weight capacitated b-matching problem in bipartite graphs with nonnegative integral edge weights and show that it can also be decomposed into W unweighted versions of the problem, where W is the largest edge weight. Our second algorithm is competitive with known algorithms when W is small. © 2016 INFORMS.
|
|
| 10. |
- Joswig, Michael, et al.
(författare)
-
Parametric Shortest-Path Algorithms via Tropical Geometry
- 2022
-
Ingår i: Mathematics of Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0364-765X .- 1526-5471. ; 47:3, s. 2065-2081
-
Tidskriftsartikel (refereegranskat)abstract
- We study parameterized versions of classical algorithms for computing shortest-path trees. This is most easily expressed in terms of tropical geometry. Applications include shortest paths in traffic networks with variable link travel times.
|
|
