Search Results

Documents authored by Chen, Yi

Found 6 Possible Name Variants:

Chen, Yi

Document
DOI: 10.4230/DagSemProc.07191.3
An XML Framework for Integrating Continuous Queries, Composite Event Detection, and Database Condition Monitoring for Multiple Data Streams

Authors: Susan Urban, Suzanne Dietrich, and Yi Chen

Published in: Dagstuhl Seminar Proceedings, Volume 7191, Event Processing (2007)

Abstract
With advancements in technology over the last ten years, data management issues have evolved from a stored persistent form to also include streaming data generated from sensors and other software monitoring tools. Furthermore, distributed, event-based systems are becoming more prevalent, with a need to develop applications that can dynamically respond to information extracted from data streams. This research is investigating the integration of stream processing and event processing techniques, with expressive filtering capabilities that include queries over persistent databases to provide application context to the filtering process. Distributed Event Processing Agents (DEPAs) continuously filter events from multiple data streams of different formats that provide XML views. Composite events for data streams are expressed using the Composite Event Detection Language (CEDL) and mapped to Composite XQuery (CXQ) for implementation. CXQ is a language that extends XQuery with features from CEDL, including operators for expressing sequence, disjunction, conjunction, repetition, aggregation, and time windows for events. Continuous queries and composite event filters are integrated with techniques for materialized view maintenance and incremental evaluation in condition monitoring to provide efficient ways of enhancing stream filters with database queries. The filtering and event detection load is distributed among multiple DEPAs, with CXQ expressions decomposed to allocate subcomponents of the expression to DEPAs that efficiently communicate in the global detection of composite events. A unique aspect of our research is that it extends XQuery with temporal, composite event features to combine techniques for continuous queries in stream processing, incremental evaluation in condition monitoring, and detection and filtering of composite events, creating an expressive environment for the extraction of meaningful events from multiple data streams with XML views.
Cite as

Susan Urban, Suzanne Dietrich, and Yi Chen. An XML Framework for Integrating Continuous Queries, Composite Event Detection, and Database Condition Monitoring for Multiple Data Streams. In Event Processing. Dagstuhl Seminar Proceedings, Volume 7191, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{urban_et_al:DagSemProc.07191.3,
  author =	{Urban, Susan and Dietrich, Suzanne and Chen, Yi},
  title =	{{An XML Framework for Integrating Continuous Queries, Composite Event Detection, and Database Condition Monitoring for Multiple Data Streams}},
  booktitle =	{Event Processing},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7191},
  editor =	{Mani Chandy and Opher Etzion and Rainer von Ammon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07191.3},
  URN =		{urn:nbn:de:0030-drops-11423},
  doi =		{10.4230/DagSemProc.07191.3},
  annote =	{Keywords: Composite events, stream processing, event filtering, extended XQuery, distributed event processing}
}

Chen, Yin

Document
DOI: 10.4230/DagSemProc.07351.12
Forgetting and Update – an exploration

Authors: Abhaya Nayak, Yin Chen, and Fangzhen Lin

Published in: Dagstuhl Seminar Proceedings, Volume 7351, Formal Models of Belief Change in Rational Agents (2007)

Abstract
Knowledge Update (respectively Erasure) and Forgetting are two very different concepts, with very different underlying motivation. Both are tools for knowledge management; however while the former is meant for accommodating new knowledge into a knowledge corpus, the latter is meant for modifying – in fact reducing the expressivity – of the underlying language. In this paper we show that there is an intimate connection between these two concepts: a particular form of knowledge update and literal forgetting are inter-definable. This connection is exploited to enhance both our understanding of update as well as forgetting in this paper.
Cite as

