Showing 1–11 of 11 results for author: Candogan, O

Achieving Fairness and Accuracy in Regressive Property Taxation

Authors: Ozan Candogan, Feiyu Han, Haihao Lu

Abstract: Regressivity in property taxation, or the disproportionate overassessment of lower-valued properties compared to higher-valued ones, results in an unfair taxation burden for Americans living in poverty. To address regressivity and enhance both the accuracy and fairness of property assessments, we introduce a scalable property valuation model called the $K$-segment model. Our study formulates a mat… ▽ More Regressivity in property taxation, or the disproportionate overassessment of lower-valued properties compared to higher-valued ones, results in an unfair taxation burden for Americans living in poverty. To address regressivity and enhance both the accuracy and fairness of property assessments, we introduce a scalable property valuation model called the $K$-segment model. Our study formulates a mathematical framework for the $K$-segment model, which divides a single model into $K$ segments and employs submodels for each segment. Smoothing methods are incorporated to balance and smooth the multiple submodels within the overall model. To assess the fairness of our proposed model, we introduce two innovative fairness measures for property evaluation and taxation, focusing on group-level fairness and extreme sales price portions where unfairness typically arises. Compared to the model employed currently in practice, our study demonstrates that the $K$-segment model effectively improves fairness based on the proposed measures. Furthermore, we investigate the accuracy--fairness trade-off in property assessments and illustrate how the $K$-segment model balances high accuracy with fairness for all properties. Our work uncovers the practical impacts of the $K$-segment models in addressing regressivity in property taxation, offering a tangible solution for policymakers and property owners. By implementing this model, we pave the way for a fairer taxation system, ensuring a more equitable distribution of tax burdens. △ Less

Submitted 10 December, 2023; originally announced December 2023.

Information Design for Spatial Resource Allocation

Authors: Ozan Candogan, Manxi Wu

Abstract: In this paper, we study platforms where resources and jobs are spatially distributed, and resources have the flexibility to strategically move to different locations for better payoffs. The price of the service at each location depends on the number of resources present and the market size, which is modeled as a random state. Our focus is on how the platform can utilize information about the under… ▽ More In this paper, we study platforms where resources and jobs are spatially distributed, and resources have the flexibility to strategically move to different locations for better payoffs. The price of the service at each location depends on the number of resources present and the market size, which is modeled as a random state. Our focus is on how the platform can utilize information about the underlying state to influence resource repositioning decisions and ultimately increase commission revenues. We establish that in many practically relevant settings a simple monotone partitional information disclosure policy is optimal. This policy reveals state realizations below a threshold and above a second (higher) threshold, and pools all states in between and maps them to a unique signal realization. We also provide algorithmic approaches for obtaining (near-)optimal information structures that are monotone partitional in general settings. △ Less

Submitted 16 July, 2023; originally announced July 2023.

Mobility Data in Operations: The Facility Location Problem

Authors: Ozan Candogan, Yiding Feng

Abstract: The recent large scale availability of mobility data, which captures individual mobility patterns, poses novel operational problems that are exciting and challenging. Motivated by this, we introduce and study a variant of the (cost-minimization) facility location problem where each individual is endowed with two locations (hereafter, her home and work locations), and the connection cost is the min… ▽ More The recent large scale availability of mobility data, which captures individual mobility patterns, poses novel operational problems that are exciting and challenging. Motivated by this, we introduce and study a variant of the (cost-minimization) facility location problem where each individual is endowed with two locations (hereafter, her home and work locations), and the connection cost is the minimum distance between any of her locations and its closest facility. We design a polynomial-time algorithm whose approximation ratio is at most 2.497. We complement this positive result by showing that the proposed algorithm is at least a 2.428-approximation, and there exists no polynomial-time algorithm with approximation ratio $2-ε$ under UG-hardness. We further extend our results and analysis to the model where each individual is endowed with K locations. Finally, we conduct numerical experiments over both synthetic data and US census data (for NYC, greater LA, greater DC, Research Triangle) and evaluate the performance of our algorithms. △ Less

Submitted 9 December, 2023; v1 submitted 15 January, 2023; originally announced January 2023.

Social Learning under Platform Influence: Consensus and Persistent Disagreement

Authors: Ozan Candogan, Nicole Immorlica, Bar Light, Jerry Anunrojwong

Abstract: Individuals increasingly rely on social networking platforms to form opinions. However, these platforms typically aim to maximize engagement, which may not align with social good. In this paper, we introduce an opinion dynamics model where agents are connected in a social network, and update their opinions based on their neighbors' opinions and on the content shown to them by the platform. We focu… ▽ More Individuals increasingly rely on social networking platforms to form opinions. However, these platforms typically aim to maximize engagement, which may not align with social good. In this paper, we introduce an opinion dynamics model where agents are connected in a social network, and update their opinions based on their neighbors' opinions and on the content shown to them by the platform. We focus on a stochastic block model with two blocks, where the initial opinions of the individuals in different blocks are different. We prove that for large and dense enough networks the trajectory of opinion dynamics in such networks can be approximated well by a simple two-agent system. The latter admits tractable analytical analysis, which we leverage to provide interesting insights into the platform's impact on the social learning outcome in our original two-block model. Specifically, by using our approximation result, we show that agents' opinions approximately converge to some limiting opinion, which is either: consensus, where all agents agree, or persistent disagreement, where agents' opinions differ. We find that when the platform is weak and there is a high number of connections between agents with different initial opinions, a consensus equilibrium is likely. In this case, even if a persistent disagreement equilibrium arises, the polarization in this equilibrium, i.e., the degree of disagreement, is low. When the platform is strong, a persistent disagreement equilibrium is likely and the equilibrium polarization is high. A moderate platform typically leads to a persistent disagreement equilibrium with moderate polarization. We analyze the effect of initial polarization on consensus and explore numerically various extensions including a three block stochastic model and a correlation between initial opinions and agents' connection probabilities. △ Less

Submitted 9 October, 2023; v1 submitted 24 February, 2022; originally announced February 2022.

Optimal Disclosure of Information to a Privately Informed Receiver

Authors: Ozan Candogan, Philipp Strack

Abstract: We study information design settings where the designer controls information about a state, and there are multiple agents interacting in a game who are privately informed about their types. Each agent's utility depends on all agents' types and actions, as well as (linearly) on the state. To optimally screen the agents, the designer first asks agents to report their types and then sends a private a… ▽ More We study information design settings where the designer controls information about a state, and there are multiple agents interacting in a game who are privately informed about their types. Each agent's utility depends on all agents' types and actions, as well as (linearly) on the state. To optimally screen the agents, the designer first asks agents to report their types and then sends a private action recommendation to each agent whose distribution depends on all reported types and the state. We show that there always exists an optimal mechanism which is laminar partitional. Such a mechanism partitions the state space for each type profile and recommends the same action profile for states that belong to the same partition element. Furthermore, the convex hulls of any two partition elements are such that either one contains the other or they have an empty intersection. In the single-agent case, each state is either perfectly revealed or lies in an interval in which the number of different signal realizations is at most the number of different types of the agent plus two. A similar result is established for the multi-agent case. We also highlight the value of screening: without screening the best achievable payoff could be as low as one over the number of types fraction of the optimal payoff. Along the way, we shed light on the solutions of optimization problems over distributions subject to a mean-preserving contraction constraint and additional side constraints, which might be of independent interest. △ Less

Submitted 28 January, 2022; v1 submitted 25 January, 2021; originally announced January 2021.

Convex Graph Invariant Relaxations For Graph Edit Distance

Authors: Utkan Onur Candogan, Venkat Chandrasekaran

Abstract: The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit dista… ▽ More The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex relaxations for obtaining lower bounds on graph edit distance. These relaxations can be tailored to the structural properties of the particular graphs via convex graph invariants. Specific examples that we highlight in this paper include constraints on the graph spectrum as well as (tractable approximations of) the stability number and the maximum-cut values of graphs. We prove under suitable conditions that our relaxations are tight (i.e., exactly compute the graph edit distance) when one of the graphs consists of few eigenvalues. We also validate the utility of our framework on synthetic problems as well as real applications involving molecular structure comparison problems in chemistry. △ Less

Submitted 17 April, 2019; originally announced April 2019.

Comments: 27 pages, 7 figures

MSC Class: 90C25; 90C22; 90C90; 90C35

Latent Agents in Networks: Estimation and Targeting

Authors: Baris Ata, Alexandre Belloni, Ozan Candogan

Abstract: We consider a network of agents. Associated with each agent are her covariate and outcome. Agents influence each other's outcomes according to a certain connection/influence structure. A subset of the agents participate on a platform, and hence, are observable to it. The rest are not observable to the platform and are called the latent agents. The platform does not know the influence structure of… ▽ More We consider a network of agents. Associated with each agent are her covariate and outcome. Agents influence each other's outcomes according to a certain connection/influence structure. A subset of the agents participate on a platform, and hence, are observable to it. The rest are not observable to the platform and are called the latent agents. The platform does not know the influence structure of the observable or the latent parts of the network. It only observes the data on past covariates and decisions of the observable agents. Observable agents influence each other both directly and indirectly through the influence they exert on the latent agents. We investigate how the platform can estimate the dependence of the observable agents' outcomes on their covariates, taking the latent agents into account. First, we show that this relationship can be succinctly captured by a matrix and provide an algorithm for estimating it under a suitable approximate sparsity condition using historical data of covariates and outcomes for the observable agents. We also obtain convergence rates for the proposed estimator despite the high dimensionality that allows more agents than observations. Second, we show that the approximate sparsity condition holds under the standard conditions used in the literature. Hence, our results apply to a large class of networks. Finally, we apply our results to two practical settings: targeted advertising and promotional pricing. We show that by using the available historical data with our estimator, it is possible to obtain asymptotically optimal advertising/pricing decisions, despite the presence of latent agents. △ Less

Submitted 26 January, 2022; v1 submitted 14 August, 2018; originally announced August 2018.

Comments: 106 pages

Finding Planted Subgraphs with Few Eigenvalues using the Schur-Horn Relaxation

Authors: Utkan Onur Candogan, Venkat Chandrasekaran

Abstract: Extracting structured subgraphs inside large graphs - often known as the planted subgraph problem - is a fundamental question that arises in a range of application domains. This problem is NP-hard in general, and as a result, significant efforts have been directed towards the development of tractable procedures that succeed on specific families of problem instances. We propose a new computationall… ▽ More Extracting structured subgraphs inside large graphs - often known as the planted subgraph problem - is a fundamental question that arises in a range of application domains. This problem is NP-hard in general, and as a result, significant efforts have been directed towards the development of tractable procedures that succeed on specific families of problem instances. We propose a new computationally efficient convex relaxation for solving the planted subgraph problem; our approach is based on tractable semidefinite descriptions of majorization inequalities on the spectrum of a symmetric matrix. This procedure is effective at finding planted subgraphs that consist of few distinct eigenvalues, and it generalizes previous convex relaxation techniques for finding planted cliques. Our analysis relies prominently on the notion of spectrally comonotone matrices, which are pairs of symmetric matrices that can be transformed to diagonal matrices with sorted diagonal entries upon conjugation by the same orthogonal matrix. △ Less

Submitted 12 May, 2016; originally announced May 2016.

Comments: 26 pages, 7 figures

Dynamics in Near-Potential Games

Authors: Ozan Candogan, Asuman Ozdaglar, Pablo A. Parrilo

Abstract: Except for special classes of games, there is no systematic framework for analyzing the dynamical properties of multi-agent strategic interactions. Potential games are one such special but restrictive class of games that allow for tractable dynamic analysis. Intuitively, games that are "close" to a potential game should share similar properties. In this paper, we formalize and develop this idea by… ▽ More Except for special classes of games, there is no systematic framework for analyzing the dynamical properties of multi-agent strategic interactions. Potential games are one such special but restrictive class of games that allow for tractable dynamic analysis. Intuitively, games that are "close" to a potential game should share similar properties. In this paper, we formalize and develop this idea by quantifying to what extent the dynamic features of potential games extend to "near-potential" games. We study convergence of three commonly studied classes of adaptive dynamics: discrete-time better/best response, logit response, and discrete-time fictitious play dynamics. For better/best response dynamics, we focus on the evolution of the sequence of pure strategy profiles and show that this sequence converges to a (pure) approximate equilibrium set, whose size is a function of the "distance" from a close potential game. We then study logit response dynamics and provide a characterization of the stationary distribution of this update rule in terms of the distance of the game from a close potential game and the corresponding potential function. We further show that the stochastically stable strategy profiles are pure approximate equilibria. Finally, we turn attention to fictitious play, and establish that the sequence of empirical frequencies of player actions converges to a neighborhood of (mixed) equilibria of the game, where the size of the neighborhood increases with distance of the game to a potential game. Thus, our results suggest that games that are close to a potential game inherit the dynamical properties of potential games. Since a close potential game to a given game can be found by solving a convex optimization problem, our approach also provides a systematic framework for studying convergence behavior of adaptive learning dynamics in arbitrary finite strategic form games. △ Less

Submitted 21 July, 2011; originally announced July 2011.

Comments: 42 pages, 8 figures

Journal ref: Games and Economic Behavior, Volume 82, November 2013, Pages 66-90

Optimal Pricing in Networks with Externalities

Authors: Ozan Candogan, Kostas Bimpikis, Asuman Ozdaglar

Abstract: We study the optimal pricing strategies of a monopolist selling a divisible good (service) to consumers that are embedded in a social network. A key feature of our model is that consumers experience a (positive) local network effect. In particular, each consumer's usage level depends directly on the usage of her neighbors in the social network structure. Thus, the monopolist's optimal pricing stra… ▽ More We study the optimal pricing strategies of a monopolist selling a divisible good (service) to consumers that are embedded in a social network. A key feature of our model is that consumers experience a (positive) local network effect. In particular, each consumer's usage level depends directly on the usage of her neighbors in the social network structure. Thus, the monopolist's optimal pricing strategy may involve offering discounts to certain agents, who have a central position in the underlying network. First, we consider a setting where the monopolist can offer individualized prices and derive an explicit characterization of the optimal price for each consumer as a function of her network position. In particular, we show that it is optimal for the monopolist to charge each agent a price that is proportional to her Bonacich centrality in the social network. In the second part of the paper, we discuss the optimal strategy of a monopolist that can only choose a single uniform price for the good and derive an algorithm polynomial in the number of agents to compute such a price. Thirdly, we assume that the monopolist can offer the good in two prices, full and discounted, and study the problem of determining which set of consumers should be given the discount. We show that the problem is NP-hard, however we provide an explicit characterization of the set of agents that should be offered the discounted price. Next, we describe an approximation algorithm for finding the optimal set of agents. We show that if the profit is nonnegative under any feasible price allocation, the algorithm guarantees at least 88% of the optimal profit. Finally, we highlight the value of network information by comparing the profits of a monopolist that does not take into account the network effects when choosing her pricing policy to those of a monopolist that uses this information optimally. △ Less

Submitted 28 January, 2011; originally announced January 2011.

Comments: 29 pages

Report number: LIDS pub# 2854

Flows and Decompositions of Games: Harmonic and Potential Games

Authors: Ozan Candogan, Ishai Menache, Asuman Ozdaglar, Pablo A. Parrilo

Abstract: In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games wit… ▽ More In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and study the structural and equilibrium properties of this new class of games. Intuitively, the potential component of a game captures interactions that can equivalently be represented as a common interest game, while the harmonic part represents the conflicts between the interests of the players. We make this intuition precise, by studying the properties of these two classes, and show that indeed they have quite distinct and remarkable characteristics. For instance, while finite potential games always have pure Nash equilibria, harmonic games generically never do. Moreover, we show that the nonstrategic component does not affect the equilibria of a game, but plays a fundamental role in their efficiency properties, thus decoupling the location of equilibria and their payoff-related properties. Exploiting the properties of the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the properties of potential and harmonic games to "nearby" games. We exemplify this point by showing that the set of approximate equilibria of an arbitrary game can be characterized through the equilibria of its projection onto the set of potential games. △ Less

Submitted 24 June, 2010; v1 submitted 13 May, 2010; originally announced May 2010.

Journal ref: Mathematics of Operations Research, Vol. 36, No. 3, pp. 474-503, 2011