Abhaya Nayak, Yin Chen, and Fangzhen Lin. Forgetting and Update – an exploration. In Formal Models of Belief Change in Rational Agents. Dagstuhl Seminar Proceedings, Volume 7351, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{nayak_et_al:DagSemProc.07351.12,
  author =	{Nayak, Abhaya and Chen, Yin and Lin, Fangzhen},
  title =	{{Forgetting and Update – an exploration}},
  booktitle =	{Formal Models of Belief Change in Rational Agents},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7351},
  editor =	{Giacomo Bonanno and James Delgrande and J\'{e}r\^{o}me Lang and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07351.12},
  URN =		{urn:nbn:de:0030-drops-12131},
  doi =		{10.4230/DagSemProc.07351.12},
  annote =	{Keywords: Knowledge Update, Erasure, Forgetting, Dalal Distance, Winslett Distance.}
}

Chen, Yijia

Document
DOI: 10.4230/LIPIcs.MFCS.2022.32
On Algorithms Based on Finitely Many Homomorphism Counts

Authors: Yijia Chen, Jörg Flum, Mingjun Liu, and Zhiyang Xun

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
It is well known [L. Lovász, 1967] that up to isomorphism a graph G is determined by the homomorphism counts hom(F, G), i.e., by the number of homomorphisms from F to G where F ranges over all graphs. Moreover, it suffices that F ranges over the graphs with at most as many vertices as G. Thus, in principle, we can answer any query concerning G with only accessing the hom(⋅, G)’s instead of G itself. In this paper, we deal with queries for which there is a hom algorithm, i.e., there are finitely many graphs F₁, …, F_k such that for any graph G whether it is a Yes-instance of the query is already determined by the vector hom^⟶_{F₁, …, F_k}(G): = (hom(F₁, G), …, hom(F_k, G)). We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. On the other hand, queries expressible as a Boolean combination of universal sentences in first-order logic FO have a hom algorithm. Even though it is not easy to find FO definable queries without a hom algorithm, we succeed to show this for the non-existence of an isolated vertex, a property expressible by the FO sentence ∀ x∃ y Exy, somehow the "simplest" graph property not definable by a Boolean combination of universal sentences. These results provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm. For adaptive hom algorithms, i.e., algorithms that might access a hom(F_{i+1}, G) with F_{i+1} depending on hom(F_j, G) for 1 ≤ j ≤ i we show that three homomorphism counts hom(⋅, G) are sufficient and in general necessary to determine the (isomorphism type of) G. In particular, by three adaptive queries we can answer any question on G. Moreover, adaptively accessing two hom(⋅, G)’s is already enough to detect an isolated vertex. In 1993 Chaudhuri and Vardi [S. Chaudhuri and M. Y. Vardi, 1993] showed the analogue of the Lovász Isomorphism Theorem for the right homomorphism vector of a graph G, i.e, the vector of values hom(G,F) where F ranges over all graphs characterizes the isomorphism type of G. We study to what extent our results carry over to the right homomorphism vector.
Cite as

Yijia Chen, Jörg Flum, Mingjun Liu, and Zhiyang Xun. On Algorithms Based on Finitely Many Homomorphism Counts. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.MFCS.2022.32,
  author =	{Chen, Yijia and Flum, J\"{o}rg and Liu, Mingjun and Xun, Zhiyang},
  title =	{{On Algorithms Based on Finitely Many Homomorphism Counts}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.32},
  URN =		{urn:nbn:de:0030-drops-168301},
  doi =		{10.4230/LIPIcs.MFCS.2022.32},
  annote =	{Keywords: homomorphism numbers, hom algorithms, adaptive hom algorithms}
}
Document
DOI: 10.4230/LIPIcs.CSL.2020.15
FO-Definability of Shrub-Depth

Authors: Yijia Chen and Jörg Flum

Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)

Abstract
Shrub-depth is a graph invariant often considered as an extension of tree-depth to dense graphs. We show that the model-checking problem of monadic second-order logic on a class of graphs of bounded shrub-depth can be decided by AC^0-circuits after a precomputation on the formula. This generalizes a similar result on graphs of bounded tree-depth [Y. Chen and J. Flum, 2018]. At the core of our proof is the definability in first-order logic of tree-models for graphs of bounded shrub-depth.
Cite as

Yijia Chen and Jörg Flum. FO-Definability of Shrub-Depth. In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CSL.2020.15,
  author =	{Chen, Yijia and Flum, J\"{o}rg},
  title =	{{FO-Definability of Shrub-Depth}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Fern\'{a}ndez, Maribel and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.15},
  URN =		{urn:nbn:de:0030-drops-116587},
  doi =		{10.4230/LIPIcs.CSL.2020.15},
  annote =	{Keywords: shrub-depth, model-checking, monadic second-order logic}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.54
The Complexity of Homomorphism Indistinguishability

Authors: Jan Böker, Yijia Chen, Martin Grohe, and Gaurav Rattan

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
For every graph class {F}, let HomInd({F}) be the problem of deciding whether two given graphs are homomorphism-indistinguishable over {F}, i.e., for every graph F in {F}, the number hom(F, G) of homomorphisms from F to G equals the corresponding number hom(F, H) for H. For several natural graph classes (such as paths, trees, bounded treewidth graphs), homomorphism-indistinguishability over the class has an efficient structural characterization, resulting in polynomial time solvability [H. Dell et al., 2018]. In particular, it is known that two non-isomorphic graphs are homomorphism-indistinguishable over the class {T}_k of graphs of treewidth k if and only if they are not distinguished by k-dimensional Weisfeiler-Leman algorithm, a central heuristic for isomorphism testing: this characterization implies a polynomial time algorithm for HomInd({T}_k), for every fixed k in N. In this paper, we show that there is a polynomial-time-decidable class {F} of undirected graphs of bounded treewidth such that HomInd({F}) is undecidable. Our second hardness result concerns the class {K} of complete graphs. We show that HomInd({K}) is co-NP-hard, and in fact, we show completeness for the class C_=P (under P-time Turing reductions). On the algorithmic side, we show that HomInd({P}) can be solved in polynomial time for the class {P} of directed paths. We end with a brief study of two variants of the HomInd({F}) problem: (a) the problem of lexographic-comparison of homomorphism numbers of two graphs, and (b) the problem of computing certain distance-measures (defined via homomorphism numbers) between two graphs.
Cite as

Jan Böker, Yijia Chen, Martin Grohe, and Gaurav Rattan. The Complexity of Homomorphism Indistinguishability. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{boker_et_al:LIPIcs.MFCS.2019.54,
  author =	{B\"{o}ker, Jan and Chen, Yijia and Grohe, Martin and Rattan, Gaurav},
  title =	{{The Complexity of Homomorphism Indistinguishability}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.54},
  URN =		{urn:nbn:de:0030-drops-109980},
  doi =		{10.4230/LIPIcs.MFCS.2019.54},
  annote =	{Keywords: graph homomorphism numbers, counting complexity, treewidth}
}
Document
DOI: 10.4230/LIPIcs.CSL.2017.19
Slicewise Definability in First-Order Logic with Bounded Quantifier Rank

Authors: Yijia Chen, Jörg Flum, and Xuangui Huang

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
For every natural number q let FO_q denote the class of sentences of first-order logic FO of quantifier rank at most q. If a graph property can be defined in FO_q, then it can be decided in time O(n^q). Thus, minimizing q has favorable algorithmic consequences. Many graph properties amount to the existence of a certain set of vertices of size k. Usually this can only be expressed by a sentence of quantifier rank at least k. We use the color coding method to demonstrate that some (hyper)graph problems can be defined in FO_q where q is independent of k. This property of a graph problem is equivalent to the question of whether the corresponding parameterized problem is in the class para-AC^0. It is crucial for our results that the FO-sentences have access to built-in addition and multiplication (and constants for an initial segment of natural numbers whose length depends only on k). It is known that then FO corresponds to the circuit complexity class uniform AC^0. We explore the connection between the quantifier rank of FO-sentences and the depth of AC^0-circuits, and prove that FO_q is strictly contained in FO_{q+1} for structures with built-in addition and multiplication.
Cite as

Yijia Chen, Jörg Flum, and Xuangui Huang. Slicewise Definability in First-Order Logic with Bounded Quantifier Rank. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CSL.2017.19,
  author =	{Chen, Yijia and Flum, J\"{o}rg and Huang, Xuangui},
  title =	{{Slicewise Definability in First-Order Logic with Bounded Quantifier Rank}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.19},
  URN =		{urn:nbn:de:0030-drops-76742},
  doi =		{10.4230/LIPIcs.CSL.2017.19},
  annote =	{Keywords: first-order logic, quantifier rank, parameterized AC^0, circuit depth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.27
Some Lower Bounds in Parameterized AC^0

Authors: Yijia Chen and Jörg Flum

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical AC^0. Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a parameterized halting problem, which recently turned out to link problems of computational complexity, descriptive complexity, and proof theory. To show the first lower bound, we prove a strong AC^0 version of the planted clique conjecture: AC^0-circuits asymptotically almost surely can not distinguish between a random graph and this graph with a randomly planted clique of any size <= n^xi (where 0 <= xi < 1).
Cite as

Yijia Chen and Jörg Flum. Some Lower Bounds in Parameterized AC^0. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.MFCS.2016.27,
  author =	{Chen, Yijia and Flum, J\"{o}rg},
  title =	{{Some Lower Bounds in Parameterized AC^0}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.27},
  URN =		{urn:nbn:de:0030-drops-64423},
  doi =		{10.4230/LIPIcs.MFCS.2016.27},
  annote =	{Keywords: parameterized AC^0, lower bound, clique, halting problem}
}

Chen, Yi-Hsiu

Document
DOI: 10.4230/LIPIcs.CCC.2018.23
A Tight Lower Bound for Entropy Flattening

Authors: Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, and Jiapeng Zhang

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We study entropy flattening: Given a circuit C_X implicitly describing an n-bit source X (namely, X is the output of C_X on a uniform random input), construct another circuit C_Y describing a source Y such that (1) source Y is nearly flat (uniform on its support), and (2) the Shannon entropy of Y is monotonically related to that of X. The standard solution is to have C_Y evaluate C_X altogether Theta(n^2) times on independent inputs and concatenate the results (correctness follows from the asymptotic equipartition property). In this paper, we show that this is optimal among black-box constructions: Any circuit C_Y for entropy flattening that repeatedly queries C_X as an oracle requires Omega(n^2) queries. Entropy flattening is a component used in the constructions of pseudorandom generators and other cryptographic primitives from one-way functions [Johan Håstad et al., 1999; John Rompel, 1990; Thomas Holenstein, 2006; Iftach Haitner et al., 2006; Iftach Haitner et al., 2009; Iftach Haitner et al., 2013; Iftach Haitner et al., 2010; Salil P. Vadhan and Colin Jia Zheng, 2012]. It is also used in reductions between problems complete for statistical zero-knowledge [Tatsuaki Okamoto, 2000; Amit Sahai and Salil P. Vadhan, 1997; Oded Goldreich et al., 1999; Vadhan, 1999]. The Theta(n^2) query complexity is often the main efficiency bottleneck. Our lower bound can be viewed as a step towards proving that the current best construction of pseudorandom generator from arbitrary one-way functions by Vadhan and Zheng (STOC 2012) has optimal efficiency.
Cite as

Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, and Jiapeng Zhang. A Tight Lower Bound for Entropy Flattening. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.CCC.2018.23,
  author =	{Chen, Yi-Hsiu and G\"{o}\"{o}s, Mika and Vadhan, Salil P. and Zhang, Jiapeng},
  title =	{{A Tight Lower Bound for Entropy Flattening}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{23:1--23:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.23},
  URN =		{urn:nbn:de:0030-drops-88669},
  doi =		{10.4230/LIPIcs.CCC.2018.23},
  annote =	{Keywords: Entropy, One-way function}
}

Chen, Yiqun

Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.40
Estimating Building Age from Google Street View Images Using Deep Learning (Short Paper)

Authors: Yan Li, Yiqun Chen, Abbas Rajabifard, Kourosh Khoshelham, and Mitko Aleksandrov

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Building databases are a fundamental component of urban analysis. However such databases usually lack detailed attributes such as building age. With a large volume of building images being accessible online via API (such as Google Street View), as well as the fast development of image processing techniques such as deep learning, it becomes feasible to extract information from images to enrich building databases. This paper proposes a novel method to estimate building age based on the convolutional neural network for image features extraction and support vector machine for construction year regression. The contributions of this paper are two-fold: First, to our knowledge, this is the first attempt for estimating building age from images by using deep learning techniques. It provides new insight for planners to apply image processing and deep learning techniques for building database enrichment. Second, an image-base building age estimation framework is proposed which doesn't require information on building height, floor area, construction materials and therefore makes the analysis process simpler and more efficient.
Cite as

Yan Li, Yiqun Chen, Abbas Rajabifard, Kourosh Khoshelham, and Mitko Aleksandrov. Estimating Building Age from Google Street View Images Using Deep Learning (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 40:1-40:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.GISCIENCE.2018.40,
  author =	{Li, Yan and Chen, Yiqun and Rajabifard, Abbas and Khoshelham, Kourosh and Aleksandrov, Mitko},
  title =	{{Estimating Building Age from Google Street View Images Using Deep Learning}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{40:1--40:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.40},
  URN =		{urn:nbn:de:0030-drops-93682},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.40},
  annote =	{Keywords: Building database, deep learning, CNN, SVM, Google Street View}
}

Chen, Yiling

Document
DOI: 10.4230/LIPIcs.ITCS.2022.44
Cursed yet Satisfied Agents

Authors: Yiling Chen, Alon Eden, and Juntao Wang

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In real-life auctions, a widely observed phenomenon is the winner’s curse - the winner’s high bid implies that the winner often overestimates the value of the good for sale, resulting in an incurred negative utility. The seminal work of Eyster and Rabin [Econometrica'05] introduced a behavioral model aimed to explain this observed anomaly. We term agents who display this bias "cursed agents." We adopt their model in the interdependent value setting, and aim to devise mechanisms that prevent the agents from obtaining negative utility. We design mechanisms that are cursed ex-post incentive compatible, that is, incentivize agents to bid their true signal even though they are cursed, while ensuring that the outcome is ex-post individually rational (EPIR) - the price the agents pay is no more than the agents' true value. Since the agents might overestimate the value of the allocated good, such mechanisms might require the seller to make positive (monetary) transfers to the agents in order to prevent agents from over-paying for the good. While the revenue of the seller not requiring EPIR might increase when agents are cursed, when imposing EPIR, cursed agents will always pay less than fully rational agents (due to the positive transfers the seller makes). We devise revenue and welfare maximizing mechanisms for cursed agents. For revenue maximization, we give the optimal deterministic and anonymous mechanism. For welfare maximization, we require ex-post budget balance (EPBB), as positive transfers might cause the seller to have negative revenue. We propose a masking operation that takes any deterministic mechanism, and masks the allocation whenever the seller requires to make positive transfers. The masking operation ensures that the mechanism is both EPIR and EPBB. We show that in typical settings, EPBB implies that the mechanism cannot make any positive transfers. Thus, applying the masking operation on the fully efficient mechanism results in a socially optimal EPBB mechanism. This further implies that if the valuation function is the maximum of agents' signals, the optimal EPBB mechanism obtains zero welfare. In contrast, we show that for sum-concave valuations, which include weighted-sum valuations and 𝓁_p-norms, the welfare optimal EPBB mechanism obtains half of the optimal welfare as the number of agents grows large.
Cite as

Yiling Chen, Alon Eden, and Juntao Wang. Cursed yet Satisfied Agents. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, p. 44:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2022.44,
  author =	{Chen, Yiling and Eden, Alon and Wang, Juntao},
  title =	{{Cursed yet Satisfied Agents}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{44:1--44:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.44},
  URN =		{urn:nbn:de:0030-drops-156407},
  doi =		{10.4230/LIPIcs.ITCS.2022.44},
  annote =	{Keywords: Mechanism Design, Interdependent Valuation Auction, Bounded Rationality, Cursed Equilibrium, Winner’s curse}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact